Gjeneratori i Algoritmit Maze të Uillsonit

Algoritmi i Wilsonit është një metodë ecjeje të rastësishme me fshirje loop-i që gjeneron pemë uniforme që përfshijnë për krijimin e labirinteve. Kjo do të thotë që të gjitha labirintet e mundshme të një madhësie të caktuar kanë të njëjtën probabilitet të gjenerohen, duke e bërë atë një teknikë të paanshme të gjenerimit të labirinteve. Algoritmi i Wilsonit mund të konsiderohet një version i përmirësuar i algoritmit Aldous-Broder, pasi gjeneron labirinte me karakteristika identike, por funksionon shumë më shpejt, kështu që nuk jam shqetësuar ta zbatoj algoritmin 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ë Wilsonit

Algoritmi i Wilsonit për gjenerimin e pemëve uniforme që përfshijnë një mur të rastësishëm të fshirë me loop u krijua nga David Bruce Wilson.

Wilson e prezantoi fillimisht këtë algoritëm në vitin 1996, ndërsa bënte kërkime mbi pemët e rastësishme që shtrihen 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ë përdorur gjerësisht për gjenerimin e labirinteve për shkak të aftësisë së tij për të prodhuar labirinte të përkryera uniforme.

Si funksionon algoritmi i Wilsonit për gjenerimin e labirinteve

Algoritmi i Wilsonit siguron që labirinti përfundimtar të jetë i lidhur plotësisht pa asnjë lak duke gdhendur në mënyrë iterative shtigje nga qelizat e pavizituara duke përdorur ecje të rastësishme.

Hapi 1: Inicializoni

• 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ë fillestare të rastësishme

• Zgjidh çdo qelizë të rastësishme dhe shënoje si të vizituar. Kjo shërben si pikënisje e labirintit gjatë gjenerimit.

Hapi 3: Ecje e rastësishme me fshirje në loop

• Zgjidh një qelizë të pavizituar dhe fillo një shëtitje të rastësishme (duke lëvizur në drejtime të rastësishme).
• Nëse ecja arrin në një qelizë të vizituar tashmë, fshini çdo syth në shteg.
• Pasi shëtitja të lidhet me rajonin e vizituar, shënoni të gjitha qelizat në shteg si të vizituara.

Hapi 4: Përsëriteni derisa të vizitohen të gjitha qelizat:

• Vazhdoni të zgjidhni qelizat e pavizituara dhe të kryeni shëtitje të rastësishme derisa çdo qelizë të jetë pjesë e labirintit.

Lexime të mëtejshme

Nëse ju pëlqeu ky postim, mund t'ju pëlqejnë edhe këto sugjerime:

• Recursive Backtracker Maze Generator
• Gjuani dhe vrisni gjeneratorin e labirintit
• Gjeneratori i Mazes së Algoritmit të Kruskalit