Gjeneratori i Algoritmit Maze të Uillsonit
Publikuar: 16 shkurt 2025 në 7:36:29 e pasdites, UTC
Gjeneratori Maze duke përdorur algoritmin e Wilson për të krijuar një labirint të përsosur. Ky algoritëm gjeneron të gjitha labirintet e mundshme të një madhësie të caktuar me të njëjtin probabilitet, kështu që në teori mund të gjenerojë labirinte të shumë planimetrive të përziera, por duke qenë se ka më shumë labirinte të mundshme me korridore më të shkurtra se më të gjata, më shpesh do t'i shihni ato.Wilson's Algorithm Maze Generator
Algoritmi i Wilsonit është një metodë ecjeje e rastësishme e fshirë me loop që gjeneron pemë uniforme që shtrihen për krijimin e labirinteve. Kjo do të thotë se të gjitha labirintet e mundshme të një madhësie të caktuar kanë po aq gjasa të gjenerohen, duke e bërë atë një teknikë të paanshme të gjenerimit të labirinteve. Algoritmi i Wilsonit mund të konsiderohet si një version i përmirësuar i algoritmit Aldous-Broder, pasi gjeneron labirinte me karakteristika identike, por ai ecën shumë më shpejt, kështu që nuk e kam shqetësuar zbatimin e algoritmit Aldous-Broder këtu.
Një labirint i përsosur është një labirint në të cilin ka saktësisht një rrugë nga çdo pikë në labirint në çdo pikë tjetër. Kjo do të thotë që nuk mund të përfundoni duke ecur në rreth, por shpesh do të hasni në rrugë pa krye, duke ju detyruar të ktheheni dhe të ktheheni.
Hartat e labirintit të krijuara këtu përfshijnë një version të paracaktuar pa asnjë pozicion fillimi dhe mbarimi, kështu që ju mund t'i vendosni ato vetë: do të ketë një zgjidhje nga çdo pikë në labirint në çdo pikë tjetër. Nëse dëshironi frymëzim, mund të aktivizoni një pozicion të sugjeruar fillimi dhe përfundimi - dhe madje të shihni zgjidhjen midis të dyjave.
Rreth algoritmit të Uillsonit
Algoritmi i Wilsonit për gjenerimin e uniformave që shtrihen në pemë duke përdorur një mur të rastësishëm të fshirë me lak u krijua nga David Bruce Wilson.
Wilson fillimisht e prezantoi këtë algoritëm në vitin 1996, ndërsa hulumtonte pemët e shtrira në mënyrë të rastësishme dhe zinxhirët Markov në teorinë e probabilitetit. Edhe pse puna e tij ishte kryesisht në matematikë dhe fizikë statistikore, algoritmi që atëherë është miratuar gjerësisht për brezin e labirinteve për shkak të aftësisë së tij për të prodhuar labirinte krejtësisht uniforme.
Si funksionon algoritmi i Uillsonit për brezin Maze?
Algoritmi i Wilsonit siguron që labirinti përfundimtar të jetë plotësisht i lidhur pa asnjë loop duke skalitur në mënyrë iterative shtigjet nga qelizat e pavizituara duke përdorur shëtitje të rastësishme.
Hapi 1: Initialize
- Filloni me një rrjetë të mbushur me mure.
- Përcaktoni një listë të të gjitha qelizave të mundshme të kalimit.
Hapi 2: Zgjidhni një qelizë të rastësishme të fillimit
- Zgjidh çdo qelizë të rastësishme dhe shëno atë siç vizitohet. Kjo shërben si pikënisje e labirintit gjatë brezit.
Hapi 3: Shëtitje e rastësishme me fshirjen e loop-it
- Zgjidhni një qelizë të pavizituar dhe filloni një shëtitje të rastësishme (duke lëvizur në drejtime të rastësishme).
- Nëse ecja arrin në një qelizë tashmë të vizituar, fshini çdo lak në shteg.
- Pasi shëtitja lidhet me rajonin e vizituar, shënoni të gjitha qelizat në shtegun siç vizitohet.
Hapi 4: Përsëriteni derisa të vizitohen të gjitha qelizat:
- Vazhdoni përzgjedhjen e qelizave të pavizituara dhe kryerjen e shëtitjeve të rastësishme derisa çdo qelizë të jetë pjesë e labirintit.