Wilsonin algoritmin sokkelogeneraattori
Julkaistu: 16. helmikuuta 2025 klo 19.31.50 UTC
Labyrinttigeneraattori, joka käyttää Wilsonin algoritmia täydellisen sokkelon luomiseen. Tämä algoritmi generoi kaikki mahdolliset tietyn kokoiset sokkelot samalla todennäköisyydellä, joten se voi teoriassa luoda sokkeloita, joissa on monia sekoitettuja asetteluja, mutta koska on enemmän mahdollisia sokkeloita, joissa on lyhyemmät käytävät kuin pidempiä, näet niitä useammin.Wilson's Algorithm Maze Generator
Wilsonin algoritmi on silmukalla pyyhitty satunnainen kävelymenetelmä, joka luo yhtenäisiä virittäviä puita sokkelon luomista varten. Tämä tarkoittaa, että kaikki mahdolliset tietyn kokoiset sokkelot luodaan yhtä todennäköisesti, mikä tekee siitä puolueettoman sokkelon luomistekniikan. Wilsonin algoritmia voidaan pitää parannetun versiona Aldous-Broder-algoritmista, koska se luo sokkeloita, joilla on identtiset ominaisuudet, mutta se toimii paljon nopeammin, joten en ole vaivautunut toteuttamaan Aldous-Broder-algoritmia tässä.
Täydellinen sokkelo on sokkelo, jossa on täsmälleen yksi reitti mistä tahansa sokkelon pisteestä mihin tahansa toiseen pisteeseen. Tämä tarkoittaa, että et voi päätyä kiertämään ympyrää, mutta joudut usein umpikujaan, jolloin sinun on pakko kääntyä ympäri ja palata takaisin.
Tässä luotuihin sokkelokarttoihin sisältyy oletusversio, jossa ei ole alku- ja loppupisteitä, joten voit päättää ne itse: mistä tahansa sokkelon pisteestä mihin tahansa muuhun pisteeseen on olemassa ratkaisu. Jos haluat inspiraatiota, voit ottaa käyttöön ehdotetun alku- ja maalipaikan - ja jopa nähdä ratkaisun näiden kahden välissä.
Tietoja Wilsonin algoritmista
David Bruce Wilson loi Wilsonin algoritmin yhtenäisten virittävien puiden luomiseksi silmukkapoistetun satunnaisen seinän avulla.
Wilson esitteli tämän algoritmin alun perin vuonna 1996 tutkiessaan satunnaisia virittäviä puita ja Markov-ketjuja todennäköisyysteoriassa. Vaikka hänen työnsä kohdistui pääasiassa matematiikkaan ja tilastolliseen fysiikkaan, algoritmi on sittemmin otettu laajalti käyttöön sokkeloiden luomiseen, koska se pystyy tuottamaan täysin yhtenäisiä sokkeloita.
Kuinka Wilsonin algoritmi toimii sokkelosukupolvessa
Wilsonin algoritmi varmistaa, että lopullinen sokkelo on täysin yhdistetty ilman silmukoita leikkaamalla iteratiivisesti polkuja vierailemattomista soluista satunnaisten kävelylenkkien avulla.
Vaihe 1: Alusta
- Aloita seinillä täytetystä ruudukosta.
- Määritä luettelo kaikista mahdollisista läpikulkusoluista.
Vaihe 2: Valitse satunnainen aloitussolu
- Valitse mikä tahansa satunnainen solu ja merkitse se käydyksi. Tämä toimii sokkelon lähtökohtana sukupolven aikana.
Vaihe 3: Satunnainen kävely silmukan pyyhkimällä
- Valitse vierailematon solu ja aloita satunnainen kävely (liikkumalla satunnaisiin suuntiin).
- Jos kävely saavuttaa jo vieraillun solun, poista kaikki silmukat polusta.
- Kun kävelymatka yhdistyy vieraillulle alueelle, merkitse kaikki polun solut käydyiksi.
Vaihe 4: Toista, kunnes kaikki solut ovat käyneet :
- Jatka vierailemattomien solujen valitsemista ja satunnaisten kävelylenkkien tekemistä, kunnes jokainen solu on osa sokkeloa.