Wilsoni algoritmi labürindi generaator

Wilsoni algoritm on silmuste kustutamise ja juhusliku kõnni meetod, mis genereerib labürindi loomiseks ühtlaseid ulatuvaid puid. See tähendab, et kõik antud suurusega võimalikud labürindid genereeritakse võrdse tõenäosusega, mis teeb sellest erapooletu labürindi genereerimise tehnika. Wilsoni algoritmi võib pidada Aldous-Broderi algoritmi täiustatud versiooniks, kuna see genereerib identsete omadustega labürinte, kuid töötab palju kiiremini, seega pole ma siin vaevunud Aldous-Broderi algoritmi rakendama.

Täiuslik labürint on labürint, kus on täpselt üks tee labürindi mis tahes punktist mis tahes teise punkti. See tähendab, et te ei saa sattuda ringiratastesse, kuid sageli satute ummikteedesse, mis sunnib teid ümber pöörama ja tagasi minema.

Siin genereeritud labürindi kaardid sisaldavad vaikimisi versiooni ilma algus- ja lõpp-punktideta, nii et saate need ise otsustada: labürindi mis tahes punktist mis tahes teise punkti on olemas lahendus. Kui soovite inspiratsiooni, saate lubada soovitatud algus- ja lõpupositsiooni - ja isegi näha lahendust nende kahe vahel.

Wilsoni algoritmi kohta

Wilsoni algoritmi ühtlaste ulatuvate puude genereerimiseks silmusteta juhusliku seina abil lõi David Bruce Wilson.

Wilson tutvustas seda algoritmi esmakordselt 1996. aastal, uurides tõenäosusteoorias juhuslikke ulatuvaid puid ja Markovi ahelaid. Kuigi tema töö oli peamiselt matemaatika ja statistilise füüsika valdkonnas, on algoritm sellest ajast alates laialdaselt kasutusel labürintide genereerimiseks tänu oma võimele luua ideaalselt ühtlaseid labürinte.

Kuidas Wilsoni algoritm labürindi genereerimiseks töötab

Wilsoni algoritm tagab, et lõplik labürint on täielikult ühendatud ilma silmusteta, nikerdades iteratiivselt teid külastamata rakkudest juhuslike jalutuskäikude abil.

1. samm: initsialiseerimine

• Alusta seintega täidetud ruudustikuga.
• Defineeri kõigi võimalike passaažirakkude loend.

2. samm: valige juhuslik alguslahter

• Vali suvaline lahter ja märgi see külastatuks. See toimib labürindi genereerimise alguspunktina.

3. samm: juhuslik jalutuskäik silmuse kustutamisega

• Vali külastamata lahter ja alusta juhuslikku jalutuskäiku (liigu juhuslikes suundades).
• Kui jalutuskäik jõuab juba külastatud lahtrisse, kustuta teelt kõik silmused.
• Kui jalutuskäik on külastatud piirkonnaga ühenduses, märkige kõik rajal olevad lahtrid külastatuks.

4. samm: korrake, kuni kõik lahtrid on külastatud:

• Jätka külastamata lahtrite valimist ja juhuslike jalutuskäikude sooritamist, kuni iga lahter on labürindi osa.

Lisalugemist

Kui see postitus teile meeldis, võivad teile meeldida ka need soovitused:

• Elleri algoritmi labürindi generaator
• Rekursiivne Backtracker labürindi generaator
• Kruskali algoritmi labürindi generaator