Rekurzivni Backtracker Maze Generator

Rekurzivni algoritam povratnog praćenja zapravo je dubinsko pretraživanje opće namjene. Kada se koristi za generiranje labirinta, malo je modificiran da nasumično izabere stazu, dok ako se koristi za stvarne svrhe pretraživanja, obično bi se svaka razina pretraživala linearnim redoslijedom. Nastoji stvoriti labirinte s dugim, zavojitim hodnicima i vrlo dugim, zavojitim 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 labirinta (labirinta bez petlji i jedne staze između bilo koje dvije točke). Jednostavan je, učinkovit i stvara vizualno privlačne labirinte s dugim, zavojitim hodnicima.

Unatoč svom nazivu, ne mora nužno biti implementiran korištenjem rekurzije. Često se implementira u iterativnom pristupu koristeći LIFO red (tj. stog). Za vrlo velike labirinte vjerojatnije je da će korištenje rekurzije rezultirati prekoračenjem stoga poziva, ovisno o programskom jeziku i dostupnoj memoriji. LIFO red čekanja može se lakše prilagoditi rukovanju velikim količinama podataka, čak i zadržavanju reda čekanja na disku ili u bazi podataka ako dostupna memorija nije dovoljna.

Kako to radi

Algoritam radi koristeći pristup pretraživanja u dubinu koji se temelji na hrpu. Evo raščlambe korak po korak:

1. Odaberite početnu ćeliju i označite je kao posjećenu.
2. Iako postoje neposjećene ćelije:
   • Pogledajte susjedne ćelije koje još niste posjetili.
   • Ako postoji barem jedan neposjećeni susjed:
     • Nasumično odaberite jednog od neposjećenih susjeda.
     • Uklonite zid između trenutne ćelije i odabranog susjeda.
     • Prijeđite do odabranog susjeda i označite ga kao posjećenog.
     • Gurnite trenutnu ćeliju na stog.
   • Ako ne postoje neposjećeni susjedi:
     • Vratite se unatrag izbacivanjem posljednje ćelije iz niza.
3. Nastavite s ovim postupkom 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 odabrane krajnje točke, hrpa će sadržavati rješenje labirinta.

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