Kruskals algoritme-labyrint-generator

Kruskals algoritme er en minimumspennende trealgoritme 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 span tree-algoritme, men siden de genererer identiske labyrinter og Kruskals kjører raskere, har jeg ikke brydd meg med å implementere Prim sine.

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

Algoritmen er utformet for å finne minimum spenntreet (MST) i en graf, og sikre at alle toppunkter er koblet med minimal mulig total kantvekt samtidig som man unngår sykluser.

Hvordan Kruskals algoritme fungerer for labyrintgenerering

Trinn 1: Initialiser

• Behandle hver celle i labyrinten som et separat 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 den som en ekte Kruskals algoritme, sorter veggene i en tilfeldig rekkefølge (siden labyrintgenerering ikke krever vekter).

Trinn 3: Prosessvegger

• Iterer gjennom de stokkede 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åingssett, kan den optimaliseres ved å bruke Union-Find-algoritmen, som gir en effektiv måte å spore tilkoblede celler under generering av labyrint. Du kan se min PHP-implementering av Union-Find-algoritmen her: Disjoint Set (Union-Find Algorithm) i PHP