Kruskal's Algoritme Maze Generator

Kruskals algoritme er en minimum spanning tree-algoritme, der kan tilpasses til labyrintgenerering. Den er særligt effektiv 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 Prims.

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ørst algoritmen i 1956 i sin artikel "On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem".

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

Hvordan Kruskals algoritme fungerer til 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: Sortér vægge

• Bland eller sorter væggene tilfældigt. Hvis det implementeres som en ægte Kruskal-algoritme, skal væggene sorteres i en tilfældig rækkefølge (da labyrintgenerering ikke kræver vægte).

Trin 3: Bearbejd vægge

• Iterer gennem de blandede vægge.
• Hvis de to celler, der er delt af væggen, tilhører forskellige sæt (dvs. de er endnu ikke forbundet i labyrinten), skal du fjerne væggen og sammenlægge sætene.
• Hvis de allerede er i samme sæt, så spring væggen over (for at undgå cyklusser).

Trin 4: Fortsæt indtil færdiggørelse

• Gentag denne proces, indtil alle celler er forbundet og danner et enkelt spanning tree.
• Til sidst er hver celle forbundet med de andre uden løkker eller isolerede sektioner.

Da Kruskals algoritme er baseret på sammenflettede sæt, kan den optimeres ved hjælp af 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: Link

Yderligere læsning

Hvis du kunne lide dette indlæg, kan du måske også lide disse forslag:

• Jag og dræb labyrintgenerator
• Wilsons Algoritme Labyrintgenerator
• Rekursiv Backtracker Maze Generator