Kruskal's Algoritme Maze Generator

Kruskals algoritme er en minimumspændende træ-algoritme, der kan tilpasses til generering af labyrint. Det er særligt effektivt til at skabe perfekte labyrinter. Et alternativ til Kruskals algoritme er Prims algoritme, som også er en minimum spanning tree algoritme, men da de genererer identiske labyrinter og Kruskals kører hurtigere, har jeg ikke gidet at implementere Prim's.

En perfekt labyrint er en labyrint, hvor der er præcis én vej fra et hvilket som helst punkt i labyrinten til et hvilket som helst andet punkt. Det betyder, at du ikke kan ende med at gå rundt i cirkler, men du vil ofte støde på blindgyder, som tvinger dig til at vende om og gå tilbage.

De labyrintkort, der genereres her, indeholder en standardversion uden start- og slutpositioner, så du selv kan bestemme dem: der vil være en løsning fra ethvert punkt i labyrinten til ethvert andet punkt. Hvis du vil have inspiration, kan du aktivere en foreslået start- og slutposition - og endda se løsningen mellem de to.

Om Kruskals algoritme

Kruskals algoritme blev skabt af Joseph Bernard Kruskal, Jr., en amerikansk matematiker, statistiker og datalog. Han beskrev første gang algoritmen i 1956 i sit papir "On the Shortest Spanning Subtree of a Graph and the Travelling Salesman Problem."

Algoritmen er designet til at finde det minimale spændingstræ (MST) i en graf, hvilket sikrer, at alle hjørner er forbundet med den minimale mulige samlede kantvægt, samtidig med at cyklusser undgås.

Hvordan Kruskals algoritme virker for labyrintgenerering

Trin 1: Initialiser

• Behandl hver celle i labyrinten som et separat sæt (en unik komponent).
• Angiv alle væggene mellem tilstødende celler som potentielle kanter.

Trin 2: Sorter vægge

• Bland eller bestil væggene tilfældigt. Hvis du implementerer det som en ægte Kruskals algoritme, skal du sortere vægge i en tilfældig rækkefølge (da labyrintgenerering ikke kræver vægte).

Trin 3: Procesvægge

• Gentag gennem de blandede vægge.
• Hvis de to celler divideret med væggen tilhører forskellige sæt (dvs. de er endnu ikke forbundet i labyrinten), fjern væggen og flet sættene sammen.
• Hvis de allerede er i det samme sæt, skal du springe væggen over (for at undgå cyklusser).

Trin 4: Fortsæt indtil afslutning

• Gentag denne proces, indtil alle celler er forbundet og danner et enkelt spændingstræ.
• Til sidst er hver celle forbundet med de andre uden sløjfer eller isolerede sektioner.

Da Kruskals algoritme er afhængig af sammenlægningssæt, kan den optimeres ved at bruge Union-Find-algoritmen, som giver en effektiv måde at spore forbundne celler under labyrintgenerering. Du kan se min PHP-implementering af Union-Find-algoritmen her: Disjoint sæt (Union-Find Algorithm) i PHP