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

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

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

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

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

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

كيف يعمل؟

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

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

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

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