مرحبا يا هبر!
بصفتنا
نواباً عن
الوحدة في السوق الروسية ، نقدم لك قراءة دراسة مثيرة للاهتمام حول الاستخدام العملي لخوارزمية WFC (Wave Function Collapse) ، المبنية في صورة ومثال مبدأ معروف جيدًا لميكانيكا الكم ومناسب جدًا للجيل الإجرائي من المستويات في الألعاب. في وقت سابق على Habré تم
نشر القصة التفصيلية حول هذه الخوارزمية. ينظر مؤلف مقالة اليوم ، ماريان كلاينبرج ، إلى الخوارزمية في سياق الرسومات ثلاثية الأبعاد وتوليد مدينة لا نهاية لها. هل لديك قراءة لطيفة!
سنتحدث عن لعبة تمشي فيها عبر مدينة لا نهاية لها يتم إنشاؤها إجرائيًا أثناء تنقلك. تم بناء المدينة من مجموعة من الكتل باستخدام خوارزمية WFC (انهيار دالة الموجة).
التجميع القابل للتشغيل متاح للتنزيل على موقع
itch.io. يمكنك أيضا أن تأخذ
شفرة المصدر على جيثب . أخيرًا ، أقترح
مقطع فيديو أسير فيه عبر المدينة.
خوارزمية
سأدعو كلمة "خلية" عنصر شبكة ثلاثية الأبعاد يمكن أن يحتوي على كتلة أو يكون فارغًا. كلمة "وحدة" سأدعو كتلة يمكن أن تشغل مثل هذه الخلية.
تقرر الخوارزمية الوحدات النمطية التي يجب تحديدها في كل خلية من خلايا اللعبة. تعتبر مجموعة من الخلايا دالة موجية في شكل غير قابل للملاحظة. وبالتالي ، كل خلية يتوافق مع العديد من الوحدات التي قد تظهر فيه. فيما يتعلق بميكانيكا الكم ، يمكن للمرء أن يقول ، "الخلية في تراكب جميع الوحدات". يبدأ وجود العالم في شكل لا يمكن ملاحظته تمامًا ، حيث يمكن أن تكون أي وحدة في كل خلية. علاوة على ذلك ، كل الخلايا تنهار ، واحدة تلو الأخرى. هذا يعني أنه لكل خلية يتم اختيار وحدة واحدة بشكل عشوائي من كل ما هو ممكن.
والخطوة التالية هي انتشار القيد. لكل وحدة ، يتم تحديد مجموعة فرعية من الوحدات النمطية التي يسمح لها أن تكون مجاورة لها. في كل مرة تنهار فيها وحدة ، يتم تحديث مجموعات فرعية من الوحدات النمطية الأخرى ، والتي لا يزال مسموحًا بها بجوارها. مرحلة نشر القيود هي الجزء الأكثر استهلاكًا للموارد من الخوارزمية من حيث القدرة الحاسوبية.
أحد الجوانب المهمة للخوارزمية هو تحديد الخلية التي ستنهار. دائمًا ما تنهار الخوارزمية مع
أصغر إنتروبيا . هذه هي الخلية التي تسمح بأقل عدد من الخيارات (أي ، الخلية ذات الأقل عشوائية). إذا كان احتمال الانهيار هو نفسه بالنسبة لجميع الوحدات ، فإن الخلية التي تحتوي على أقل عدد ممكن من الوحدات النمطية سيكون لها أدنى انتروبيا. وكقاعدة عامة ، فإن احتمالات الاختيار مختلفة بالنسبة للوحدات النمطية المختلفة المتاحة. توفر الخلية التي تحتوي على وحدتين محتملتين لهما نفس الاحتمال خيارًا أوسع (الانتروبيا الأكبر) من الخلية التي يوجد بها وحدتان ، واحتمال حدوث السقوط تحت الخيار واحدًا كبيرًا بالنسبة لأحدهما ، والآخر صغير جدًا.
(GIF نشرته
ExUtumno على جيثب)
يمكن العثور على مزيد من المعلومات التفصيلية حول خوارزمية انهيار دالة الموجات ، فضلاً عن عدد من الأمثلة الجميلة ، هنا. في البداية ، تم اقتراح هذه الخوارزمية لتوليد مواد ثنائية الأبعاد تعتمد على عينة واحدة. في هذه الحالة ، يتم تحديد المؤشرات الاحتمالية للوحدات النمطية والقواعد المجاورة اعتمادًا على حدوثها في المثال. توفر هذه المقالة هذه المعلومات يدويًا.
إليك
مقطع فيديو يوضح هذه الخوارزمية قيد التنفيذ.
حول الكتل والنماذج الأولية والوحدات النمطية
يتم إنشاء العالم من مجموعة فيها حوالي 100 كتل. أنا خلقت لهم باستخدام خلاط. في البداية ، كان لدي عدد قليل جدًا من الكتل ، وأضفتها قليلًا عندما اعتبرتها ضرورية.
تحتاج الخوارزمية إلى معرفة الوحدات التي يمكن تحديد موقعها بجوار بعضها البعض. لكل وحدة ، هناك 6 قوائم من الجيران المحتملين ، واحدة في كل اتجاه. ومع ذلك ، أردت تجنب الاضطرار إلى إنشاء مثل هذه القائمة يدويًا. بالإضافة إلى ذلك ، أردت إنشاء خيارات مُدارة تلقائيًا لكل مجموعة من القطع الخاصة بي.
يتم حل كلتا هاتين المهمتين باستخدام ما يسمى بوحدات النموذج الأولي. في جوهرها ، هذا هو
MonoBehaviour ، وهو ملائم للعمل مع محرر Unity. يتم إنشاء الوحدات النمطية جنبًا إلى جنب مع قوائم العناصر المجاورة الصالحة والخيارات المدارة تلقائيًا بناءً على هذه النماذج الأولية.
نشأت مشكلة معقدة في نمذجة المعلومات المجاورة ، بحيث نجحت هذه العملية التلقائية. إليك ما حصلت عليه:
كل كتلة لديها 6 جهات اتصال ، واحدة لكل وجه. جهة الاتصال لديها رقم. بالإضافة إلى ذلك ، قد تكون جهات الاتصال الأفقية مقلوبة أو غير مقلوبة أو متماثلة. تحتوي جهات الاتصال الرأسية إما على مؤشر دوران في النطاق من 0 إلى 3 ، أو يتم تمييزها على أنها
ثابتة الدوران .
بناءً على ذلك ، يمكنني التحقق تلقائيًا من الوحدات التي يُسمح لها بالتوافق مع بعضها البعض. يجب أن تحتوي الوحدات المجاورة على نفس أرقام الدبوس. يجب أن يتزامن تناظرها أيضًا (نفس مؤشر التناوب العمودي ، زوج من الاتصالات الأفقية المقلوبة وغير المقلوبة) ، أو يجب أن تكون الوحدات متماثلة / ثابتة.
هناك قواعد استبعاد يمكنني بموجبها حظر خيارات الحي التي سيتم السماح بها افتراضيًا. بعض الكتل مع جهات الاتصال مطابقة ببساطة تبدو قبيحة في مكان قريب. فيما يلي مثال لخريطة تم إنشاؤها دون تطبيق قواعد الاستثناء:
الطريق إلى ما لا نهاية
تقوم خوارزمية انهيار دالة الموجة الأصلية بإنشاء خرائط ذات حجم محدد. كنت أرغب في بناء عالم يتوسع ويتوسع مع تقدمك.
في البداية ، حاولت إنشاء أجزاء ذات حجم محدود واستخدام جهات اتصال الأجزاء المجاورة كقيود. إذا تم إنشاء جزء ، كما تم إنشاء جزء مجاور له ، عندئذٍ فقط تلك الوحدات المسموح بها والتي تلائم الوحدات النمطية الموجودة. مع هذا النهج ، تنشأ المشكلة التالية: كلما انهارت الخلية ، فإن انتشار القيود سيقلل الفرص حتى على مسافة من عدة خلايا. الصورة التالية توضح آثار انهيار خلية واحدة:
إذا تم إنشاء جزء واحد فقط في كل خطوة من الخوارزمية ، فلا تنطبق القيود على الأجزاء المجاورة. في هذه الحالة ، تم اختيار هذه الوحدات داخل الجزء الذي سيكون غير مقبول إذا تم أخذ الأجزاء الأخرى في الاعتبار. نتيجة لذلك ، عندما حاولت الخوارزمية إنشاء الجزء التالي ، لم تتمكن من إيجاد حل واحد.
الآن لم أعد أستخدم الشظايا ، لكنني أحفظ الخريطة في قاموس يعرض موضع الخلية على خلية. تملأ الخلية فقط إذا لزم الأمر. يجب ضبط بعض عناصر الخوارزمية مع وضع ذلك في الاعتبار. عند اختيار خلية من المفترض أن تنهار ، يستحيل مراعاة جميع الخلايا إذا كان عددها غير محدود. بدلاً من ذلك ، فإننا نقوم بإنشاء جزء صغير فقط من الخريطة في وقت واحد ، بمجرد وصول اللاعب إليها. خارج هذه المنطقة ، تستمر القيود في الانتشار.
في بعض الحالات ، هذا النهج لا يعمل. النظر في مجموعة من وحدات لقسم مستقيم من نفق من الشكل أعلاه - لا يوجد مدخل للنفق. إذا اختارت الخوارزمية وحدة النفق هذه ، فإن النفق سيكون بلا حدود حسب التعريف. في مرحلة توزيع القيود ، سيحاول البرنامج تخصيص عدد لا حصر له من الخلايا. لقد قمت بتطوير مجموعة خاصة من الوحدات للتغلب على هذه المشكلة.
شروط الحدود
هناك نوعان من الشروط الحدودية الهامة. يجب أن يكون لجميع الوجوه في المستوى العلوي من الخريطة جهات اتصال "جوية". يجب أن يكون لكل الوجوه على قاعدة الخريطة جهات اتصال "صلبة". إذا لم يتم استيفاء هذه الشروط ، فسيظهر على الخريطة ثقوب في الأرض ، وستكون بعض المباني بدون سقف.
على خريطة ذات الحجم المحدود ، يمكن حل هذه المشكلة بسهولة. بالنسبة لجميع الخلايا في أعلى وأدنى مستوى ، سيكون من الضروري إزالة جميع الوحدات النمطية مع جهات اتصال غير مناسبة. ثم ابدأ في توزيع القيود وإزالة الوحدات المتبقية التي لم تعد تناسبنا.
على خريطة ذات حجم لا حصر له ، لن ينجح هذا ، لأنه في كل من المستوى الأعلى والأدنى ، لدينا عدد لا حصر له من الخلايا. الحل الأكثر سذاجة هو حذف جميع الخلايا غير المناسبة فور ظهورها. ومع ذلك ، عند إزالة وحدة نمطية في المستوى العلوي ، تنطبق القيود على تلك الخلايا المجاورة لها. هناك تأثير الانهيار ، مما يؤدي مرة أخرى إلى مجموعة لا حصر لها من الخلايا.
لقد حللت هذه المشكلة عن طريق إنشاء خريطة 1 × n × 1 ، حيث n هو الارتفاع. تستخدم هذه الخريطة التفاف العالم لنشر القيود. تعمل الآلية كما في لعبة Pacman: تجاوز الحافة اليمنى للخريطة ، تعود الشخصية إليها بسبب الحافة اليسرى. الآن يمكنني تطبيق أي قيود على خريطتي. في كل مرة تنشئ فيها خلية جديدة على خريطة لا حصر لها ، تتم تهيئة هذه الخلية بمجموعة من الوحدات النمطية التي تتوافق مع موضع معين على الخريطة.
شروط الخطأ والعودة البحث
تصل خوارزمية WFC أحيانًا إلى حالة لا تتوافق فيها الخلية مع أي وحدة نمطية محتملة. في التطبيقات التي نتعامل فيها مع عالم ذي حجم محدود ، يمكنك ببساطة إعادة تعيين النتيجة والبدء من جديد. في عالم لا حصر له ، لن ينجح هذا ، حيث يتم عرض جزء من العالم للاعب بالفعل. أولاً ، لقد توصلت إلى حل تمتلئ فيه الأماكن التي حدثت فيها الأخطاء بكتل بيضاء.
أنا حاليا باستخدام البحث عن عودة. يتم تخزين ترتيب انهيار الخلايا وبعض المعلومات حول توزيع القيود في شكل محفوظات. إذا فشلت خوارزمية WFC ، فسيتم إلغاء جزء من السجل. كقاعدة عامة ، يعمل هذا ، ولكن في بعض الأحيان يمكن التعرف على الأخطاء بعد فوات الأوان ، ويغطي البحث عن نتائج الكثير من الخطوات. في حالات نادرة ، يتم تجديد الخلية التي يقع فيها اللاعب.
في رأيي ، بسبب هذا القيد ، فإن تطبيق خوارزمية WFC مع عوالم لانهائية لا يناسب الألعاب التجارية.
قبل التاريخ
بدأت العمل في هذه المهمة بعد أن شاهدت
محاضرة أوسكار ستيلبرج حول كيفية استخدام الخوارزمية لإنشاء مستويات في لعبة Bad North. بشكل عام ، تم تنفيذ خوارزمية بلدي خلال أسبوع
procjam .
لديّ بعض الأفكار لتحسين هذه الخوارزمية ، لكنني لست متأكدًا من أنني سأضيف يومًا ما طريقة لعب لهذه اللعبة. وإذا اجتمعت - بالتأكيد لن تكون هذه استراتيجية ملحمية تخيلتها بالفعل. ومع ذلك ، إذا كنت تريد التحقق من كيفية عمل ميكانيكا الألعاب المفضلة لديك مع هذه الخوارزمية - فقط جربها بنفسك! في النهاية ، شفرة المصدر متاحة للجمهور ومرخصة من قبل معهد ماساتشوستس للتكنولوجيا.