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

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

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

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

حول خوارزمية إيلر

تم تقديم خوارزمية إيلر بواسطة ديفيد إيلر.

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

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

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

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

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

• قم بتعيين معرف مجموعة فريد لكل خلية في الصف.

الخطوة الثانية: ضم بعض الخلايا المتجاورة أفقيًا

• قم بدمج الخلايا المتجاورة عشوائياً عن طريق تعيين نفس معرّف المجموعة لها. هذا يضمن وجود ممرات أفقية.

الخطوة 3: إنشاء اتصالات رأسية بالصف التالي

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

الخطوة الرابعة: الانتقال إلى الصف التالي

• قم بنقل الاتصالات الرأسية عن طريق تعيين نفس معرف المجموعة للخلايا المقابلة أدناه.
• قم بتعيين معرّفات مجموعات جديدة لأي خلايا غير مُعيّنة.

الخطوة 5: كرر الخطوات من 2 إلى 4 حتى الوصول إلى الصف الأخير

• استمر في المعالجة صفًا تلو الآخر.

الخطوة 6: معالجة الصف الأخير

• تأكد من أن جميع الخلايا في الصف الأخير تنتمي إلى نفس المجموعة عن طريق دمج أي مجموعات منفصلة متبقية.

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

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

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