الجيل الإجرائي متعدد الطوابق الأبراج المحصنة

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

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

بعدين

أولاً أحتاج إلى كتابة خوارزمية لبعدين. بشكل عام ، تعمل نفس خوارزمية TinyKeep ، ولكن لديها اختلافات لإنشاء مستويات أكثر إثارة للاهتمام.

يسمى المشهد لهذا المثال Dungeon2D. الرمز الخاص به موجود في المجلد Scripts2D.

خوارزمية

ينقسم العالم إلى شبكة مستطيلة. أفترض أن 1 وحدة ستكون كافية للإشارة إلى الممر. في لعبة كاملة ، يمكن أن تتوافق وحدة واحدة من الوحدة ، على سبيل المثال ، على بعد 5 أمتار. للشبكة ، اخترت حجم 30 × 30.

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


المستطيلات الحمراء عبارة عن غرف

2. إنشاء الرسم البياني التثليث Delaunay للغرف. لقد استخدمت خوارزمية Bower-Watson لهذا الغرض. هناك العديد من تطبيقات هذه الخوارزمية بعدة لغات ، لقد اخترت واحدة سيكون من السهل نقلها إلى C #.


ديلوناي تثليث

3. إنشاء شجرة تمتد الحد الأدنى (MST) من التثليث. لقد استخدمت خوارزمية Prim لهذا الغرض.


ممرات MST

4. نقوم بإنشاء قائمة من الممرات ، تبدأ من كل حافة الشجرة من المرحلة 3. تحتوي الشجرة على جميع الغرف ، وبالتالي فإن الطريق إلى كل غرفة مضمون. أضف عشوائيا الحواف من التثليث إلى القائمة. لذلك سنقوم بإنشاء عدة حلقات في الممرات. في الكود ، استخدمت احتمال إضافة كل حافة إلى 12.5٪.


ممرات بعد إضافة حواف متعددة إلى MST. لاحظ أن الحلقات قد ظهرت.

5. لكل ممر في القائمة ، استخدم خوارزمية A * للعثور على المسارات من بداية الممر إلى النهاية. بعد العثور على مسار واحد ، فإنه يغير حالة العالم حتى تتمكن الممرات المستقبلية دائمًا من تجاوز الممرات الحالية.

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


المستطيلات الزرقاء عبارة عن ممرات

فيما يلي بعض الأمثلة لخوارزمية تستخدم موارد رسومية حقيقية (الموارد والرمز لوضعها غير موجود في المستودع):

ثلاثة أبعاد

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

خوارزمية

يبلغ حجم الشبكة الآن 30 × 5 × 30.

1. كان التغيير الأول هو توليد غرف ثلاثية الأبعاد. هذا التغيير تافه.


يرجى ملاحظة أن الغرف يمكن أن تكون عدة طوابق.

2. ثم نجد تثليث Delaunay ثلاثي الأبعاد لهذه الغرف ، أو بالأحرى رباعي السطوح Delaunay. بعد البحث عن معلومات حول استفسارات "3D Delaunay triangulation" أو "Delaunay tetrahedralization" ، وجدت العديد من المقالات البحثية ، ولكن ليس مثالًا واحدًا على الكود.

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

في النهاية ، اضطررت إلى دراسة مبدأ خوارزمية Bower-Watson بنفسي لتغييره بنفسي. ما زلت لا أفهم حقًا سبب أهمية الدوائر المقيدة ، لكن على الأقل تمكنت من إعادة كتابة الخوارزمية مع المجالات الموصوفة باستخدام هذه الصفحة مع Wolfram MathWorld. نظرًا لأن هذه عمليات أساسًا باستخدام مصفوفات 4x4 ، فقد قمت بتعيين كل الأعمال المعقدة لنوع Matrix4x4 من Unity3D.

يوجد هذا الإصدار الجديد في Scripts3D/Delaunay3D.cs ، في حالة احتياج أي شخص إلى كود سهل الفهم برخصة MIT.


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

3 و 4. الحواف من المرحلة 2 مع تغييرات تافهة تماما يمكن أن تنتقل إلى خوارزمية Prim.


ممرات 3D-MST


تم إضافة ممرات ذات أضلاع متعددة مرة أخرى

5. تبدأ الصعوبات عند تنفيذها في خوارزمية 3D A *. الإصدار 2D بسيط للغاية ، إنه تطبيق قياسي لـ A *. لنقله إلى ثلاثي الأبعاد ، أحتاج إلى إضافة القدرة على خوارزمية البحث عن المسار للتنقل لأعلى ولأسفل وتوصيل الغرف في طوابق مختلفة. قررت أن أربط الطوابق ليس بالسلالم العمودية ، ولكن برحلات السلالم.

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


عرض الجانب. يمكنك إنشاء العقد على الجانبين ، ولكن ليس العقدة في الأعلى.

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


الدرج والمساحة الحرة فوقه

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



وهذا هو ، في النهاية ، يجب أن يبدو شكل الدرج مثل الصورة أدناه. يجب أن تضمن خوارزمية العثور على المسار وجود ممرات في مربعين أزرقين.


يبدأ الدرج بساحة زرقاء صلبة ويتحرك لأعلى في طابق واحد.

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

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

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

مطلوب السلوك الموصوف أعلاه فقط لعدد قليل من المسارات المحتملة داخل استدعاء دالة المسار نفسه. لتوليد جميع الممرات ، لا يزال هناك العديد من التحديات لإيجاد الطريق. التكرارات اللاحقة ستتجاوز ببساطة الدرج الموجود كما كان من قبل.

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

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

بصرف النظر عن ذلك ، سيكون التعقيد الكلي هو تقريبا O (N ^ 2) ، على الرغم من أنني لا أعرف كيفية تحليل هذا بشكل صحيح. هذا التعديل هو "عنق الزجاجة" الرئيسي لخوارزمية توليد الأبراج المحصنة.

بعد إجراء كل هذه التغييرات ، كانت النتيجة كما يلي:


المستطيلات الخضراء عبارة عن سلالم


يمكن أن تكون مسارات المولد بسيطة ...


... أو معقدة

إليك شكل زنزانة ثلاثية الأبعاد باستخدام موارد رسومات حقيقية:


زنزانة مع عدة طوابق


خوارزمية جيل الأبراج المحصنة قادرة على خلق سلوكيات طارئة مثيرة للاهتمام.


يشكّل درجان درجًا عريضًا


من الصعب شرح سلم العرض الثلاثي


يمكن أن يؤدي المسار الذي يسير إلى طابقين إلى إنشاء درجين مع منصة في المنتصف


عندما تمر عدة مسارات بجانب بعضها البعض ، يمكن أن تكون الممرات كبيرة جدًا


ينزل درجان إلى طابق واحد

استنتاج

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

لكن العمل كان يستحق كل هذا العناء. الأبراج المحصنة التي أنشأتها هذه الخوارزمية مثيرة للاهتمام ويمكن أن تصبح الأساس لمباراة جيدة.