Recursive Backtracker Maze Generator

Algoritmi rekursiv i gjurmimit prapa është në të vërtetë një kërkim i përgjithshëm që përqendrohet në thellësi. Kur përdoret për gjenerimin e labirintit, modifikohet pak për të zgjedhur rrugën rastësisht, ndërsa nëse përdoret për qëllime kërkimi real, zakonisht do të kërkohet çdo nivel në rend linear. Ai tenton të prodhojë labirinte me korridore të gjata e dredha-dredha dhe një zgjidhje shumë të gjatë e dredha-dredha.

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.

Algoritmi rekursiv i gjurmimit prapa është një metodë kërkimi që vë në dukje thellësinë për të gjeneruar labirinte perfekte (labirinte pa sythe dhe me një shteg të vetëm midis dy pikave). Është i thjeshtë, efikas dhe prodhon labirinte tërheqëse vizualisht me korridore të gjata e dredha-dredha.

Pavarësisht emrit të tij, nuk është e thënë domosdoshmërisht të zbatohet duke përdorur rekursionin. Shpesh zbatohet në një qasje iterative duke përdorur një radhë LIFO (domethënë një pirg). Për labirinte shumë të mëdha, përdorimi i rekursionit ka më shumë të ngjarë të rezultojë në mbingarkesë të pirgut të thirrjeve, varësisht nga gjuha e programimit dhe memoria e disponueshme. Një radhë LIFO mund të përshtatet më lehtë për të trajtuar sasi të mëdha të dhënash, madje duke e mbajtur radhën në disk ose në një bazë të dhënash nëse memoria e disponueshme është e pamjaftueshme.

Si funksionon

Algoritmi funksionon duke përdorur një qasje kërkimi me thellësi të parë bazuar në grumbull. Ja ndarja hap pas hapi:

1. Zgjidhni një qelizë fillestare dhe shënojeni si të vizituar.
2. Ndërsa ka qeliza të pavizituara: Shikoni qelizat fqinje që nuk janë vizituar ende. Nëse ekziston të paktën një fqinj i pavizituar: Zgjidhni rastësisht një nga fqinjët e pavizituar. Hiqni murin midis qelizës aktuale dhe fqinjit të zgjedhur. Lëvizni te fqinji i zgjedhur dhe shënojeni atë si të vizituar. Shtyni qelizën aktuale në grumbull. Nëse nuk ka fqinjë të pavizituar: Kthehuni prapa duke hequr qelizën e fundit nga grumbulli.
3. Vazhdoni këtë proces derisa pirgu të jetë bosh.

Një fakt interesant në lidhje me këtë algoritëm është se ai funksionon si gjenerator labirinti dhe si zgjidhës labirinti. Nëse e ekzekutoni në një labirint të gjeneruar tashmë dhe ndaloni kur të arrini pikën e caktuar të përfundimit, pirgu do të përmbajë zgjidhjen e labirintit.

Në fakt, kam dy versione të këtij algoritmi në lojë në këtë faqe interneti: një të bazuar në radhën LIFO për gjenerimin e labirinteve në këtë faqe dhe një të bazuar në rekursion për zgjidhjen e labirinteve, gjithashtu labirinteve të gjeneruara nga algoritme të tjera (kështu bëhen hartat me zgjidhjet). Të kesh dy versione të ndryshme është vetëm për sport sepse jam një nerd që e gjen interesante, secili mund të kishte funksionuar për të dy ;-)

Lexime të mëtejshme

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

• Gjeneratori i Algoritmit Maze të Uillsonit
• Gjeneratori Maze i Algoritmit të Ellerit
• Gjuani dhe vrisni gjeneratorin e labirintit