مولد متاهة التتبع التكراري

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

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

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

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

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

كيف يعمل

تعتمد الخوارزمية على أسلوب البحث العميق أولاً باستخدام بنية مكدسة. إليك شرحاً مفصلاً للخطوات:

1. اختر خلية بداية وقم بتحديدها على أنها تمت زيارتها.
2. طالما توجد خلايا لم تتم زيارتها: انظر إلى الخلايا المجاورة التي لم تتم زيارتها بعد. إذا وُجد جار واحد على الأقل لم تتم زيارته: اختر عشوائيًا أحد الجيران الذين لم تتم زيارتهم. أزل الجدار بين الخلية الحالية والجار المختار. انتقل إلى الجار المختار وقم بتمييزه على أنه تمت زيارته. ادفع الخلية الحالية إلى المكدس. إذا لم تكن هناك جيران لم تتم زيارتهم: تراجع عن طريق إزالة الخلية الأخيرة من المكدس.
3. استمر في هذه العملية حتى تصبح المجموعة فارغة.

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

لديّ في الواقع نسختان من هذه الخوارزمية قيد الاستخدام على هذا الموقع: نسخة تعتمد على قائمة انتظار LIFO لإنشاء المتاهات في هذه الصفحة، ونسخة أخرى تعتمد على الاستدعاء الذاتي لحل المتاهات، بما في ذلك المتاهات التي تولدها خوارزميات أخرى (وهكذا تُنشأ الخرائط التي تحتوي على الحلول). وجود نسختين مختلفتين هو مجرد تسلية لأنني مهووس بالتكنولوجيا وأجدها مثيرة للاهتمام، وكان من الممكن استخدام أيٍّ منهما لكلا الغرضين ;-)

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

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

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