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

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

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

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

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

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

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

كيف تعمل خوارزمية الصيد والقتل في توليد المتاهات

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

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

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

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

الخطوة 3: مرحلة البحث (التراجع عبر المسح الضوئي)

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

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

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

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