Rekurzivni Backtracker Maze Generator

Rekurzivni algoritam povratnog praćenja zapravo je opća pretraga u dubinu. Kada se koristi za generiranje labirinta, malo se modificira kako bi se put birao nasumično, dok bi se u stvarne svrhe pretraživanja obično pretraživala svaka razina linearnim redoslijedom. Obično stvara labirinte s dugim, vijugavim hodnicima i vrlo dugim, vijugavim rješenjem.

Savršen labirint je labirint u kojem postoji točno jedan put od bilo koje točke u labirintu do bilo koje druge točke. To znači da se ne možete vrtjeti u krug, ali ćete često naići na slijepe ulice, zbog čega ćete se morati okrenuti i vratiti.

Ovdje generirane karte labirinta 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 labirintu do bilo koje druge točke. Ako želite inspiraciju, možete omogućiti predloženu početnu i ciljnu poziciju - pa čak i vidjeti rješenje između ta dva.

Rekurzivni algoritam povratnog praćenja je metoda pretraživanja u dubinu za generiranje savršenih labirinata (labirinta bez petlji i s jednim putem između bilo koje dvije točke). Jednostavan je, učinkovit i stvara vizualno privlačne labirinte s dugim, vijugavim hodnicima.

Unatoč nazivu, ne mora nužno biti implementiran pomoću rekurzije. Često se implementira iterativnim pristupom korištenjem LIFO reda (tj. stoga). Za vrlo velike labirinte, korištenje rekurzije vjerojatnije će rezultirati prepunjavanjem stoga 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 funkcionira

Algoritam radi koristeći pristup pretraživanja u dubinu temeljen na stogu. Evo detaljnog opisa:

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 odabranog susjeda. Pomaknite se do odabranog susjeda i označite ga kao posjećenog. Stavite trenutnu ćeliju na stog. Ako ne postoje neposjećeni susjedi: Vratite se natrag uklanjanjem posljednje ćelije iz stoga.
3. Nastavite ovaj postupak dok se stog ne isprazni.

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

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

Dodatno čitanje

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

• Generator labirinta Wilsonovog algoritma
• Generator Labirinta Lov i Ubijanje
• Algoritam rastućeg stabla Generator labirinta