Kruskals algoritm labyrintgenerator

Kruskals algoritm är en minimumspännande trädalgoritm som kan anpassas för labyrintgenerering. Det är särskilt effektivt för att skapa perfekta labyrinter. Ett alternativ till Kruskals algoritm är Prims algoritm, som också är en minimal spaning tree-algoritm, men eftersom de genererar identiska labyrinter och Kruskals går snabbare har jag inte brytt mig om att implementera Prims.

En perfekt labyrint är en labyrint där det finns exakt en väg från varje punkt i labyrinten till varje annan punkt. Det betyder att du inte kan gå runt i cirklar, men du kommer ofta att stöta på återvändsgränder, vilket tvingar dig att vända om och gå tillbaka.

De labyrintkartor som genereras här innehåller en standardversion utan några start- och målpositioner, så att du själv kan bestämma dem: det kommer att finnas en lösning från vilken punkt som helst i labyrinten till vilken annan punkt som helst. Om du vill ha inspiration kan du aktivera en föreslagen start- och målposition - och till och med se lösningen mellan de två.

Om Kruskals algoritm

Kruskals algoritm skapades av Joseph Bernard Kruskal, Jr., en amerikansk matematiker, statistiker och datavetare. Han beskrev algoritmen först 1956 i sin artikel "On the Shortest Spanning Subtree of a Graph and the Travelling Salesman Problem."

Algoritmen är utformad för att hitta det minsta överspänningsträdet (MST) i en graf, vilket säkerställer att alla hörn är sammankopplade med den minimala möjliga totala kantvikten samtidigt som man undviker cykler.

Hur Kruskals algoritm fungerar för Maze Generation

Steg 1: Initiera

• Behandla varje cell i labyrinten som en separat uppsättning (en unik komponent).
• Lista alla väggar mellan intilliggande celler som potentiella kanter.

Steg 2: Sortera väggar

• Blanda eller slumpmässigt beställ väggarna. Om du implementerar det som en äkta Kruskals algoritm, sortera väggar i slumpmässig ordning (eftersom labyrintgenerering inte kräver vikter).

Steg 3: Processväggar

• Iterera genom de blandade väggarna.
• Om de två cellerna som delas av väggen tillhör olika uppsättningar (dvs. de är ännu inte anslutna i labyrinten), ta bort väggen och slå samman uppsättningarna.
• Om de redan är i samma uppsättning, hoppa över väggen (för att undvika cykler).

Steg 4: Fortsätt tills det är klart

• Upprepa denna process tills alla celler är anslutna och bildar ett enda spännträd.
• I slutet är varje cell ansluten till de andra utan slingor eller isolerade sektioner.

Eftersom Kruskals algoritm är beroende av sammanslagna uppsättningar, kan den optimeras genom att använda Union-Find-algoritmen, som ger ett effektivt sätt att spåra anslutna celler under labyrintgenerering. Du kan se min PHP-implementering av Union-Find-algoritmen här: Disjoint Set (Union-Find Algorithm) i PHP