Generatorul de labirint al algoritmului lui Kruskal

Algoritmul lui Kruskal este un algoritm de tip arbore minim de acoperire care poate fi adaptat pentru generarea de labirinturi. Este deosebit de eficient pentru crearea de labirinturi perfecte. O alternativă la algoritmul lui Kruskal este algoritmul lui Prim, care este, de asemenea, un algoritm de tip arbore minim de acoperire, dar, deoarece generează labirinturi identice, iar algoritmul lui Kruskal rulează mai rapid, nu m-am obosit să implementez algoritmul lui Prim.

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 Kruskal

Algoritmul lui Kruskal a fost creat de Joseph Bernard Kruskal, Jr., un matematician, statistician și informatician american. El a descris algoritmul pentru prima dată în 1956 în lucrarea sa „Despre subarborele cu cea mai scurtă întindere a unui graf și problema comisarului ambulant”.

Algoritmul este conceput pentru a găsi arborele de acoperire minimă (MST) al unui graf, asigurându-se că toate vârfurile sunt conectate cu ponderea totală minimă posibilă a muchiilor, evitând în același timp ciclurile.

Cum funcționează algoritmul lui Kruskal pentru generarea labirintului

Pasul 1: Inițializare

• Tratați fiecare celulă din labirint ca un set separat (o componentă unică).
• Enumerați toți pereții dintre celulele adiacente ca posibile muchii.

Pasul 2: Sortează pereții

• Amestecați sau ordonați aleatoriu pereții. Dacă implementați algoritmul Kruskal, sortați pereții în ordine aleatorie (deoarece generarea labirinturilor nu necesită ponderi).

Pasul 3: Prelucrarea pereților

• Iterează prin pereții amestecați.
• Dacă cele două celule separate de perete aparțin unor mulțimi diferite (adică nu sunt încă conectate în labirint), îndepărtați peretele și uniți mulțimile.
• Dacă sunt deja în același set, săriți peste perete (pentru a evita ciclurile).

Pasul 4: Continuați până la finalizare

• Repetați acest proces până când toate celulele sunt conectate, formând un singur arbore de acoperire.
• La final, fiecare celulă este conectată la celelalte fără bucle sau secțiuni izolate.

Întrucât algoritmul lui Kruskal se bazează pe fuzionarea seturilor, acesta poate fi optimizat utilizând algoritmul Union-Find, care oferă o modalitate eficientă de a urmări celulele conectate în timpul generării labirintului. Puteți vedea implementarea mea PHP a algoritmului Union-Find aici: Link

Lectură suplimentară

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

• Generatorul de labirint al algoritmului lui Wilson
• Generator de labirint al algoritmului de creștere a arborilor
• Generatorul de labirint de vânătoare și ucidere