Rekurzivni Backtracker Maze Generator

Rekurzivni algoritem za sledenje nazaj je v resnici splošno iskanje v globino. Ko se uporablja za ustvarjanje labirinta, je nekoliko spremenjen, da naključno izbere pot, medtem ko, če se uporablja za namene dejanskega iskanja, bi običajno iskali vsako raven v linearnem vrstnem redu. Nagnjen je k ustvarjanju labirintov z dolgimi, zavitimi hodniki in zelo dolgo, zavito rešitvijo.

Popoln labirint je labirint, v katerem obstaja natanko ena pot od katere koli točke v labirintu do katere koli druge točke. To pomeni, da se ne morete vrteti v krogu, vendar boste pogosto naleteli na slepe ulice, zaradi česar se boste morali obrniti in vrniti nazaj.

Tukaj ustvarjeni zemljevidi labirintov vključujejo privzeto različico brez začetnih in končnih položajev, tako da jih lahko določite sami: iz katere koli točke v labirintu do katere koli druge točke obstaja rešitev. Če želite navdih, lahko omogočite predlagana začetni in končni položaj - in si celo ogledate rešitev med njima.

Rekurzivni algoritem povratnega sledenja je metoda iskanja v globino za generiranje popolnih labirintov (labirintov brez zank in ene same poti med katerima koli dvema točkama). Je preprost, učinkovit in ustvarja vizualno privlačne labirinte z dolgimi vijugastimi hodniki.

Kljub svojemu imenu ni nujno, da je implementiran z uporabo rekurzije. Pogosto se izvaja v iterativnem pristopu z uporabo čakalne vrste LIFO (tj. sklada). Pri zelo velikih labirintih je verjetneje, da bo uporaba rekurzije povzročila prepolnitev sklada klicev, odvisno od programskega jezika in razpoložljivega pomnilnika. Čakalno vrsto LIFO je mogoče lažje prilagoditi za obdelavo velikih količin podatkov, celo ohraniti čakalno vrsto na disku ali v bazi podatkov, če razpoložljivega pomnilnika ni dovolj.

Kako deluje

Algoritem deluje s pristopom iskanja v globino, ki temelji na skladu. Tukaj je razčlenitev po korakih:

1. Izberite začetno celico in jo označite kot obiskano.
2. Čeprav obstajajo neobiskane celice:
   • Oglejte si sosednje celice, ki še niso bile obiskane.
   • Če obstaja vsaj en neobiskani sosed:
     • Naključno izberite enega od neobiskanih sosedov.
     • Odstranite steno med trenutno celico in izbrano sosedo.
     • Premaknite se do izbranega soseda in ga označite kot obiskanega.
     • Potisnite trenutno celico na sklad.
   • Če ni neobiskanih sosedov:
     • Vrnite se nazaj tako, da odstranite zadnjo celico iz sklada.
3. Nadaljujte s tem postopkom, dokler sklad ni prazen.

Zanimivo dejstvo o tem algoritmu je, da deluje kot generator labirintov in kot reševalec labirintov. Če ga zaženete na že ustvarjenem labirintu in se ustavite, ko dosežete izbrano končno točko, bo sklad vseboval rešitev labirinta.

Pravzaprav imam na tej strani v igri dve različici tega algoritma: LIFO, ki temelji na čakalni vrsti za generiranje labirintov na tej strani, in rekurzivno, ki temelji na reševanju labirintov, tudi labirintov, ki jih generirajo drugi algoritmi (tako so narejeni zemljevidi z rešitvami). Imeti dve različni različici je samo za šport, ker sem piflar, ki se mu zdi zanimivo, katera koli bi lahko delovala za obe ;-)