ما هي الخوارزمية الجيدة لإنشاء متاهة؟

https://stackoverflow.com/questions/38502

09-06-2019
|

سؤال

لنفترض أنك تريد متاهة بسيطة على شبكة N by M، بمسار واحد خلالها، وعدد لا بأس به من النهايات المسدودة، ولكن هذا يبدو "صحيحًا" (على سبيل المثال.كما لو أن شخصًا ما صنعها يدويًا دون الكثير من الطرق المسدودة الصغيرة وكل ذلك).هل هناك طريقة معروفة للقيام بذلك؟

المحلول

من http://www.astrolog.org/labyrnth/algrithm.htm

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

إنهم ينتجون 10٪ فقط من الطرق المسدودة

هو مثال على المتاهة التي تم إنشاؤها بهذه الطريقة.

نصائح أخرى

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

لمزيد من المعلومات، تحقق من مزليب على GitHub، مكتبة Python التي تنفذ جميع خوارزميات إنشاء/حل المتاهة القياسية.

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

أفضل مناقشة على الإطلاق حول خوارزميات توليد المتاهة: http://www.jamisbuck.org/presentations/rubyconf2011/index.html (كان على HN قبل يومين).

ومن الغريب أنه من خلال تغيير القواعد "المعتمدة" قليلاً والبدء من تكوين عشوائي، لعبة كونواي للحياة يبدو أنها تولد متاهات جميلة!

(لا أتذكر القاعدة بالضبط، لكنه تعديل بسيط للغاية يميل إلى "تكثيف" عدد الخلايا...)

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

من خلال تغيير الأوزان لأنواع الحواف المختلفة، يمكنك إنشاء متاهات تحتوي على الكثير من الخصائص المميزة أو "الشخصيات".انظر المثال الخاص بي هنا:

https://mtimmerm.github.io/webStuff/maze.html

إحدى طرق إنشاء المتاهة هي النسخة العشوائية من خوارزمية بريم.

ابدأ بشبكة مليئة بالجدران.اختر خلية، ضع علامة عليها كجزء من المتاهة.أضف جدران الخلية إلى قائمة الجدران.بينما توجد جدران في القائمة:

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

(ط) اجعل الجدار ممرًا وحدد الخلية الموجودة على الجانب الآخر كجزء من المتاهة.

(2) أضف جدران الخلية المجاورة إلى قائمة الجدران.

إذا كانت الخلية الموجودة على الجانب الآخر موجودة بالفعل في المتاهة، فقم بإزالة الجدار من القائمة.

لمزيد من الفهم انقر هنا

إليك خوارزمية DFS مكتوبة كرمز زائف:

قم بإنشاء CellStack (LIFO) للاحتفاظ بقائمة بمواقع الخلايا
تعيين TotalCells = عدد الخلايا في الشبكة
اختر خلية بشكل عشوائي وأطلق عليها اسم CurrentCell
تعيين الخلايا التي تمت زيارتها = 1

في حين أن زيارته <TotalCells يجدون جميع جيران CurrentCell مع جميع الجدران سليمة
إذا تم العثور على واحد أو أكثر ، فاختر واحدة بشكل عشوائي
هدم الجدار بينه وبين CurrentCell
ادفع موقع CurrentCell على CellStack
إنشاء الخلية الجديدة CurrentCell
أضف 1 إلى زيارة أخرى تطفو على أحدث دخول الخلية قبالة cellstack
اجعله currentcell endif endh endhile

مرخصة بموجب: CC-BY-SA مع الإسناد

لا تنتمي إلى StackOverflow