مولد متاهة خوارزمية نمو الأشجار

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

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

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

حول خوارزمية زراعة الأشجار

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

كيف تعمل خوارزمية نمو الشجرة

الخطوة 1: التهيئة

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

الخطوة 2: حلقة إنشاء المتاهة

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

الخطوة 3: الإنهاء

• تنتهي الخوارزمية عندما لا يبقى أي خلايا أخرى في القائمة، مما يعني أنه تم نحت المتاهة بأكملها.

استراتيجيات اختيار الخلايا (مرونة الخوارزمية)

الميزة المميزة لخوارزمية الشجرة النامية هي كيفية اختيار الخلية التي سيتم معالجتها بعد ذلك. يؤثر هذا الاختيار بشكل كبير على مظهر المتاهة:

الخلية الأحدث (سلوك يشبه المكدس) – المتعقب الخلفي المتكرر:

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

الخلية العشوائية (خوارزمية عشوائية بدائية):

• اختر خلية عشوائية من القائمة في كل مرة.
• إنشاء متاهة موزعة بشكل أكثر توازناً مع مسارات معقدة ومتشابكة.
• عدد أقل من الممرات الطويلة وتفرعات أكثر.

الخلية الأقدم (سلوك يشبه قائمة الانتظار):

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

النهج الهجين:

دمج الاستراتيجيات لخصائص المتاهة المتنوعة. على سبيل المثال:

• 90% أحدث، 10% عشوائي: يبدو في الغالب مثل متاهة متتبع خلفي متكررة، ولكن مع فروع عرضية تقطع الممرات الطويلة.
• 50% أحدث، 50% أقدم: يوازن بين الممرات الطويلة والنمو الكثيف.