حساب أي البلاط مضاءة في لعبة تعتمد على البلاط ("Raytracing")

Question

أنا أكتب لعبة صغيرة قائمة على البلاط ، والتي أود دعم مصادر الضوء. لكن خوارزمي فو ضعيف جدًا ، وبالتالي أتيت إليك طلبًا للمساعدة.

الموقف مثل هذا: هناك خريطة تستند إلى البلاط (تم عقدها كصفيف ثنائي الأبعاد) ، والتي تحتوي على مصدر ضوء واحد وعدة عناصر تقف حولها. أريد حساب أي البلاط الذي يضيء بواسطة مصدر الضوء ، وأيها في الظل.

مساعدة بصرية لما يبدو عليه ، تقريبًا. L هو مصدر الضوء ، XS هي عناصر تمنع الضوء ، و 0s هي البلاط المضاءة ، والبلاط -s في الظل.

0 0 0 0 0 0 - - 0
0 0 0 0 0 0 - 0 0
0 0 0 0 0 X 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 L 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 X X X X 0 0
0 0 0 - - - - - 0
0 0 - - - - - - -

سيكون نظام الكسور أفضل ، بالطبع ، حيث يمكن أن يكون البلاط في نصفين بسبب حجبه جزئيًا. لن تكون الخوارزمية مثالية - ليست خاطئة وسرعة معقولة.

(بالطبع ، سيكون هناك مصادر إضاءة متعددة ، لكن هذه مجرد حلقة.)

أي من الأشخاص يود ذلك؟

Answer 1

يمتلك مجتمع التنمية في Roguelike جزءًا من هاجس خوارزميات خط العرض.

إليك رابط لمقال Wiki Roguelike حول هذا الموضوع:http://roguebasin.roguelikedevelopment.org/index.php؟title=field_of_vision

في لعبة Roguelike الخاصة بي ، قمت بتطبيق خوارزمية لإلقاء الظل (http://roguebasin.roguelikedevelopment.org/index.php؟title=shadow_casting) في بيثون. كان من المعقد بعض الشيء تجميعها ، ولكن ركض بكفاءة بشكل معقول (حتى في الثعبان النقي) وتوليد نتائج لطيفة.

يبدو أن "مجال الرؤية المسموح به" يكتسب شعبية أيضًا:http://roguebasin.roguelikedevelopment.org/index.php؟title=permissive_field_of_view

Answer 2

يمكنك الدخول في جميع أنواع التعقيدات مع حساب انسداد وما إلى ذلك ، أو يمكنك الذهاب إلى طريقة القوة الغاشمة البسيطة: لكل خلية ، استخدم خوارزمية رسم خط مثل خوارزمية خط بريسنهام لفحص كل خلية بين التيار ومصدر الضوء. إذا كانت هناك خلايا مملوءة أو (إذا كان لديك مصدر واحد فقط من المصدر للضوء) تم اختبارها بالفعل ووجد أنها في الظل ، فإن خليةك في الظل. إذا واجهت خلية معروفة أنها مضاءة ، فستضيء خليةك بالمثل. من السهل التحسين لهذا هو تعيين حالة أي خلايا تواجهها على طول الخط إلى أي النتيجة النهائية.

هذا أكثر أو أقل ما استخدمته في بلدي 2004 دخول الفوز IOCCC. من الواضح أن هذا لا يجعل رمز مثال جيد. ؛)

تحرير: كما يشير لورين ، مع هذه التحسينات ، تحتاج فقط إلى اختيار وحدات البكسل على طول حافة الخريطة لتتبعها.

Answer 3

يبدو لي الخوارزميات التي يتم تقديمها هنا أنها تقوم بحسابات أكثر مما أعتقد أنه مطلوب. لم أختبر هذا ولكن أعتقد أنه سيعمل:

في البداية ، حدد جميع وحدات البكسل كما مضاء.

