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

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

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

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

نبذة عن خوارزمية إيلر

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

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

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

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

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

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

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

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

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

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

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

الخطوة 4: الانتقال إلى الصف التالي

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

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

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

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

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