مولد متاهة الصيد والقتل

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

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

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

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

حول خوارزمية الصيد والقتل

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

كيف تعمل خوارزمية البحث والقتل لإنشاء المتاهة

الخطوة 1: ابدأ بخلية عشوائية

• ابحث عن خلية عشوائية في الشبكة وقم بوضع علامة عليها كخلية تمت زيارتها.

الخطوة الثانية: مرحلة المشي (المشي العشوائي)

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

الخطوة 3: مرحلة الصيد (العودة عبر المسح)

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