لكل بكسل على حافة الخريطة: كما اقترح Arachnid ، استخدم Bresenham لتتبع خط من البكسل إلى الضوء. إذا ضرب هذا الخط عرقلة ، فقم بتمييز جميع وحدات البكسل من الحافة إلى ما وراء الانسداد كما هو في الظل.

Answer 4

سريع و قذر:

(اعتمادًا على حجم الصفيف)

• حلقة من خلال كل بلاط
• ارسم خطًا إلى الضوء
• إذا كان أي ثمل من الخط يضرب X ، فهو في الظل
• (اختياري): احسب كمية X التي يمر بها الخط والقيام بالرياضيات الفاخرة لتحديد نسبة البلاط في الظل. NB: يمكن القيام بذلك عن طريق مكافحة الخط الفاصل بين البلاط والضوء (وبالتالي النظر إلى البلاط الأخرى على طول الطريق إلى مصدر الضوء) أثناء إجراء العتبة ، ستظهر هذه كآثار صغيرة. اعتمادًا على المنطق المستخدم ، يمكن أن تحدد مقدار (إن وجدت) البلاط في الظل.

يمكنك أيضًا متابعة مسار تم اختبار وحدات البكسل ، وبالتالي قم بتحسين الحل قليلاً وليس إعادة اختبار وحدات البكسل مرتين.

قد يكون هذا جيدًا بشكل جيد باستخدام معالجة الصور ورسم خطوط مستقيمة بين البيكلين (البلاط) إذا كانت الخطوط شبه شفافة وكتل X شبه شفافة مرة أخرى. يمكنك عتبة الصورة لتحديد ما إذا كان الخط قد تداخل "X"

إذا كان لديك خيار لاستخدام أداة الطرف الثالث ، فمن المحتمل أن تأخذها. على المدى الطويل قد يكون أسرع ، لكنك ستفهم أقل عن لعبتك.

Answer 5

هذا للتسلية فقط:

يمكنك تكرار نهج Doom 3 في 2D إذا قمت أولاً بتنفيذ خطوة لتحويل البلاط إلى خطوط. على سبيل المثال،

- - - - -
- X X X -
- X X - -
- X - - -
- - - - L

... سيتم تقليلها إلى ثلاثة خطوط تربط زوايا الكائن الصلب في مثلث.

ثم ، افعل ما يفعله محرك Doom 3: من منظور مصدر الضوء ، فكر في كل "جدار" يواجه الضوء. (في هذا المشهد ، سيتم النظر فقط في الخط قطري.) لكل خط من هذا القبيل ، قم بإعداده في شبه منحرف هو الحافة الأمامية هي الخط الأصلي ، الذي تقع جوانبه على خطوط من مصدر الضوء من خلال كل نقطة نهاية ، والتي يكون ظهرها بعيدا ، الماضي المشهد بأكمله. لذلك ، إنه شبه منحرف "يشير إلى" الضوء. أنه يحتوي على كل المساحة التي يلقي بها الجدار ظله. املأ كل بلاط في هذا المنحرف مع الظلام.

تابع جميع هذه الخطوط وستنتهي بـ "استنسل" يتضمن جميع البلاط المرئي من مصدر الضوء. املأ هذه البلاط باللون الفاتح. قد ترغب في إضاءة البلاط أقل بقليل مع الابتعاد عن المصدر ("التوهين") أو القيام بأشياء رائعة أخرى.

كرر لكل مصدر ضوء في المشهد الخاص بك.

Answer 6

للتحقق مما إذا كان البلاط في الظل ، تحتاج إلى رسم خط مستقيم إلى مصدر الضوء. إذا كان الخط يتقاطع مع بلاط آخر مشغول ، فإن البلاط الذي كنت تختبره في الظل. تقوم خوارزميات Raytracing بذلك لكل كائن (في بلاط قضيتك) في العرض.

ال مقالة Raytracing على ويكيبيديا لديه رمز كاذب.

Answer 7

