Rekurzivni Backtracker Maze Generator

Rekurzivni algoritem povratnega sledenja je v resnici splošno iskanje v globino. Pri uporabi za generiranje labirintov je nekoliko spremenjen tako, da naključno izbere pot, medtem ko bi pri uporabi za dejansko iskanje običajno iskali vsako raven v linearnem vrstnem redu. Običajno ustvari labirinte z dolgimi, vijugastimi 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 ustvarjanje popolnih labirintov (labirintov brez zank in z eno samo potjo med katerima koli dvema točkama). Je preprost, učinkovit in ustvarja vizualno privlačne labirinte z dolgimi, vijugastimi hodniki.

Kljub imenu ni nujno, da je implementirana z uporabo rekurzije. Pogosto se izvaja z iterativnim pristopom z uporabo čakalne vrste LIFO (tj. sklada). Pri zelo velikih labirintih je večja verjetnost, da bo uporaba rekurzije povzročila preobremenitev sklada klicev, odvisno od programskega jezika in razpoložljivega pomnilnika. Čakalno vrsto LIFO je lažje prilagoditi za obdelavo velikih količin podatkov, celo tako, da se čakalna vrsta ohrani na disku ali v zbirki podatkov, če razpoložljivega pomnilnika ni dovolj.

Kako deluje

Algoritem deluje z uporabo pristopa 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. Dokler obstajajo neobiskane celice: Poglejte sosednje celice, ki še niso bile obiskane. Če obstaja vsaj en neobiskan sosed: Naključno izberite enega od neobiskanih sosedov. Odstranite steno med trenutno celico in izbranim sosedom. 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 iz sklada odstranite zadnjo celico.
3. Nadaljujte s tem postopkom, dokler sklad ni prazen.

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

Na tej strani imam pravzaprav dve različici tega algoritma: različico, ki temelji na čakalni vrsti LIFO za generiranje labirintov na tej strani, in različico, ki temelji na rekurziji, za reševanje labirintov, ki jih generirajo tudi drugi algoritmi (tako so narejeni zemljevidi z rešitvami). Dve različni različici sta samo za šport, ker sem piflar, ki se mi zdi zanimiva, katera koli bi lahko delovala za obe ;-)

Nadaljnje branje

Če vam je bila ta objava všeč, vam bodo morda všeč tudi ti predlogi:

• Generator labirinta Wilsonovega algoritma
• Algoritem rastočega drevesa Generator labirinta
• Generator Labirinta Lov in Ubij