Rekurzív Backtracker labirintus generátor

A rekurzív visszakövető algoritmus valójában egy általános célú mélységi keresés. Labirintus generálásához kissé módosul, hogy véletlenszerűen válassza ki az útvonalat, míg ha tényleges keresési célokra használjuk, jellemzően csak lineáris sorrendben keressük át az egyes szinteket. Általában hosszú, kanyargós folyosókkal és nagyon hosszú, csavarodó megoldással rendelkező labirintusokat hoz 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.

Rekurzív visszakövető algoritmus egy mélységi keresési módszer tökéletes labirintusok (hurkok nélküli labirintusok, amelyek között bármely két pont között egyetlen út vezet) létrehozására. Egyszerű, hatékony, és vizuálisan vonzó 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éssel valósítják meg LIFO sor (azaz egy verem) használatával. Nagyon nagy labirintusok esetén a rekurzió használata nagyobb valószínűséggel okoz 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, akár lemezen vagy adatbázisban is tarthatja a sort, ha nincs elegendő rendelkezésre álló memória.

Hogyan működik

Az algoritmus egy veremalapú mélységi keresési megközelítéssel működik. Íme a lépésenkénti lebontás:

1. Válasszon ki egy kezdőcellát, és jelölje meg látogatottként.
2. Amíg vannak meg nem látogatott cellák: Nézd meg a még meg nem látogatott szomszédos cellákat. Ha létezik legalább egy meg nem látogatott szomszéd: Véletlenszerűen válassz ki egyet a meg nem látogatott szomszédok közül. Távolítsd el a falat az aktuális cella és a kiválasztott szomszéd között. Lépj a kiválasztott szomszédra, és jelöld meg meglátogatottként. Helyezd az aktuális cellát a veremre. Ha nincsenek meg nem látogatott szomszédok: Lépj vissza az utolsó cella kiemelésével a veremből.
3. Folytasd ezt a folyamatot, amíg a kupac ki nem ürül.

Ennek az algoritmusnak egy érdekessége, hogy labirintusgenerátorként és labirintusmegoldóként is működik. Ha egy már létrehozott labirintuson futtatod, és csak a megadott végpontnál állsz meg, a verem tartalmazza a labirintus megoldását.

Ennek az algoritmusnak két verziója van futtatva ezen az oldalon: egy LIFO soron alapuló labirintusok generálására ezen az oldalon, és egy rekurzión alapuló labirintusok megoldására, amelyeket más algoritmusok generálnak (így készülnek a megoldásokat tartalmazó térképek). A két különböző verzió csak a sport miatt van, mert én egy stréber vagyok, aki érdekesnek találja, bármelyik működhetett volna mindkettőnél ;-)

További olvasmányok

Ha tetszett ez a bejegyzés, akkor ezek a javaslatok is érdekelhetik:

• Hunt and Kill labirintus generátor
• Növekvő fa algoritmus labirintus generátor
• Wilson algoritmus labirintus generátor