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

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

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

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

حول خوارزمية الشجرة المتنامية

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

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

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

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

الخطوة الثانية: حلقة توليد المتاهة

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

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

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

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

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

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

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

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

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

أقدم خلية (سلوك يشبه الطابور):

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

الأساليب الهجينة:

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

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

قراءات إضافية

إذا أعجبك هذا المنشور، فقد تعجبك أيضًا هذه الاقتراحات:

• مولد متاهة خوارزمية ويلسون
• مولد متاهة خوارزمية كروسكال
• مولد المتاهة لخوارزمية إلير