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

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

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

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

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

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

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

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

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

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

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

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

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

الخطوة 3: المشي العشوائي مع المسح الدائري

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

الخطوة 4: كرر حتى تتم زيارة كافة الخلايا :

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