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

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

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

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

حول خوارزمية ويلسون

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

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

كيف تعمل خوارزمية ويلسون في توليد المتاهات

تضمن خوارزمية ويلسون أن تكون المتاهة النهائية متصلة بالكامل دون أي حلقات عن طريق نحت المسارات بشكل متكرر من الخلايا غير المزارة باستخدام المشي العشوائي.

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

• ابدأ بشبكة مليئة بالجدران.
• حدد قائمة بجميع خلايا المرور الممكنة.

الخطوة الثانية: اختر خلية بداية عشوائية

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

الخطوة 3: المشي العشوائي مع مسح الحلقات

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

الخطوة الرابعة: كرر العملية حتى يتم زيارة جميع الخلايا:

• استمر في اختيار الخلايا التي لم تتم زيارتها وإجراء عمليات المشي العشوائي حتى تصبح كل خلية جزءًا من المتاهة.

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

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

• مولد المتاهة لخوارزمية إلير
• مولد متاهة خوارزمية نمو الأشجار
• مولد متاهة التتبع التكراري