Wilsons algoritme labyrintgenerator

Wilsons algoritme er en sløyfeslettet tilfeldig gangmetode som genererer ensartede spennede trær for labyrintoppretting. Dette betyr at alle mulige labyrinter av en gitt størrelse er like sannsynlig å bli generert, noe som gjør det til en objektiv labyrintgenereringsteknikk. Wilsons algoritme kan betraktes som en forbedret versjon av Aldous-Broder-algoritmen, siden 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 spennende trær ved å bruke en sløyfeslettet tilfeldig vegg ble laget av David Bruce Wilson.

Wilson introduserte opprinnelig denne algoritmen i 1996 mens han undersøkte tilfeldig spennende trær og Markov-kjeder i sannsynlighetsteori. Selv om arbeidet hans først og fremst var innen matematikk og statistisk fysikk, har algoritmen siden blitt bredt 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 koblet sammen uten løkker ved iterativt å skjære ut stier 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 utgangspunktet for labyrinten under generasjonen.

Trinn 3: Tilfeldig gange med sløyfesletting

• Velg en ubesøkt celle og begynn en tilfeldig spasertur (beveg deg i tilfeldige retninger).
• Hvis turen når en allerede besøkt celle, slett eventuelle løkker i banen.
• Når turen kobles til den besøkte regionen, merker du alle cellene i stien som besøkt.

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

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