فيما يلي نهج بسيط للغاية ولكنه فعال إلى حد ما يستخدم الوقت الخطي في عدد البلاط على الشاشة. كل بلاط إما غير شفاف أو شفاف (يتم منحنا لنا) ، ويمكن أن يكون كل منهما مرئيًا أو مظللاً (هذا ما نحاول حسابه).

نبدأ بوضع علامة على الصورة الرمزية نفسها على أنها "مرئية".

ثم نطبق هذه القاعدة العودية لتحديد رؤية البلاط المتبقية.

1. إذا كان البلاط على نفس الصف أو العمود مثل الصورة الرمزية ، فسيكون ذلك مرئيًا فقط إذا كان البلاط المجاور بالقرب من الصورة الرمزية مرئية وشفافة.
2. إذا كان البلاط على 45 درجة قطرية من الصورة الرمزية ، فمن المرئي فقط إذا كان البلاط القطري المجاور (نحو الصورة الرمزية) مرئيًا وشفافًا.
3. في جميع الحالات الأخرى ، ضع في اعتبارك البلاط الثلاثة المجاورة أقرب إلى الصورة الرمزية من البلاط المعني. على سبيل المثال ، إذا كان هذا البلاط في (x ، y) وهو أعلى وإلى يمين الصورة الرمزية ، فإن البلاط الثلاثة يجب مراعاته هو (x-1 ، y) ، (x ، y-1) و (x- 1 ، Y-1). البلاط المعني مرئي إذا أي من تلك البلاط الثلاثة مرئية وشفافة.

من أجل جعل هذا العمل ، يجب فحص البلاط بترتيب محدد لضمان حساب الحالات العودية بالفعل. فيما يلي مثال على طلب العمل ، بدءًا من 0 (وهو الصورة الرمزية نفسها) والعد:

9876789
8543458
7421247
6310136
7421247
8543458
9876789

يمكن فحص البلاط مع نفس العدد بأي ترتيب فيما بينها.

والنتيجة ليست جميلة في الظل ، ولكنها تحسب رؤية البلاط المعقولة.

Answer 8

حل TK هو الحل الذي ستستخدمه بشكل عام لهذا النوع من الأشياء.

بالنسبة لسيناريو الإضاءة الجزئي ، يمكنك الحصول عليه بحيث إذا كان البلاط ينتج عنه ظل ، فسيتم تقسيم هذا البلاط إلى 4 بلاط ويتم اختبار كل منها. يمكنك بعد ذلك تقسيم ذلك بقدر ما تريد؟

يحرر:

يمكنك أيضًا تحسينه قليلاً من خلال عدم اختبار أي من البلاط المجاور للضوء - سيكون هذا أكثر أهمية عندما يكون لديك مصادر إضاءة متعددة ، على ما أعتقد ...

Answer 9

لقد كتبت هذه الوظيفة مؤخرًا في أحد مشاريعي.

