Generatorul de labirint al algoritmului lui Kruskal

Algoritmul lui Kruskal este un algoritm de arbore de întindere minim care poate fi adaptat pentru generarea labirintului. Este deosebit de eficient pentru a crea labirinturi perfecte. O alternativă la algoritmul lui Kruskal este algoritmul lui Prim, care este, de asemenea, un algoritm de arbore de întindere minim, dar din moment ce generează labirinturi identice și ale lui Kruskal rulează mai repede, nu m-am deranjat să-l implementez pe 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 pentru prima dată algoritmul în 1956 în lucrarea sa „On the Shortest Spanning Subtree of a Graph and the Travelling Salesman Problem”.

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

Cum funcționează algoritmul lui Kruskal pentru generarea labirintului

Pasul 1: Inițializați

• Tratați fiecare celulă din labirint ca pe un set separat (o componentă unică).
• Listați toți pereții dintre celulele adiacente ca margini potențiale.

Pasul 2: Sortați pereții

• Amestecă sau ordonă aleatoriu pereții. Dacă îl implementați ca un algoritm adevărat al lui Kruskal, sortați pereții într-o ordine aleatorie (deoarece generarea labirintului nu necesită greutăți).

Pasul 3: Procesați pereții

• Iterați prin pereții amestecați.
• Dacă cele două celule împărțite de perete aparțin unor seturi diferite (adică nu sunt încă conectate în labirint), îndepărtați peretele și îmbinați seturile.
• Dacă sunt deja în același set, sări 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 care se întinde.
• La sfârșit, fiecare celulă este conectată la celelalte fără bucle sau secțiuni izolate.

Deoarece algoritmul lui Kruskal se bazează pe îmbinarea seturilor, acesta poate fi optimizat prin utilizarea algoritmului 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: Set disjunc (Algoritmul Union-Find) în PHP