Gjuani dhe vrisni gjeneratorin e labirintit

Algoritmi "Gjuaj dhe Vrit" është në të vërtetë një version i modifikuar i "Rikthyesit Rekursiv". Modifikimi konsiston në skanimin (ose "kërkimin") sistematik të një qelize të re për të vazhduar nga momenti kur nuk mund të shkojë më tej, në krahasim me një kërkim të vërtetë rekursiv, 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 labirinte me pamje dhe ndjesi të ndryshme, vetëm duke zgjedhur të hyni në modalitetin "gjueti" më shpesh ose sipas rregullave specifike. Versioni i zbatuar 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 të Gjuetisë dhe Vrasjes

Algoritmi "Gjuaj dhe Vrit" është një metodë e thjeshtë por efektive për gjenerimin e labirinteve. Është disi i ngjashëm me një kërkim që fillon në thellësi (domethënë algoritmi "Rekursiv i Mbrapshtitjes"), përveçse 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 nga e cila të vazhdojë. Algoritmi përbëhet nga dy faza kryesore: ecja dhe gjuetia.

Si funksionon algoritmi i gjuetisë dhe vrasjes për gjenerimin e labirintit

Hapi 1: Filloni nga një qelizë e rastësishme

• Gjej një qelizë të rastësishme në rrjet dhe shënoje atë si të vizituar.

Hapi 2: Faza e ecjes (Ecje e rastësishme)

• Zgjidhni një fqinj të rastësishëm të pavizituar.
• Lëviz te ai qelizë fqinje, shënoje si të vizituar dhe cakto 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)

• Skano rrjetën rresht pas rreshti (ose kolonë pas kolone).
• Gjej qelizën e parë të pavizituar që ka të paktën një fqinj të vizituar.
• Lidhe atë qelizë me një fqinj të vizituar për të rifilluar fazën e ecjes.
• Përsëriteni derisa të jenë vizituar të gjitha qelizat.

Lexime të mëtejshme

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

• Gjeneratori Maze i Algoritmit të Ellerit
• Gjeneratori i Algoritmit Maze të Uillsonit
• Gjeneratori i Mazes së Algoritmit të Kruskalit