Wilsoni algoritmi labürindi generaator
Avaldatud: 16. veebruar 2025, kell 19:31:49 UTC
Labürindigeneraator, mis kasutab täiusliku labürindi loomiseks Wilsoni algoritmi. See algoritm genereerib kõik võimalikud antud suurusega labürindid sama tõenäosusega, nii et teoreetiliselt võib see luua paljude segapaigutustega labürinte, kuid kuna lühema koridoriga labürinte on rohkem kui pikemaid, näete neid sagedamini.Wilson's Algorithm Maze Generator
Wilsoni algoritm on tsükliga kustutatud juhusliku kõndimise meetod, mis genereerib labürindi loomiseks ühtseid ulatuvaid puid. See tähendab, et kõik võimalikud antud suurusega labürindid luuakse võrdse tõenäosusega, mistõttu on tegemist erapooletu labürindi genereerimise tehnikaga. Wilsoni algoritmi võib pidada Aldous-Broderi algoritmi täiustatud versiooniks, kuna see genereerib identsete omadustega labürinti, kuid töötab palju kiiremini, nii et ma ei ole vaevunud siin Aldous-Broderi algoritmi juurutama.
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 ühtsete ulatuvate puude genereerimiseks silmustega kustutatud juhusliku seina abil lõi David Bruce Wilson.
Algselt tutvustas Wilson seda algoritmi 1996. aastal, kui uuris tõenäosusteoorias juhuslikult ulatuvaid puid ja Markovi ahelaid. Kuigi tema töö oli peamiselt seotud matemaatika ja statistilise füüsikaga, on algoritm sellest ajast alates laialdaselt kasutusele võetud labürindi genereerimiseks, kuna see suudab luua täiesti ühtlaseid labürinti.
Kuidas Wilsoni algoritm labürindi genereerimisel töötab
Wilsoni algoritm tagab, et lõplik labürint on täielikult ühendatud ilma silmusteta, nikerdades juhuslike jalutuskäikude abil korduvalt külastamata rakkudest radu.
1. samm: lähtestamine
- Alustage seintega täidetud võrega.
- Määratlege kõigi võimalike läbipääsurakkude loend.
2. samm: valige juhuslik stardilahter
- Valige suvaline lahter ja märkige see külastatuks. See toimib genereerimise ajal labürindi lähtepunktina.
3. samm: juhuslik jalutuskäik silmuse kustutamisega
- Valige külastamata lahter ja alustage juhuslikku jalutuskäiku (juhuslikes suundades liikudes).
- Kui jalutuskäik jõuab juba külastatud lahtrisse, kustutage teelt kõik silmused.
- Kui jalutuskäik on ühendatud külastatud piirkonnaga, märkige kõik tee lahtrid külastatuks.
4. samm: korrake, kuni kõik rakud on külastatud :
- Jätkake külastamata lahtrite valimist ja juhuslikke jalutuskäike, kuni iga lahter on osa labürindist.