ما هو الجيل الإجرائي؟

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

وظيفة خوارزمية انهيار الموجة ونطاقها

في هذه المقالة ، نقوم بفحص خوارزمية انهيار دالة الموج (WaveFunctionCollapse ، WFC) التي اقترحها Maxim Gumin (على Twitter ، هناك مجموعة من المحتوى المذهل الذي تم إنشاؤه باستخدام هذه الخوارزمية بواسطة مطورين آخرين!) للحصول على الجيل الإجرائي من الصور أو التضاريس من خلال إنشاء صور متشابهة محليًا مع الوارد صورة في شبكة بحجم معين.

تعتمد الخوارزمية على فكرة إنشاء صورة نهائية خطوة بخطوة مع تتبع أي تجانب "يتوافق" مع صورة تم إنشاؤها جزئيًا بالفعل. لدراسة الوصف التفصيلي للخوارزمية ، نوصيك بالرجوع إلى مستودع WFC الأصلي في Github والقسم الرابع من المقالة " WaveFunctionCollapse هو قيد القيد في البرية ".


أمثلة لصور البذور المنتجة من الناحية الإجرائية

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


أمثلة من البلاط المتولدة عشوائيا

التحدي وحلنا

لقد تولينا مهمة إنشاء بطاقة تجانب استنادًا إلى لعبة اللوحة Carcassonne ("Carcassonne") ، والتي يتم فيها إنشاء الحقل بواسطة اللاعبين "يدويًا" (انظر الرسوم المتحركة أدناه) من البلاطات التي يجب دمجها مع بعضها البعض.


والمثير للدهشة ، من الناحية النظرية ، أنها تشبه إلى حد كبير خوارزمية WFC لإنشاء بطاقات تجانب تعسفية عن طريق إضافة أجزاء جديدة إلى حل غير مكتمل. وبما أنه يمكن استخدام WaveFunctionCollapse كمولد بطاقة تجانب ، فإنه يمكن أيضًا إنشاء حقول "Carcassonne"!

ومع ذلك ، يوجد في اللعبة نفسها عدد كبير جدًا من المربعات المختلفة ، ويعتبر ترميز كل نسبها مهمة ضخمة جدًا للهاكاتون على مدار الساعة. لذلك ، قررنا تشغيل إصدار مبسط جدًا من "كاركاسون" بدون قلاع وأنهار ، فقط مع الطرق والأعشاب والأديرة. لذلك حصلنا على 6 بلاطات محتملة مع تناوبها وتماثلها. ولكن حتى في ظل هذه الظروف ، تبدو النتيجة جميلة وتبدو وكأنها لعبة حقيقية في كاركاسون!


تصور لملء خوارزمية حقل كاركاسون


مثال على القواعد المقدمة في الخوارزمية

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

النظرية الافتراضية توزيع الاحتمال الأولي

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


حلول مختلفة لتوزيعات احتمالية أولية مختلفة

مثال آخر: الاحتمالات الشرطية والتجميع

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

على الرغم من عدم مراعاة ذلك في الصورة أدناه ، فإن الاحتمال في اللعبة يعتمد أيضًا على ارتفاع التجانبات ، وبالتالي فإن الموضع في الصورة يمكن أن يؤثر أيضًا على شروط توزيع احتمالات التجانب.


ماين كرافت مثال على خريطة بلاط الخام التي أنشأتها WFC

استنتاج

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