Recursive Backtracker Maze Generator

Algoritmi rekursiv backtracker është me të vërtetë një kërkim i përgjithshëm i thellësisë së parë. Kur përdoret për gjenerimin e labirinteve, ajo pak e modifikuar për të zgjedhur rrugën në mënyrë të rastësishme, ndërsa nëse përdoret për qëllime reale kërkimi, zakonisht do të kërkonte çdo nivel në rendin linear. Ajo ka tendencë të prodhojë labirinte me korridore të gjata gjarpëruese dhe një zgjidhje shumë të gjatë dhe përdredhëse.

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 backtracker është një metodë kërkimi thellësi-parë për gjenerimin e labirinteve të përsosura (labirintet pa loops dhe një rrugë të vetme midis çdo dy pikash). Është i thjeshtë, i efektshëm dhe prodhon labirinte tërheqëse vizualisht me korridore të gjata gjarpëruese.

Pavarësisht nga emri i saj, ajo nuk duhet domosdoshmërisht të zbatohet duke përdorur rishfaqjen. Ajo shpesh zbatohet në një qasje iterative duke përdorur një rradhë LIFO (d.m.th. një stack). Për labirintet shumë të mëdha, përdorimi i rekursionit ka më shumë gjasa të rezultojë në vërshimin e call stack, në varësi të gjuhës së programimit dhe kujtesës në dispozicion. Një rradhë LIFO mund të përshtatet më lehtë me trajtimin e sasive të mëdha të të dhënave, madje edhe mbajtjen e rradhës në disk ose në një bazë të dhënash nëse memoria në dispozicion është e pamjaftueshme.

Si funksionon?

Algoritmi funksionon duke përdorur një qasje kërkimi të bazuar në thellësinë e parë të stack-it. Ja ku është prishja hap pas hapi:

1. Zgjidhni një qelizë fillestare dhe shënoni atë siç vizitohet.
2. Ndërsa ka qeliza të pavizituara:
   • Shikoni qelizat fqinje që ende nuk janë vizituar.
   • 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.
     • Shko te fqinji i zgjedhur dhe shëno si të vizituar.
     • Shtyjeni qelizën aktuale në stack.
   • Nëse nuk ka fqinjë të pavizituar:
     • Backtrack duke hedhur qelizën e fundit nga stack.
3. Vazhdoni këtë proces derisa grumbulli të jetë bosh.

Një fakt interesant në lidhje me këtë algoritëm është se ai punon si një gjenerator labirinti dhe si një zgjidhës labirinti. Nëse e drejtoni në një labirint tashmë të gjeneruar dhe thjesht ndaloni kur të arrini pikën e fundit të vendosur, stack-u do të përmbajë zgjidhjen e labirintit.

Në fakt kam dy versione të këtij algoritmi në lojë në këtë faqe: një rradhë LIFO e bazuar një për gjenerimin e labirinteve në këtë faqe dhe një rekursion të bazuar në një për zgjidhjen e labirinteve, gjithashtu labirintet e 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 unë jam një nerd që e gjen interesante, ose mund të kishte punuar për të dyja ;-)