Wilsons Algoritme Labyrintgenerator
Udgivet: 16. februar 2025 kl. 19.31.27 UTC
Labyrintgenerator ved hjælp af Wilsons algoritme til at skabe en perfekt labyrint. Denne algoritme genererer alle mulige labyrinter af en given størrelse med samme sandsynlighed, så den kan i teorien generere labyrinter med mange blandede layouts, men da der er flere mulige labyrinter med kortere korridorer end længere, vil du oftere se dem.Wilson's Algorithm Maze Generator
Wilsons algoritme er en sløjfeslettet tilfældig gangmetode, der genererer ensartede spændende træer til labyrintskabelse. Dette betyder, at alle mulige labyrinter af en given størrelse er lige så sandsynlige, at de bliver genereret, hvilket gør det til en upartisk labyrintgenereringsteknik. Wilsons algoritme kan betragtes som en forbedret udgave af Aldous-Broder-algoritmen, da den genererer labyrinter med identiske karakteristika, men den kører meget hurtigere, så jeg har ikke gidet at 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 spændende træer ved hjælp af en sløjfeslettet tilfældig væg blev skabt af David Bruce Wilson.
Wilson introducerede oprindeligt denne algoritme i 1996, mens han forskede i tilfældige træer og Markov-kæder i sandsynlighedsteori. Selvom hans arbejde primært var i matematik og statistisk fysik, er algoritmen siden blevet bredt brugt til labyrintgenerering på grund af dens evne til at producere perfekt ensartede labyrinter.
Hvordan Wilsons algoritme virker for Maze Generation
Wilsons algoritme sikrer, at den endelige labyrint er fuldt forbundet uden nogen sløjfer ved iterativt at udskære stier fra ubesøgte celler ved hjælp af tilfældige vandreture.
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 tjener som udgangspunktet for labyrinten under generationen.
Trin 3: Tilfældig gåtur med sløjfesletning
- Vælg en ubesøgt celle og start en tilfældig gåtur (bevæg dig i tilfældige retninger).
- Hvis gåturen når en allerede besøgt celle, skal du slette eventuelle sløjfer i stien.
- Når gåturen har forbindelse til den besøgte region, skal du markere alle cellerne i stien som besøgt.
Trin 4: Gentag, indtil alle celler er besøgt :
- Fortsæt med at vælge ubesøgte celler og udfør tilfældige gåture, indtil hver celle er en del af labyrinten.