Kruskals algoritm labyrintgenerator

Kruskals algoritm är en minimum spanning tree-algoritm som kan anpassas för labyrintgenerering. Den är särskilt effektiv för att skapa perfekta labyrinter. Ett alternativ till Kruskals algoritm är Prims algoritm, som också är en minimum spanning tree-algoritm, men eftersom de genererar identiska labyrinter och Kruskals algoritm 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 Traveling Salesman Problem".

Algoritmen är utformad för att hitta det minsta omspännande trädet (MST) för en graf, vilket säkerställer att alla noder är sammankopplade med minsta möjliga totala kantvikt samtidigt som cykler undviks.

Hur Kruskals algoritm fungerar för labyrintgenerering

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 ordna väggarna. Om det implementeras som en sann Kruskals algoritm, sortera väggarna i slumpmässig ordning (eftersom labyrintgenerering inte kräver vikter).

Steg 3: Bearbeta väggar

• Iterera genom de blandade väggarna.
• Om de två cellerna som delas av väggen tillhör olika mängder (dvs. de är ännu inte sammankopplade i labyrinten), ta bort väggen och sammanfoga mängderna.
• Om de redan är i samma set, hoppa över väggen (för att undvika cykler).

Steg 4: Fortsätt tills det är klart

• Upprepa denna process tills alla celler är sammankopplade och bildar ett enda spanning tree.
• Slutet är varje cell ansluten till de andra utan loopar eller isolerade sektioner.

Eftersom Kruskals algoritm bygger på sammanslagning av mängder kan den optimeras med hjälp av Union-Find-algoritmen, vilket ger ett effektivt sätt att spåra sammankopplade celler under labyrintgenerering. Du kan se min PHP-implementering av Union-Find-algoritmen här: Länk

Vidare läsning

Om du gillade det här inlägget kanske du också gillar dessa förslag:

• Wilsons algoritm labyrintgenerator
• Växande trädalgoritm labyrintgenerator
• Ellers algoritm labyrintgenerator