Eller algoritmus labirintusgenerátora

Az Eller-féle algoritmus egy labirintusgeneráló algoritmus, amely soronkénti megközelítéssel hatékonyan állít elő tökéletes labirintusokat (hurok nélküli útvesztőket és egyetlen útvonalat bármely két pont között). A Kruskal-algoritmushoz hasonló labirintusokat hoz létre, de ezt úgy teszi, hogy egyszerre csak egy sort generál anélkül, hogy a teljes labirintust a memóriában kellene tárolnia. Ez hasznossá teszi nagyon nagy labirintusok létrehozását nagyon korlátozott rendszereken és eljárási tartalom létrehozásához.

A tökéletes labirintus olyan labirintus, amelyben a labirintus bármely pontjából pontosan egy út vezet bármely más pontba. Ez azt jelenti, hogy a végén nem járhatsz körbe-körbe, de gyakran fogsz zsákutcába jutni, ami arra kényszerít, hogy megfordulj és visszamenj.

Az itt generált labirintustérképek tartalmaznak egy alapértelmezett verziót kezdő és végpontok nélkül, így ezeket te magad döntheted el: a labirintus bármely pontjából bármelyik másik pontba el lehet jutni. Ha inspirációra vágysz, engedélyezhetsz egy javasolt kezdő- és célpozíciót - és még a kettő közötti megoldást is láthatod.

Az Eller-algoritmusról

Eller algoritmusát David Eller vezette be.

Az algoritmus figyelemre méltó a labirintusgenerálás hatékony, soronkénti megközelítéséről, ami ideálissá teszi a végtelen számú labirintushoz vagy a valós időben generált labirintusokhoz. A procedurális tartalomgenerálás és a labirintusgenerálási szakirodalom gyakran idézi, de nem találtam olyan elsődleges forrást, amely részletezné az eredeti megjelenését.

Hogyan működik az Eller-algoritmus a labirintusgeneráláshoz

Az Eller-algoritmus egyszerre egy sort dolgoz fel, fenntartva és módosítva az összekapcsolt cellák halmazait. Biztosítja a kapcsolatot, miközben elkerüli a hurkokat, és hatékonyan kiterjeszti a labirintust lefelé.

Elméletileg használható végtelen labirintus generálására, azonban annak érdekében, hogy a létrehozott labirintus valóban megoldható legyen, valamikor át kell váltani az "utolsó sor" logikára, hogy befejezze a labirintust.

1. lépés: Inicializálja az első sort

• Rendeljen a sor minden cellájához egyedi készletazonosítót.

2. lépés: Csatlakoztasson néhány szomszédos cellát vízszintesen

• Véletlenszerűen egyesítse a szomszédos cellákat, ha ugyanazt a beállított azonosítót állítja be. Ez biztosítja, hogy legyenek vízszintes járatok.

3. lépés: Hozzon létre függőleges kapcsolatokat a következő sorhoz

• A sorban megjelenő minden készlethez legalább egy cellának lefelé kell csatlakoznia (a kapcsolat biztosítása érdekében).
• Véletlenszerűen válasszon ki egy vagy több cellát mindegyik halmazból a következő sorhoz való csatlakozáshoz.

4. lépés: Lépjen a következő sorra

• Vigye tovább a függőleges kapcsolatokat úgy, hogy ugyanazt a készletazonosítót rendeli hozzá az alábbi megfelelő cellákhoz.
• Rendeljen új készletazonosítókat a hozzá nem rendelt cellákhoz.

5. lépés: Ismételje meg a 2–4. lépéseket, amíg el nem éri az utolsó sort

• Folytassa a feldolgozást soronként.

6. lépés: Az utolsó sor feldolgozása

• Győződjön meg arról, hogy az utolsó sorban lévő összes cella ugyanahhoz a halmazhoz tartozik a fennmaradó különálló készletek összevonásával.