Rekurzivni Backtracker Maze Generator

Rekurzivni algoritam backtrackera je zapravo pretraga u dubinu opće namjene. Kada se koristi za generisanje lavirinta, neznatno je modifikovan da bira putanju nasumično, dok ako se koristi u stvarne svrhe pretraživanja, obično bi se samo pretraživao svaki nivo u linearnom redosledu. Ima tendenciju da proizvodi labirinte sa dugim, krivudavim hodnicima i veoma dugim, uvrnutim rešenjem.

Savršen labirint je labirint u kojem postoji tačno jedan put od bilo koje tačke u labirintu do bilo koje druge tačke. To znači da ne možete završiti u krugu, ali ćete često nailaziti na slijepe ulice, prisiljavajući vas da se okrenete i vratite.

Mape lavirinta koje se ovdje generiraju uključuju zadanu verziju bez ikakvih početnih i završnih pozicija, tako da ih možete sami odlučiti: postojat će rješenje od bilo koje točke u lavirintu do bilo koje druge točke. Ako želite inspiraciju, možete omogućiti predloženi početni i ciljni položaj - pa čak i vidjeti rješenje između njih.

Rekurzivni algoritam backtrackera je metoda pretraživanja u dubinu za generiranje savršenih lavirinta (labirinta bez petlji i jedne putanje između bilo koje dvije točke). Jednostavan je, efikasan i stvara vizuelno privlačne lavirinte sa dugim, krivudavim hodnicima.

Uprkos svom imenu, ne mora nužno biti implementiran pomoću rekurzije. Često se implementira u iterativnom pristupu koristeći LIFO red (tj. stek). Za vrlo velike lavirinte, korištenje rekurzije će vjerojatnije dovesti do prekoračenja steka poziva, ovisno o programskom jeziku i raspoloživoj memoriji. LIFO red se može lakše prilagoditi za rukovanje velikim količinama podataka, čak i čuvanje reda na disku ili u bazi podataka ako je raspoloživa memorija nedovoljna.

Kako radi

Algoritam radi koristeći pristup pretrazi u dubinu zasnovan na steku. Evo detaljne analize korak po korak:

1. Odaberite početnu ćeliju i označite je kao posjećenu.
2. Dok postoje neposjećene ćelije:
   • Pogledajte susjedne ćelije koje još nisu posjećene.
   • Ako postoji barem jedan neposjećeni susjed:
     • Nasumično odaberite jednog od neposjećenih susjeda.
     • Uklonite zid između trenutne ćelije i izabranog susjeda.
     • Premjestite se na izabranog susjeda i označite ga kao posjećenog.
     • Gurnite trenutnu ćeliju na stog.
   • Ako nema neposjećenih susjeda:
     • Vratite se tako što ćete iskočiti posljednju ćeliju iz hrpe.
3. Nastavite sa ovim procesom dok se stog ne isprazni.

Zanimljiva činjenica o ovom algoritmu je da radi i kao generator lavirinta i kao rješavač lavirinta. Ako ga pokrenete na već generiranom lavirintu i samo se zaustavite kada dođete do određene krajnje točke, stek će sadržavati rješenje za labirint.

Zapravo imam dvije verzije ovog algoritma u igri na ovoj stranici: onu baziranu na LIFO redu za generiranje lavirinta na ovoj stranici i onu zasnovanu na rekurziji za rješavanje lavirinta, također lavirinta generiranih od strane drugih algoritama (tako se prave karte sa rješenjima). Imati dvije različite verzije je samo za sport jer sam štreber kome je to zanimljivo, i jedna i druga bi mogla raditi za obje ;-)