Algorithm Maze Generator Wilson
Birt: 19. mars 2025 kl. 20:34:27 UTC
Völundarhús rafall sem notar reiknirit Wilsons til að búa til fullkomið völundarhús. Þetta reiknirit býr til öll möguleg völundarhús af tiltekinni stærð með sömu líkum, þannig að það getur í orði búið til völundarhús með mörgum blönduðum skipulagi, en þar sem það eru fleiri mögulegar völundarhús með styttri göngum en lengri, muntu sjá þau oftar.Wilson's Algorithm Maze Generator
Reiknirit Wilsons er lykkjueydd handahófskennd gönguaðferð sem býr til einsleit tré til að búa til völundarhús. Þetta þýðir að öll möguleg völundarhús af tiltekinni stærð eru jafn líkleg til að myndast, sem gerir það að óhlutdrægri völundarhúsmyndunartækni. Reiknirit Wilsons getur talist endurbætt útgáfa af Aldous-Broder reikniritinu, þar sem það býr til völundarhús með sömu eiginleika, en það keyrir mun hraðar, svo ég hef ekki nennt að innleiða Aldous-Broder reikniritið hér.
Fullkomið völundarhús er völundarhús þar sem það er nákvæmlega ein leið frá hvaða stað sem er í völundarhúsinu til annars staðar. Það þýðir að þú getur ekki endað á því að fara í hringi, en þú munt oft lenda í blindgötum, sem neyðir þig til að snúa við og fara til baka.
Völundarkortin sem mynduð eru hér innihalda sjálfgefna útgáfu án upphafs- og lokastaða, svo þú getur ákveðið þær sjálfur: það verður lausn frá hvaða stað sem er í völundarhúsinu til hvers annars. Ef þú vilt innblástur geturðu virkjað tillögu um upphafs- og lokastöðu - og jafnvel séð lausnina á milli þeirra tveggja.
Um Wilson's reiknirit
Wilson's reiknirit fyrir að búa til jafna spanningstré með því að nota lykkju-eytt tilviljanakennt vegg var búið til af David Bruce Wilson.
Wilson kynnti upphaflega þetta reiknirit árið 1996 þegar hann var að rannsaka tilviljanakennd spanningstré og Markov keðjur í líkindi kenningum. Þó að vinna hans hafi aðallega verið í stærðfræði og tölfræði eðlisfræði, hefur reikniritið verið mikið notað við gerð völundarhúsa vegna getu þess til að framleiða fullkomlega jöfn völundarhús.
Hvernig Wilson's reiknirit virkar fyrir gerð völundarhúsa
Wilson's reiknirit tryggir að endanlega völundarhúsið sé algerlega tengt án nokkurra lykkja með því að höggva slóðir frá óheimsóttum frumum með því að nota tilviljanakenndar göngur.
Skref 1: Fyrsta uppsetning
- Byrjaðu með neti fullt af veggjum.
- Skilgreindu lista yfir allar mögulegar farvegsfrumur.
Skref 2: Veldu tilviljanakennda upphafsfrumu
- Veldu hvaða tilviljanakennda frumu sem er og merkja hana sem heimsótta. Þetta þjónar sem upphafspunktur völundarhússins meðan á gerðinni stendur.
Skref 3: Tilviljanakennd göngur með lykkju-eyðingu
- Veldu óheimsótt frumu og byrjar tilviljanakennda göngu (ferða í tilviljanakenndum áttum).
- Ef göngurnar ná til frumur sem þegar hefur verið heimsótt, eyðileggja allar lykkjur í slóðinni.
- Þegar göngurnar tengjast heimsótta svæðinu, merkja allar frumur í slóðinni sem heimsóttar.
Skref 4: Endurtaka þar til allar frumur hafa verið heimsóttar:
- Halda áfram að velja óheimsóttar frumur og framkvæma tilviljanakenndar göngur þar til hver fruma er hluti af völundarhúsinu.