Kruskals algoritme-labyrint-generator

Kruskals algoritme er en algoritme med minimalt spenn som kan tilpasses for labyrintgenerering. Det er spesielt effektivt for å lage perfekte labyrinter. Et alternativ til Kruskals algoritme er Prims algoritme, som også er en minimum spanning tree-algoritme, men siden de genererer identiske labyrinter og Kruskals løp raskere, har jeg ikke brydd meg med å implementere Prims.

En perfekt labyrint er en labyrint der det finnes nøyaktig én vei fra et hvilket som helst punkt i labyrinten til et hvilket som helst annet punkt. Det betyr at du ikke kan ende opp med å gå i sirkler, men at du ofte vil støte på blindveier som tvinger deg til å snu og gå tilbake.

Labyrintkartene som genereres her, inneholder en standardversjon uten start- og målposisjoner, slik at du selv kan bestemme disse: Det vil finnes en løsning fra et hvilket som helst punkt i labyrinten til et hvilket som helst annet punkt. Hvis du vil ha inspirasjon, kan du aktivere en foreslått start- og målposisjon - og til og med se løsningen mellom de to.

Om Kruskals algoritme

Kruskals algoritme ble laget av Joseph Bernard Kruskal, Jr., en amerikansk matematiker, statistiker og informatiker. Han beskrev algoritmen første gang i 1956 i sin artikkel "On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem."

Algoritmen er designet for å finne det minste spenntreet (MST) til en graf, og sikrer at alle hjørner er forbundet med den minimale mulige totale kantvekten samtidig som sykluser unngås.

Hvordan Kruskals algoritme fungerer for labyrintgenerering

Trinn 1: Initialiser

• Behandle hver celle i labyrinten som et eget sett (en unik komponent).
• List opp alle veggene mellom tilstøtende celler som potensielle kanter.

Trinn 2: Sorter vegger

• Bland eller bestill veggene tilfeldig. Hvis du implementerer det som en ekte Kruskals algoritme, sorter vegger i en tilfeldig rekkefølge (siden labyrintgenerering ikke krever vekter).

Trinn 3: Behandle vegger

• Iterer gjennom de blandede veggene.
• Hvis de to cellene delt av veggen tilhører forskjellige sett (dvs. de er ennå ikke koblet sammen i labyrinten), fjern veggen og slå sammen settene.
• Hvis de allerede er i samme sett, hopp over veggen (for å unngå sykluser).

Trinn 4: Fortsett til ferdigstillelse

• Gjenta denne prosessen til alle cellene er koblet sammen, og danner et enkelt spenntre.
• På slutten er hver celle koblet til de andre uten løkker eller isolerte seksjoner.

Siden Kruskals algoritme er avhengig av sammenslåing av sett, kan den optimaliseres ved å bruke Union-Find-algoritmen, som gir en effektiv måte å spore tilkoblede celler under labyrintgenerering. Du kan se min PHP-implementering av Union-Find-algoritmen her: Disjoint Set (Union-Find Algorithm) i PHP

Videre lesing

Hvis du likte dette innlegget, kan du også like disse forslagene:

• Rekursiv Backtracker Maze Generator
• Jakt og Drep Labyrint Generator
• Ellers algoritme-labyrintgenerator