Növekvő fa algoritmus labirintus generátor

A Growing Tree algoritmus azért érdekes, mert képes több más algoritmus viselkedését is utánozni attól függően, hogy a generálás során hogyan választják ki a következő cellát. Az ezen az oldalon található implementáció egy szélesség-első, sor-szerű megközelítést használ.

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 növekvő fa algoritmusáról

A Growing Tree algoritmus egy rugalmas és hatékony módszer tökéletes labirintusok létrehozására. Az algoritmus azért érdekes, mert képes több más labirintusgeneráló algoritmus viselkedését is utánozni, például a Prim algoritmust, a rekurzív visszalépést és a rekurzív osztást, attól függően, hogy hogyan választjuk ki a következő cellát a feldolgozáshoz.

Hogyan működik a növekvő fa algoritmus

1. lépés: Inicializálás

• Kezdj egy meglátogatatlan cellákból álló ráccsal.
• Válasszon ki egy véletlenszerű kezdőcellát, és adja hozzá egy listához.

2. lépés: Labirintusgenerációs hurok

• Amíg a cellalista nem üres: Válassz ki egy cellát a listából egy adott stratégia alapján (lásd alább). Vágj átjárót a kiválasztott cellából az egyik meg nem látogatott szomszédjába (véletlenszerűen kiválasztva). Add hozzá a szomszédot a listához, mivel most már a labirintus része. Ha a kiválasztott cellának nincsenek meg nem látogatott szomszédai, távolítsd el a listából.

3. lépés: Lezárás

• Az algoritmus akkor fejeződik be, amikor már nincsenek cellák a listában, azaz a teljes labirintust kifaragták.

Cellakiválasztási stratégiák (az algoritmus rugalmassága)

A Growing Tree algoritmus meghatározó jellemzője, hogy hogyan választjuk ki, hogy melyik cellát dolgozzuk fel legközelebb. Ez a választás drámaian befolyásolja a labirintus megjelenését:

Legújabb cella (veremszerű viselkedés) – Rekurzív visszalépéskövető:

• Mindig a legutóbb hozzáadott cellát jelölje ki.
• Hosszú, kanyargós folyosókat hoz létre sok zsákutcával (mint egy mélységi keresőlabirintus).
• A labirintusok általában hosszú átjárókkal rendelkeznek, és könnyen megoldhatók.

Véletlenszerű cella (véletlenszerű Prim algoritmusa):

• Minden alkalommal válassz ki egy véletlenszerű cellát a listából.
• Egyenletesebb elosztású labirintust hoz létre összetett, kusza ösvényekkel.
• Kevesebb hosszú folyosó és több elágazás.

Legrégebbi cella (sorszerű viselkedés):

• Mindig a lista legrégebbi celláját válaszd.
• Egyenletesebb eloszlású labirintusokat generál, mint például szélességi keresési minta.
• Rövid, bozótos átjárók sűrű csatlakozásokkal.
• (Ez az itt implementált verzió)

Hibrid megközelítések:

Kombináljon stratégiákat a változatos labirintusjellemzőkhöz. Például:

• 90%-ban legújabb, 10%-ban véletlenszerű: Leginkább egy rekurzív visszafelé haladó labirintusra hasonlít, de alkalmanként elágazik, ami hosszú folyosókat szakít fel.
• 50%-ban legújabb, 50%-ban legidősebb: Hosszú folyosókat bokros növényzettel egyensúlyoz.

További olvasmányok

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

• Eller algoritmus labirintusgenerátora
• Hunt and Kill labirintus generátor
• Rekurzív Backtracker labirintus generátor