void Battle::CheckSensorRange(Unit* unit,bool fog){
    int sensorRange = 0;
    for(int i=0; i < unit->GetSensorSlots(); i++){
        if(unit->GetSensorSlot(i)->GetSlotEmpty() == false){
            sensorRange += unit->GetSensorSlot(i)->GetSensor()->GetRange()+1;
        }
    }
    int originX = unit->GetUnitX();
    int originY = unit->GetUnitY();

    float lineLength;
    vector <Place> maxCircle;

    //get a circle around the unit
    for(int i = originX - sensorRange; i < originX + sensorRange; i++){
        if(i < 0){
            continue;
        }
        for(int j = originY - sensorRange; j < originY + sensorRange; j++){
            if(j < 0){
                continue;
            }
            lineLength = sqrt( (float)((originX - i)*(originX - i)) + (float)((originY - j)*(originY - j)));
            if(lineLength < (float)sensorRange){
                Place tmp;
                tmp.x = i;
                tmp.y = j;
                maxCircle.push_back(tmp);
            }
        }
    }

    //if we're supposed to fog everything we don't have to do any fancy calculations
    if(fog){
        for(int circleI = 0; circleI < (int) maxCircle.size(); circleI++){
            Map->GetGrid(maxCircle[circleI].x,maxCircle[circleI].y)->SetFog(fog);
        }
    }else{

        bool LOSCheck = true;
        vector <bool> placeCheck;

        //have to check all of the tiles to begin with 
        for(int circleI = 0; circleI < (int) maxCircle.size(); circleI++){
            placeCheck.push_back(true);
        }

        //for all tiles in the circle, check LOS
        for(int circleI = 0; circleI < (int) maxCircle.size(); circleI++){
            vector<Place> lineTiles;
            lineTiles = line(originX, originY, maxCircle[circleI].x, maxCircle[circleI].y);

            //check each tile in the line for LOS
            for(int lineI = 0; lineI < (int) lineTiles.size(); lineI++){
                if(false == CheckPlaceLOS(lineTiles[lineI], unit)){
                    LOSCheck = false;

                    //mark this tile not to be checked again
                    placeCheck[circleI] = false;
                }
                if(false == LOSCheck){
                    break;
                }
            }

            if(LOSCheck){
                Map->GetGrid(maxCircle[circleI].x,maxCircle[circleI].y)->SetFog(fog);
            }else{
                LOSCheck = true;
            }
        }
    }

}

هناك بعض الأشياء الإضافية التي لن تحتاجها إذا كنت تقوم بتكييفها للاستخدام الخاص بك. يتم تعريف المكان فقط على أنه موضع X و Y لصالح وسائل الراحة.

وظيفة الخط مأخوذة من ويكيبيديا مع تعديلات صغيرة جدا. بدلاً من طباعة إحداثيات XY ، قمت بتغييرها لإرجاع متجه مكان مع جميع النقاط في السطر. تُرجع وظيفة checkplacelos فقط بشكل صحيح أو خطأ بناءً على ما إذا كان البلاط يحتوي على كائن عليه. هناك المزيد من التحسينات التي يمكن القيام بها مع هذا ولكن هذا جيد لاحتياجاتي.

Answer 10

أعلم أن هذا سؤال يبلغ من العمر سنوات ، ولكن عن أي شخص يبحث عن هذا النمط من الأشياء ، أود أن أقدم حلًا استخدمته مرة واحدة لروغويلي ؛ يدويًا "FOV" يدويًا. إذا كنت لدى Field of View of Light Source مسافة خارجية أقصى ، فليس من الجهد كبيرًا جدًا لجذب الظلال التي تم إنشاؤها عن طريق حظر الكائنات. تحتاج فقط إلى رسم 1/8 من الدائرة (بالإضافة إلى الاتجاهات المستقيمة والقطرية) ؛ يمكنك استخدام symmerty ل eigths الأخرى. سيكون لديك العديد من خرائط الظل كما لديك مربعات في تلك الدائرة 1/8. ثم فقط أو معا وفقا للكائنات.

الايجابيات الرئيسية الثلاثة لهذا هي: 1. إنه سريع للغاية إذا تم تنفيذه بشكل صحيح 2. يمكنك أن تقرر كيف يجب أن يتم إلقاء الظل ، ولا تقارن الخوارزف الذي يتعامل مع الموقف هو الأفضل 3. إصلاح بطريقة ما

الخداع هو أنك لا تحصل حقًا على تنفيذ خوارزمية ممتعة.

Answer 11

لقد قمت بتطبيق مجال الرؤية القائم على TileBased في وظيفة C واحدة. ها هو:https://gist.github.com/zloedi/9551625

Answer 12

إذا كنت لا ترغب في قضاء الوقت لإعادة اختراع/إعادة تنفيذ ذلك ، فهناك الكثير من محركات الألعاب هناك. Ogre3d هو محرك لعبة مفتوح المصدر يدعم الإضاءة بالكامل ، وكذلك عناصر التحكم في الصوت والألعاب.