Gjuani dhe vrisni gjeneratorin e labirintit
Publikuar: 16 shkurt 2025 në 8:58:47 e pasdites, UTC
Gjeneratori i labirintit duke përdorur algoritmin Hunt and Kill për të krijuar një labirint të përsosur. Ky algoritëm është i ngjashëm me Recursive Backtracker, por tenton të gjenerojë labirint me korridore disi më pak të gjata dhe dredha-dredha.Hunt and Kill Maze Generator
Algoritmi Hunt and Kill është me të vërtetë një version i modifikuar i Backtracker Recursive. Modifikimi konsiston në skanimin (ose "gjuetinë") sistematike për një qelizë të re për të vazhduar nga momenti kur nuk mund të shkojë më tej, në krahasim me një kërkim të vërtetë rekurziv, i cili gjithmonë do të kthehet në qelizën e mëparshme në pirg.
Për shkak të kësaj, ky algoritëm mund të përshtatet lehtësisht për të gjeneruar labirint me pamje dhe ndjesi të ndryshme, thjesht duke zgjedhur të hyni në modalitetin "gjueti" më shpesh ose sipas rregullave specifike. Versioni i implementuar këtu hyn në modalitetin "gjueti" vetëm kur nuk mund të shkojë më larg nga qeliza aktuale.
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 Hunt and Kill
Algoritmi Hunt and Kill është një metodë e thjeshtë por efektive për gjenerimin e labirinteve. Është disi e ngjashme me një kërkim të parë në thellësi (dmth. algoritmi Recursive Backtracker), me përjashtim të rasteve kur nuk mund të shkojë më larg nga pozicioni aktual, ai skanon (ose "gjuan") sistematikisht mbi labirint për të gjetur një qelizë të re për të vazhduar. Algoritmi përbëhet nga dy faza kryesore: ecja dhe gjuetia.
Si funksionon algoritmi Hunt and Kill për Maze Generation
Hapi 1: Filloni në një qelizë të rastësishme
- Gjeni një qelizë të rastësishme në rrjet dhe shënojeni atë si të vizituar.
Hapi 2: Faza e Ecjes (Ecje e rastësishme)
- Zgjidhni një fqinj të rastësishëm të pavizituar.
- Lëvizni te ai fqinj, shënojeni atë si të vizituar dhe gdhendni një shteg midis qelizës së mëparshme dhe asaj të re.
- Përsëriteni derisa të mos mbeten fqinjë të pavizituar.
Hapi 3: Faza e Gjuetisë (Kthim prapa nëpërmjet skanimit)
- Skanoni rrjetin rresht pas rreshti (ose kolonë pas kolonë).
- Gjeni qelizën e parë të pavizituar që ka të paktën një fqinj të vizituar.
- Lidheni atë qelizë me një fqinj të vizituar për të rifilluar fazën e ecjes.
- Përsëriteni derisa të vizitohen të gjitha qelizat.