Vilsona algoritma labirinta ģenerators
Publicēts: 2025. gada 16. februāris 19:32:33 UTC
Labirints ģenerators, izmantojot Vilsona algoritmu, lai izveidotu perfektu labirintu. Šis algoritms ģenerē visus iespējamos noteikta izmēra labirintus ar vienādu varbūtību, tāpēc teorētiski tas var ģenerēt daudzu jauktu izkārtojumu labirintus, taču, tā kā ir vairāk iespējamo labirintu ar īsākiem koridoriem nekā garākiem, jūs tos redzēsit biežāk.Wilson's Algorithm Maze Generator
Vilsona algoritms ir cilpas izdzēsta nejaušas pastaigas metode, kas ģenerē vienotus aptverošus kokus labirinta izveidei. Tas nozīmē, ka visi iespējamie noteikta izmēra labirinti, visticamāk, tiks ģenerēti, padarot to par objektīvu labirintu ģenerēšanas paņēmienu. Vilsona algoritmu var uzskatīt par uzlabotu Aldous-Broder algoritma versiju, jo tas ģenerē labirintus ar identiskiem raksturlielumiem, taču tas darbojas daudz ātrāk, tāpēc es neesmu apgrūtināts ar Aldous-Broder algoritma ieviešanu.
Ideāls labirints ir labirints, kurā ir tieši viens ceļš no jebkura labirinta punkta uz jebkuru citu punktu. Tas nozīmē, ka jūs nevarat nonākt apļveida ceļos, bet bieži sastapsieties ar strupceļiem, kas liks jums apgriezties un atgriezties atpakaļ.
Šeit ģenerētajās labirinta kartēs ir noklusējuma versija bez sākuma un beigu pozīcijām, lai jūs paši varētu tās noteikt: būs risinājums no jebkura labirinta punkta uz jebkuru citu punktu. Ja vēlaties iedvesmu, varat ieslēgt ieteikto sākuma un beigu pozīciju un pat apskatīt risinājumu starp šīm divām pozīcijām.
Par Vilsona algoritmu
Vilsona algoritmu vienotu aptverošu koku ģenerēšanai, izmantojot cilpas izdzēstu nejaušu sienu, izveidoja Deivids Brūss Vilsons.
Sākotnēji Vilsons šo algoritmu ieviesa 1996. gadā, pētot nejauši aptverošus kokus un Markova ķēdes varbūtības teorijā. Lai gan viņa darbs galvenokārt bija matemātikā un statistiskajā fizikā, algoritms kopš tā laika ir plaši izmantots labirintu ģenerēšanai, jo tas spēj radīt pilnīgi viendabīgus labirintus.
Kā Vilsona algoritms darbojas labirintu paaudzē
Vilsona algoritms nodrošina, ka gala labirints ir pilnībā savienots bez jebkādām cilpām, iteratīvi izgriežot ceļus no neapmeklētām šūnām, izmantojot nejaušas pastaigas.
1. darbība. Inicializējiet
- Sāciet ar režģi, kas piepildīts ar sienām.
- Definējiet visu iespējamo pārejas šūnu sarakstu.
2. darbība: izvēlieties nejaušu sākuma šūnu
- Izvēlieties jebkuru nejaušu šūnu un atzīmējiet to kā apmeklētu. Tas kalpo kā labirinta sākumpunkts paaudzes laikā.
3. darbība: staigāšana nejauši ar cilpas dzēšanu
- Izvēlieties neapmeklētu šūnu un sāciet nejaušu pastaigu (pārvietojoties nejaušos virzienos).
- Ja pastaiga sasniedz jau apmeklētu šūnu, izdzēsiet visas cilpas ceļā.
- Kad pastaiga savienosies ar apmeklēto reģionu, atzīmējiet visas ceļa šūnas kā apmeklētas.
4. darbība: atkārtojiet, līdz visas šūnas ir apmeklētas :
- Turpiniet atlasīt neapmeklētās šūnas un veikt nejaušas pastaigas, līdz katra šūna ir daļa no labirinta.