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 o singură cale între oricare două puncte) folosind o abordare rând cu rând. Produce labirinturi similare cu algoritmul lui Kruskal, dar face acest lucru prin generarea unui singur rând la un moment dat, 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 eficientă rând cu rând a generării labirintului, făcându-l ideal pentru labirinturi infinite sau generate în timp real. Este citat în mod obișnuit în literatura privind generarea de conținut procedural și generarea labirintului, dar nu am reușit să găsesc surse primare care să detalieze publicarea sa originală.

Cum funcționează algoritmul lui Eller pentru Maze Generation

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

Teoretic, poate fi folosit pentru a genera labirinturi infinite, cu toate acestea, pentru a vă asigura că labirintul generat este de fapt rezolvabil, este necesar să treceți la logica „rândului final” 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 de set.

Pasul 2: Uniți unele celule adiacente pe orizontală

• Îmbină aleatoriu celulele adiacente setându-le la același ID setat. Acest lucru asigură că există pasaje orizontale.

Pasul 3: Creați conexiuni verticale la 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 vă conecta la rândul următor.

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

• Continuați conexiunile verticale prin atribuirea aceluiași ID setat celulelor corespunzătoare de mai jos.
• Atribuiți ID-uri de set noi oricăror celule nealocate.

Pasul 5: Repetați pașii 2–4 până când se ajunge 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, îmbinând toate seturile separate rămase.