Recursive Backtracker Maze Generator

Ang recursive backtracker algorithm ay talagang isang pangkalahatang layunin ng malalim na paghahanap. Kapag ginamit para sa pagbuo ng maze, bahagyang binago ito upang piliin ang landas nang random, samantalang kung ginamit para sa aktwal na mga layunin ng paghahanap, karaniwang hahanapin ng isa ang bawat antas sa linear na pagkakasunud-sunod. Ito ay may posibilidad na gumawa ng mga maze na may mahaba, paikot-ikot na mga koridor at isang napakahaba, paikot-ikot na solusyon.

Ang perpektong maze ay isang maze kung saan mayroong eksaktong isang landas mula sa anumang punto sa maze hanggang sa anumang iba pang punto. Nangangahulugan iyon na hindi ka maaaring maglibot sa mga bilog, ngunit madalas kang makatagpo ng mga patay na dulo, na pinipilit kang tumalikod at bumalik.

Ang mga mapa ng maze na nabuo dito ay may kasamang default na bersyon nang walang anumang mga posisyon sa pagsisimula at pagtatapos, kaya maaari kang magpasya para sa iyong sarili: magkakaroon ng solusyon mula sa anumang punto sa maze hanggang sa anumang iba pang punto. Kung gusto mo ng inspirasyon, maaari mong paganahin ang isang iminungkahing posisyon sa pagsisimula at pagtatapos - at kahit na makita ang solusyon sa pagitan ng dalawa.

Ang recursive backtracker algorithm ay isang pamamaraan ng depth-first search para sa paggawa ng perpektong mga labirinto (mga labirinto na walang mga loop at may isang landas lamang sa pagitan ng dalawang punto). Ito ay simple, epektibo, at nagbubunga ng mga kaakit-akit na labirinto na may mahahabang, paikot-ikot na mga koridor.

Sa kabila ng pangalan nito, hindi kailangang ipatupad gamit ang recursion. Madalas itong ipinatutupad gamit ang isang iterative na pamamaraan gamit ang LIFO queue (i.e. isang stack). Para sa mga labirinto na sobrang laki, ang paggamit ng recursion ay malamang magresulta sa overflow ng call stack, depende sa wika ng pag-programa at available na memorya. Ang LIFO queue ay mas madaling ma-adapt sa paghawak ng malalaking halaga ng data, kahit na itago ang queue sa disk o sa isang database kung hindi sapat ang available na memorya.

Paano Ito Gumagana

Ang algorithm ay gumagana gamit ang isang stack-based na pamamaraan ng depth-first search. Narito ang step-by-step na breakdown:

1. Pumili ng isang starting cell at markahan ito bilang bisitado.
2. Habang may mga hindi pa bisitadong cell:
   • Tingnan ang mga kalapit na cell na hindi pa bisitado.
   • Kung may hindi bababa sa isang hindi pa bisitadong kalapit na cell:
     • Pumili ng random na isa sa mga hindi pa bisitadong kalapit.
     • Alisin ang pader sa pagitan ng kasalukuyang cell at ng napiling kalapit.
     • Lumipat sa napiling kalapit at markahan ito bilang bisitado.
     • I-push ang kasalukuyang cell sa stack.
   • Kung walang mga hindi pa bisitadong kalapit na cell:
     • Mag-backtrack sa pamamagitan ng pag-pop ng huling cell mula sa stack.
3. I-continue ang prosesong ito hanggang ang stack ay maging walang laman.

Isang kawili-wiling katotohanan tungkol sa algorithm na ito ay gumagana ito pareho bilang isang generator ng labirinto at bilang isang solver ng labirinto. Kung patakbuhin mo ito sa isang labirintong na-generate na at tumigil lang kapag narating mo ang pinili mong endpoint, ang stack ay maglalaman ng solusyon sa labirinto.

Mayroon akong dalawang bersyon ng algorithm na ito sa site na ito: isang LIFO queue-based para sa paggawa ng mga labirinto sa pahinang ito at isang recursion-based para sa paglutas ng mga labirinto, pati na rin ang mga labirinto na ginawa ng ibang mga algorithm (ganyan ang paggawa ng mga mapa na may mga solusyon). Ang pagkakaroon ng dalawang magkaibang bersyon ay para lang sa kasiyahan dahil ako ay isang nerd na nakakakita ng interes dito, alinman sa mga ito ay maaaring gumana para sa pareho ;-)