Ang Algorithm Maze Generator ni Wilson

Ang algorithm ni Wilson ay isang loop-erased random walk method na bumubuo ng magkakatulad na spanning tree para sa paggawa ng maze. Nangangahulugan ito na ang lahat ng posibleng maze ng isang partikular na laki ay pantay na malamang na mabuo, na ginagawa itong isang walang pinapanigan na pamamaraan ng pagbuo ng maze. Ang algorithm ni Wilson ay maaaring ituring na isang pinahusay na bersyon ng Aldous-Broder algorithm, dahil ito ay bumubuo ng mga maze na may magkaparehong katangian, ngunit ito ay tumatakbo nang mas mabilis, kaya hindi ako nag-abala sa pagpapatupad ng Aldous-Broder algorithm dito.

Ang perpektong maze ay isang maze kung saan mayroong eksaktong isang landas mula sa anumang punto sa maze hanggang sa anumang iba pang punto. Nangangahulugan iyon na hindi ka maaaring maglibot sa mga bilog, ngunit madalas kang makatagpo ng mga patay na dulo, na pinipilit kang tumalikod at bumalik.

Ang mga mapa ng maze na nabuo dito ay may kasamang default na bersyon nang walang anumang mga posisyon sa pagsisimula at pagtatapos, kaya maaari kang magpasya para sa iyong sarili: magkakaroon ng solusyon mula sa anumang punto sa maze hanggang sa anumang iba pang punto. Kung gusto mo ng inspirasyon, maaari mong paganahin ang isang iminungkahing posisyon sa pagsisimula at pagtatapos - at kahit na makita ang solusyon sa pagitan ng dalawa.

Tungkol sa Algorithm ni Wilson

Ang algorithm ni Wilson para sa paggawa ng mga uniform spanning tree gamit ang loop-erased random walk ay nilikha ni David Bruce Wilson.

Orihinal na ipinakilala ni Wilson ang algorithm na ito noong 1996 habang nagsasagawa ng pananaliksik tungkol sa mga random spanning tree at Markov chains sa teorya ng probabilidad. Bagamat ang kanyang trabaho ay pangunahing nasa matematika at pisikang estadistikal, ang algorithm na ito ay malawakang tinanggap para sa paggawa ng mga maze dahil sa kakayahan nitong makabuo ng mga perpektong uniform na maze.

Paano Gumagana ang Algorithm ni Wilson para sa Pagbuo ng Maze

Tinitiyak ng algorithm ni Wilson na ang huling maze ay ganap na konektado nang walang mga loop sa pamamagitan ng paulit-ulit na pag-ukit ng mga landas mula sa mga hindi pa nabisitang cell gamit ang random walks.

Hakbang 1: Inisyalisa

• Mag-umpisa sa isang grid na puno ng mga pader.
• Mag-define ng isang listahan ng lahat ng posibleng mga passage cell.

Hakbang 2: Pumili ng Random na Panimulang Cell

• Pumili ng kahit anong random na cell at markahan ito bilang nabisita. Ito ay magsisilbing panimulang punto ng maze habang ito ay binubuo.

Hakbang 3: Random Walk na may Pag-aalis ng Loop

• Pumili ng isang hindi pa nabisitang cell at magsimula ng random walk (paggalaw sa mga random na direksyon).
• Kung ang walk ay makarating sa isang cell na nabisita na, alisin ang mga loop sa landas.
• Kapag ang walk ay kumonekta sa nabisitang rehiyon, markahan ang lahat ng cell sa landas bilang nabisita.

Hakbang 4: Ulitin Hanggang ang Lahat ng Cell ay Mabisita:

• Patuloy na pumili ng mga hindi pa nabisitang cell at magsagawa ng random walks hanggang ang bawat cell ay maging bahagi ng maze.