Wilsonin algoritmin sokkelogeneraattori

Wilsonin algoritmi on silmukoista poistettu satunnaiskävelymenetelmä, joka luo tasaisia virityspuita sokkeloiden luomista varten. Tämä tarkoittaa, että kaikki tietyn kokoiset mahdolliset sokkelot generoidaan yhtä todennäköisesti, mikä tekee siitä harhattoman sokkeloiden generointitekniikan. Wilsonin algoritmia voidaan pitää Aldous-Broder-algoritmin paranneltuna versiona, koska se luo identtisillä ominaisuuksilla varustettuja sokkeloita, 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

Wilsonin algoritmin tasaisten virittävien puiden luomiseksi silmukasta poistetun satunnaisseinän avulla loi David Bruce Wilson.

Wilson esitteli tämän algoritmin alun perin vuonna 1996 tutkiessaan satunnaisia virityspuita ja Markov-ketjuja todennäköisyysteoriassa. Vaikka hänen työnsä oli pääasiassa matematiikan ja tilastollisen fysiikan alalla, algoritmia on sittemmin käytetty laajalti sokkeloiden luomiseen, koska se pystyy tuottamaan täysin yhtenäisiä sokkeloita.

Miten Wilsonin algoritmi toimii sokkeloiden luomisessa

Wilsonin algoritmi varmistaa, että lopullinen sokkelo on täysin yhtenäinen ilman silmukoita, iteratiivisesti kaivertamalla polkuja vierailemattomista soluista satunnaisten kävelyjen avulla.

Vaihe 1: Alusta

• Aloita ruudukolla, joka on täynnä seiniä.
• Määrittele lista kaikista mahdollisista kulkusoluista.

Vaihe 2: Valitse satunnainen aloitussolu

• Valitse mikä tahansa satunnainen solu ja merkitse se käydyksi. Tämä toimii sokkelon lähtöpisteenä luonnin aikana.

Vaihe 3: Satunnainen kävely silmukan poistolla

• Valitse vierailematon solu ja aloita satunnainen kävely (liikkuminen satunnaisiin suuntiin).
• Jos kävely saavuttaa jo vieraillun solun, poista polulta kaikki silmukat.
• Kun kävelyreitti yhdistyy vierailtuun alueeseen, merkitse kaikki polun solut vierailluiksi.

Vaihe 4: Toista, kunnes kaikki solut on käyty läpi:

• Jatka vierailemattomien solujen valitsemista ja satunnaisten kävelyjen suorittamista, kunnes jokainen solu on osa sokkeloa.

Lisälukemista

Jos pidit tästä postauksesta, saatat pitää myös näistä ehdotuksista:

• Rekursiivinen Backtracker Maze Generator
• Kasvavan puun algoritmin sokkelogeneraattori
• Ellerin algoritmin sokkelogeneraattori