Wilsons algoritm labyrintgenerator

Wilsons algoritm är en slingaraderad slumpmässig vandringsmetod som genererar enhetliga spännande träd för att skapa labyrint. Detta innebär att alla möjliga labyrinter av en given storlek är lika sannolikt att genereras, vilket gör det till en opartisk labyrintgenereringsteknik. Wilsons algoritm kan betraktas som en förbättrad version av Aldous-Broder-algoritmen, eftersom den genererar labyrinter med identiska egenskaper, men den går mycket snabbare, så jag har inte brytt mig om att implementera Aldous-Broder-algoritmen här.

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 Wilsons algoritm

Wilsons algoritm för att generera enhetliga spännande träd med hjälp av en slinga raderad slumpmässig vägg skapades av David Bruce Wilson.

Wilson introducerade ursprungligen denna algoritm 1996 medan han undersökte slumpmässiga träd och Markov-kedjor i sannolikhetsteori. Även om hans arbete främst handlade om matematik och statistisk fysik, har algoritmen sedan dess antagits allmänt för generering av labyrint på grund av dess förmåga att producera perfekt enhetliga labyrinter.

Hur Wilsons algoritm fungerar för Maze Generation

Wilsons algoritm säkerställer att den slutliga labyrinten är helt ansluten utan några slingor genom att iterativt skära ut stigar från obesökta celler med hjälp av slumpmässiga promenader.

Steg 1: Initiera

• Börja med ett rutnät fyllt med väggar.
• Definiera en lista över alla möjliga passageceller.

Steg 2: Välj en slumpmässig startcell

• Välj valfri slumpmässig cell och markera den som besökt. Detta fungerar som startpunkten för labyrinten under generationen.

Steg 3: Random Walk med loopradering

• Välj en obesökt cell och påbörja en slumpmässig promenad (rör dig i slumpmässiga riktningar).
• Om promenaden når en redan besökt cell, radera alla slingor i banan.
• När vandringen ansluter till den besökta regionen, markera alla celler i vägen som besökta.

Steg 4: Upprepa tills alla celler har besökts :

• Fortsätt att välja obesökta celler och utföra slumpmässiga promenader tills varje cell är en del av labyrinten.