Wilsons algoritme labyrintgenerator

Wilsons algoritme er en sløyfe-slettet tilfeldig gåmetode som genererer ensartede spenntrær for labyrintskaping. Dette betyr at alle mulige labyrinter av en gitt størrelse har like stor sannsynlighet for å bli generert, noe som gjør det til en objektiv labyrintgenereringsteknikk. Wilsons algoritme kan betraktes som en forbedret versjon av Aldous-Broder-algoritmen, da den genererer labyrinter med identiske egenskaper, men den kjører mye raskere, så jeg har ikke brydd meg med å implementere Aldous-Broder-algoritmen her.

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

Wilsons algoritme for å generere ensartede trær ved hjelp av en sløyfe-slettet tilfeldig vegg ble laget av David Bruce Wilson.

Wilson introduserte opprinnelig denne algoritmen i 1996 mens han forsket på tilfeldige spenntrær og Markov-kjeder i sannsynlighetsteori. Selv om arbeidet hans først og fremst var innen matematikk og statistisk fysikk, har algoritmen siden blitt mye tatt i bruk for labyrintgenerering på grunn av dens evne til å produsere perfekt ensartede labyrinter.

Hvordan Wilsons algoritme fungerer for labyrintgenerering

Wilsons algoritme sikrer at den endelige labyrinten er fullstendig tilkoblet uten noen sløyfer ved å iterativt skjære ut baner fra ubesøkte celler ved hjelp av tilfeldige turer.

Trinn 1: Initialiser

• Start med et rutenett fylt med vegger.
• Definer en liste over alle mulige passasjeceller.

Trinn 2: Velg en tilfeldig startcelle

• Velg en tilfeldig celle og merk den som besøkt. Dette fungerer som utgangspunkt for labyrinten under generasjonen.

Trinn 3: Tilfeldig vandring med sløyfe-sletting

• Velg en ubesøkt celle og begynn en tilfeldig vandring (beveger deg i tilfeldige retninger).
• Hvis turen når en allerede besøkt celle, sletter du eventuelle løkker i stien.
• Når turen kobles til det besøkte området, merker du alle cellene i stien som besøkt.

Trinn 4: Gjenta til alle cellene er besøkt:

• Fortsett å velge ubesøkte celler og utføre tilfeldige turer til hver celle er en del av labyrinten.

Videre lesing

Hvis du likte dette innlegget, kan du også like disse forslagene:

• Rekursiv Backtracker Maze Generator
• Kruskals algoritme-labyrint-generator
• Jakt og Drep Labyrint Generator