Generatorul de labirint al algoritmului lui Eller

Algoritmul lui Eller este un algoritm de generare a labirintului care produce eficient labirinturi perfecte (labirinturi fără bucle și cu o singură cale între oricare două puncte) folosind o abordare rând cu rând. Acesta produce labirinturi similare algoritmului lui Kruskal, dar o face prin generarea unui singur rând pe rând, fără a fi nevoie de stocarea întregului labirint în memorie. Acest lucru îl face util pentru generarea de labirinturi foarte mari pe sisteme foarte limitate și pentru generarea de conținut procedural.

Un labirint perfect este un labirint în care există exact o singură cale de la orice punct din labirint la orice alt punct. Aceasta înseamnă că nu puteți ajunge să vă învârtiți în cerc, dar veți întâlni adesea fundături, forțându-vă să vă întoarceți.

Hărțile labirintului generate aici includ o versiune implicită fără poziții de început și de sfârșit, astfel încât să le puteți decide singuri: va exista o soluție din orice punct al labirintului către orice alt punct. Dacă doriți să vă inspirați, puteți activa o poziție de început și de sfârșit sugerată - și chiar să vedeți soluția între cele două.

Despre algoritmul lui Eller

Algoritmul lui Eller a fost introdus de David Eller.

Algoritmul este remarcabil pentru abordarea sa eficientă, rând cu rând, în ceea ce privește generarea de labirinturi, ceea ce îl face ideal pentru labirinturi infinite sau labirinturi generate în timp real. Este frecvent citat în literatura de specialitate despre generarea de conținut procedural și generarea de labirinturi, dar nu am reușit să găsesc surse primare care să detalieze publicarea sa originală.

Cum funcționează algoritmul lui Eller pentru generarea labirintului

Algoritmul lui Eller procesează câte un rând pe rând, menținând și modificând seturi de celule conectate. Acesta asigură conectivitatea evitând buclele și extinde eficient labirintul în jos.

Teoretic, poate fi folosit pentru a genera labirinturi infinite, însă pentru a se asigura că labirintul generat este de fapt rezolvabil, este necesar să se treacă la logica „ultimului rând” la un moment dat pentru a termina labirintul.

Pasul 1: Inițializați primul rând

• Atribuiți fiecărei celule din rând un ID unic al setului.

Pasul 2: Uniți orizontal câteva celule adiacente

• Îmbinați aleatoriu celulele adiacente setând același ID. Acest lucru asigură existența unor pasaje orizontale.

Pasul 3: Creați conexiuni verticale cu rândul următor

• Pentru fiecare set care apare pe rând, cel puțin o celulă trebuie să se conecteze în jos (pentru a asigura conectivitatea).
• Alegeți aleatoriu una sau mai multe celule din fiecare set pentru a le conecta la rândul următor.

Pasul 4: Treceți la rândul următor

• Continuați conexiunile verticale atribuind același ID de set celulelor corespunzătoare de mai jos.
• Atribuiți ID-uri de set noi oricăror celule neatribuite.

Pasul 5: Repetați pașii 2-4 până când ajungeți la ultimul rând

• Continuați procesarea rând cu rând.

Pasul 6: Procesați ultimul rând

• Asigurați-vă că toate celulele din ultimul rând aparțin aceluiași set prin combinarea oricăror seturi separate rămase.

Lectură suplimentară

Dacă ți-a plăcut această postare, s-ar putea să-ți placă și aceste sugestii:

• Generatorul de labirint al algoritmului lui Kruskal
• Generator de labirint al algoritmului de creștere a arborilor
• Recursive Backtracker Maze Generator