Miklix

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.

Þessi síða var vélþýdd úr ensku til að gera hana aðgengilega sem flestum. Því miður er vélþýðing ekki enn fullkomin tækni, svo villur geta komið upp. Ef þú vilt geturðu skoðað upprunalegu ensku útgáfuna hér:

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.


Búðu til nýtt völundarhús








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.
Deildu á BlueskyDeildu á FacebookDeildu á LinkedInDeildu á TumblrDeildu á XDeildu á LinkedInFestu á Pinterest

Mikkel Christensen

Um höfundinn

Mikkel Christensen
Mikkel er skapari og eigandi miklix.com. Hann hefur yfir 20 ára reynslu sem faglegur tölvuforritari/hugbúnaðarhönnuður og er nú í fullu starfi hjá stóru evrópsku upplýsingatæknifyrirtæki. Þegar hann er ekki að blogga eyðir hann frítíma sínum í margs konar áhugamál, áhugamál og athafnir, sem geta að einhverju leyti endurspeglast í margs konar efni sem fjallað er um á þessari vefsíðu.