Rekurzív Backtracker labirintus generátor

A rekurzív backtracker algoritmus valójában egy általános célú mélységi keresés. Ha labirintus generálására használták, kissé módosult, hogy véletlenszerűen válassza ki az útvonalat, míg ha tényleges keresési célokra használták, általában csak lineáris sorrendben keresnek minden szinten. Hajlamos arra, hogy hosszú, kanyargós folyosókkal és nagyon hosszú, kanyargós megoldású labirintusokat hozzon létre.

A tökéletes labirintus olyan labirintus, amelyben a labirintus bármely pontjából pontosan egy út vezet bármely más pontba. Ez azt jelenti, hogy a végén nem járhatsz körbe-körbe, de gyakran fogsz zsákutcába jutni, ami arra kényszerít, hogy megfordulj és visszamenj.

Az itt generált labirintustérképek tartalmaznak egy alapértelmezett verziót kezdő és végpontok nélkül, így ezeket te magad döntheted el: a labirintus bármely pontjából bármelyik másik pontba el lehet jutni. Ha inspirációra vágysz, engedélyezhetsz egy javasolt kezdő- és célpozíciót - és még a kettő közötti megoldást is láthatod.

A rekurzív backtracker algoritmus egy mélység-első keresési módszer tökéletes labirintusok (hurkok nélküli útvesztők és egyetlen útvonal bármely két pont között) generálására. Egyszerű, hatékony, és látványos labirintusokat hoz létre hosszú, kanyargós folyosókkal.

A neve ellenére nem feltétlenül kell rekurzióval megvalósítani. Gyakran iteratív megközelítésben valósítják meg LIFO-sor (vagyis verem) használatával. Nagyon nagy labirintusok esetén a rekurzió használata nagyobb valószínűséggel eredményez hívásverem túlcsordulást, a programozási nyelvtől és a rendelkezésre álló memóriától függően. A LIFO sor könnyebben adaptálható nagy mennyiségű adat kezelésére, még akkor is, ha a sort a lemezen vagy egy adatbázisban tartja, ha a rendelkezésre álló memória nem elegendő.

Hogyan működik

Az algoritmus verem alapú mélységi keresési megközelítést használ. Íme a lépésről lépésre lebontva:

1. Válasszon ki egy kezdő cellát, és jelölje meg látogatottként.
2. Míg vannak nem látogatott cellák:
   • Nézze meg a szomszédos cellákat, amelyeket még nem látogattak meg.
   • Ha létezik legalább egy nem látogatott szomszéd:
     • Véletlenszerűen válasszon egyet a nem látogatott szomszédok közül.
     • Távolítsa el a falat az aktuális cella és a kiválasztott szomszéd között.
     • Menjen a kiválasztott szomszédhoz, és jelölje meg látogatottként.
     • Tolja az aktuális cellát a veremre.
   • Ha nincsenek meglátogatott szomszédok:
     • Lépjen vissza a verem utolsó cellájának előugrásával.
3. Folytassa ezt a folyamatot, amíg a verem ki nem ürül.

Érdekes tény ezzel az algoritmussal kapcsolatban, hogy labirintusgenerátorként és labirintusmegoldóként is működik. Ha egy már létrehozott labirintuson futtatod, és csak megállsz, amikor eléred a meghatározott végpontot, akkor a verem tartalmazza a labirintus megoldását.

Valójában ennek az algoritmusnak két verziója van ezen az oldalon: egy LIFO-sor alapú útvesztők generálására ezen az oldalon és egy rekurzió alapú labirintusok megoldására, szintén más algoritmusok által generált labirintusok (így készülnek a megoldásokat tartalmazó térképek). A két különböző verzió csak a sportoláshoz való, mert én egy majom vagyok, aki érdekesnek találja, bármelyik működhetett volna mindkettőnél ;-)