Eller algoritmus labirintusgenerátora

Eller algoritmusa egy labirintusgeneráló algoritmus, amely hatékonyan hoz létre tökéletes labirintusokat (hurkok nélküli labirintusokat, amelyek között bármely két pont egyetlen útvonallal rendelkezik) soronkénti megközelítéssel. Kruskal algoritmusához 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árolni. Ez hasznossá teszi nagyon nagy labirintusok létrehozására nagyon korlátozott rendszereken, valamint procedurális tartalomgenerálásra.

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.

Eller algoritmusáról

Eller algoritmusát David Eller vezette be.

Az algoritmus figyelemre méltó a hatékony, soronkénti labirintusgenerálási megközelítéséről, így ideális végtelen labirintusokhoz vagy valós időben generált labirintusokhoz. Gyakran hivatkoznak rá a procedurális tartalomgenerálási és labirintusgenerálási szakirodalomban, de nem találtam olyan elsődleges forrásokat, amelyek részleteznék az eredeti publikációját.

Hogyan működik Eller algoritmusa a labirintusgenerálásban?

Eller algoritmusa egyszerre egy sort dolgoz fel, miközben karbantartja és módosítja az összekapcsolt cellák halmazait. Biztosítja az összekapcsolhatóságot a hurkok elkerülése mellett, és hatékonyan kiterjeszti a labirintust lefelé.

Elméletileg végtelen labirintusok generálására használható, azonban ahhoz, hogy a létrehozott labirintus valóban megoldható legyen, valamikor át kell kapcsolni az „utolsó sor” logikára a labirintus befejezéséhez.

1. lépés: Az első sor inicializálása

• Rendeljen a sor minden cellájához egyedi halmazazonosítót.

2. lépés: Néhány szomszédos cella vízszintes összekapcsolása

• Véletlenszerűen egyesítse a szomszédos cellákat úgy, hogy azonos halmazazonosítót adjon nekik. Ez biztosítja a vízszintes átjárók létrehozását.

3. lépés: Függőleges kapcsolatok létrehozása a következő sorhoz

• A sorban megjelenő minden egyes halmazhoz legalább egy cellának lefelé kell csatlakoznia (az összekapcsolhatóság biztosítása érdekében).
• Véletlenszerűen válassz ki egy vagy több cellát minden készletből, hogy csatlakozz a következő sorhoz.

4. lépés: Ugrás a következő sorra

• Vigye át a függőleges kapcsolatokat úgy, hogy ugyanazt a halmazazonosítót rendeli hozzá a megfelelő cellákhoz az alatta.
• Rendeljen új halmazazonosítókat a nem hozzá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 sorról sorra.

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ó halmazok egyesítésével.

További olvasmányok

Ha tetszett ez a bejegyzés, akkor ezek a javaslatok is érdekelhetik:

• Wilson algoritmus labirintus generátor
• Rekurzív Backtracker labirintus generátor
• Kruskal algoritmus labirintus generátora