Wilsons algoritm labyrintgenerator

Wilsons algoritm är en loop-eraserad slumpmässig gångmetod som genererar enhetliga spänningsträd för labyrintskapande. Detta innebär att alla möjliga labyrinter av en given storlek har lika stor sannolikhet att genereras, vilket gör den 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 loop-eraserad slumpmässig vägg skapades av David Bruce Wilson.

Wilson introducerade ursprungligen denna algoritm 1996 när han forskade om slumpmässiga uppspännande träd och Markovkedjor inom sannolikhetsteori. Även om hans arbete främst var inom matematik och statistisk fysik har algoritmen sedan dess använts i stor utsträckning för labyrintgenerering tack vare dess förmåga att producera perfekt enhetliga labyrinter.

Hur Wilsons algoritm fungerar för labyrintgenerering

Wilsons algoritm säkerställer att den slutliga labyrinten är helt ansluten utan loopar genom att iterativt snida banor från obesökta celler med hjälp av slumpmässiga vandringar.

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 en slumpmässig cell och markera den som besökt. Detta fungerar som startpunkt för labyrinten under genereringen.

Steg 3: Slumpmässig promenad med loop-radering

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

Steg 4: Upprepa tills alla celler är besökta:

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

Vidare läsning

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

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