Rekurzivni Backtracker Maze Generator

Rekurzivni algoritam za praćenje unatrag je zapravo opća pretraga u dubinu. Kada se koristi za generiranje lavirinata, neznatno se modificira kako bi se put birao nasumično, dok bi se u stvarne svrhe pretrage obično pretraživao svaki nivo linearnim redoslijedom. Obično proizvodi lavirinte s dugim, krivudavim hodnicima i vrlo dugim, vijugavim rješ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 za praćenje unatrag je metoda pretraživanja u dubinu za generiranje savršenih lavirinata (labirinta bez petlji i s jednim putem između bilo koje dvije tačke). Jednostavan je, efikasan i proizvodi vizualno privlačne lavirinte s dugim, krivudavim hodnicima.

Uprkos svom nazivu, ne mora nužno biti implementiran korištenjem rekurzije. Često se implementira iterativnim pristupom korištenjem LIFO reda (tj. steka). Za vrlo velike labirinte, korištenje rekurzije će vjerovatnije rezultirati prepunjavanjem steka poziva, ovisno o programskom jeziku i dostupnoj memoriji. LIFO red se lakše može prilagoditi za rukovanje velikim količinama podataka, čak i zadržavanjem reda na disku ili u bazi podataka ako nema dovoljno dostupne memorije.

Kako funkcioniše

Algoritam funkcioniše koristeći pristup pretrage u dubinu zasnovan na steku. Evo detaljnog opisa:

1. Odaberite početnu ćeliju i označite je kao posjećenu.
2. Dok postoje neposjećene ćelije: Pregledajte 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 odabranog susjeda. Pomaknite se do odabranog susjeda i označite ga kao posjećenog. Premjestite trenutnu ćeliju na stek. Ako ne postoje neposjećeni susjedi: Vratite se unatrag uklanjanjem posljednje ćelije sa steka.
3. Nastavite ovaj postupak dok se stek 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 zaustavite se kada dođete do određene krajnje tačke, stek će sadržavati rješenje lavirinta.

Zapravo imam dvije verzije ovog algoritma koje se koriste na ovoj stranici: onu zasnovanu na LIFO redu čekanja za generiranje labirinata na ovoj stranici i onu zasnovanu na rekurziji za rješavanje labirinata, također labirinata generiranih drugim algoritmima (tako se prave mape s rješenjima). Posjedovanje dvije različite verzije je samo za sport jer sam štreber kojem je to zanimljivo, bilo koja je mogla funkcionirati za obje ;-)

Dodatno čitanje

Ako vam se svidio ovaj post, možda će vam se svidjeti i ovi prijedlozi:

• Generator labirinta algoritama za uzgoj drveća
• Generator Labirinta Algoritma Eller
• Kruskalov algoritam Generator labirinta