Miklix

Generatorul de labirint al algoritmului lui Eller

Publicat: 16 februarie 2025 la 20:02:03 UTC

Generator de labirint folosind algoritmul lui Eller pentru a crea un labirint perfect. Acest algoritm este interesant deoarece necesită doar păstrarea rândului curent (nu a întregului labirint) în memorie, așa că poate fi folosit pentru a crea labirinturi foarte, foarte mari chiar și pe sisteme foarte limitate.

Această pagină a fost tradusă automat din limba engleză pentru a o face accesibilă cât mai multor persoane. Din păcate, traducerea automată nu este încă o tehnologie perfecționată, astfel încât pot apărea erori. Dacă preferați, puteți vizualiza versiunea originală în limba engleză aici:

Eller's Algorithm Maze Generator

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ă.


Generați un labirint nou








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.

Distribuie pe BlueskyDistribuie pe FacebookDistribuie pe LinkedInDistribuie pe TumblrDistribuie pe XDistribuie pe LinkedInPin pe Pinterest

Mikkel Bang Christensen

Despre autor

Mikkel Bang Christensen
Mikkel este creatorul și proprietarul miklix.com. El are peste 20 de ani de experiență ca programator de calculatoare/dezvoltator software profesionist și este în prezent angajat cu normă întreagă pentru o mare corporație europeană de IT. Atunci când nu scrie pe blog, își petrece timpul liber cu o gamă largă de interese, hobby-uri și activități, care se pot reflecta într-o anumită măsură în varietatea de subiecte abordate pe acest site.