Wilsons Algoritme Labyrintgenerator

Wilsons algoritme er en loop-erased random walk-metode, der genererer ensartede spanning trees til labyrintoprettelse. Det betyder, at alle mulige labyrinter af en given størrelse har lige stor sandsynlighed for at blive genereret, hvilket gør den til en objektiv labyrintgenereringsteknik. Wilsons algoritme kan betragtes som en forbedret version af Aldous-Broder-algoritmen, da den genererer labyrinter med identiske egenskaber, men den kører meget hurtigere, så jeg har ikke gidet implementere Aldous-Broder-algoritmen her.

En perfekt labyrint er en labyrint, hvor der er præcis én vej fra et hvilket som helst punkt i labyrinten til et hvilket som helst andet punkt. Det betyder, at du ikke kan ende med at gå rundt i cirkler, men du vil ofte støde på blindgyder, som tvinger dig til at vende om og gå tilbage.

De labyrintkort, der genereres her, indeholder en standardversion uden start- og slutpositioner, så du selv kan bestemme dem: der vil være en løsning fra ethvert punkt i labyrinten til ethvert andet punkt. Hvis du vil have inspiration, kan du aktivere en foreslået start- og slutposition - og endda se løsningen mellem de to.

Om Wilsons algoritme

Wilsons algoritme til at generere ensartede udspændende træer ved hjælp af en løkkeslettet tilfældig væg blev skabt af David Bruce Wilson.

Wilson introducerede oprindeligt denne algoritme i 1996, mens han forskede i tilfældige udspændende træer og Markov-kæder i sandsynlighedsteori. Selvom hans arbejde primært var inden for matematik og statistisk fysik, er algoritmen siden blevet bredt anvendt til labyrintgenerering på grund af dens evne til at producere perfekt ensartede labyrinter.

Hvordan Wilsons algoritme fungerer til labyrintgenerering

Wilsons algoritme sikrer, at den endelige labyrint er fuldt forbundet uden løkker ved iterativt at udskære stier fra ubesøgte celler ved hjælp af tilfældige vandringer.

Trin 1: Initialiser

• Start med et gitter fyldt med vægge.
• Definer en liste over alle mulige passageceller.

Trin 2: Vælg en tilfældig startcelle

• Vælg en tilfældig celle og marker den som besøgt. Dette fungerer som startpunkt for labyrinten under genereringen.

Trin 3: Tilfældig vandring med løkkesletning

• Vælg en ubesøgt celle og begynd en tilfældig gåtur (bevæger dig i tilfældige retninger).
• Hvis gåturen når en allerede besøgt celle, skal du slette eventuelle løkker i stien.
• Når turen forbinder til det besøgte område, skal du markere alle cellerne i stien som besøgte.

Trin 4: Gentag indtil alle celler er besøgt:

• Fortsæt med at vælge ubesøgte celler og udføre tilfældige ture, indtil hver celle er en del af labyrinten.

Yderligere læsning

Hvis du kunne lide dette indlæg, kan du måske også lide disse forslag:

• Ellers algoritme labyrintgenerator
• Jag og dræb labyrintgenerator
• Growing Tree algoritme labyrintgenerator