Növekvő fa algoritmus labirintus generátor
Megjelent: 2025. február 16. 21:36:24 UTC
Utolsó frissítés: 2025. március 6. 9:55:39 UTC
Growing Tree Algorithm Maze Generator
A Növekvő fa algoritmus azért érdekes, mert több más algoritmus viselkedését is képes emulálni, 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ó megvalósítás szélesség-első, sorszerű megközelítést alkalmaz.
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 Növekvő fa algoritmus egy rugalmas és hatékony módszer a tökéletes labirintusok létrehozására. Az algoritmus azért érdekes, mert képes emulálni számos más labirintusgeneráló algoritmus viselkedését, például a Prim algoritmusát, a rekurzív visszalépést és a rekurzív osztást, attól függően, hogy hogyan választja ki a következő feldolgozandó cellát.
Hogyan működik a Növekvő fa algoritmusa
1. lépés: Inicializálás
- Kezdje a nem látogatott cellák rácsával.
- Válasszon ki egy véletlenszerű kezdő cellát, és adja hozzá a listához.
2. lépés: Labirintusgenerációs hurok
- Amíg a cellalista nem üres:
- Válasszon ki egy cellát a listából egy adott stratégia alapján (lásd alább).
- Vágjon át egy átjárót a kiválasztott cellából az egyik (véletlenszerűen kiválasztott) nem látogatott szomszédhoz.
- Adja hozzá a szomszédot a listához, mivel az immár a labirintus része.
- Ha a kijelölt cellának nincsenek meglátogatott szomszédai, távolítsa el a listából.
3. lépés: Felmondás
- Az algoritmus akkor fejeződik be, amikor már nincs több cella a listában, vagyis az egész labirintus ki lett vésve.
Sejtkiválasztási stratégiák (az algoritmus rugalmassága)
A Növekvő fa algoritmus meghatározó jellemzője az, hogy hogyan választja ki, melyik cellát kívánja feldolgozni legközelebb. Ez a választás drámaian befolyásolja a labirintus megjelenését:
Legújabb cella (veremszerű viselkedés) – Rekurzív Backtracker:
- Mindig a legutóbb hozzáadott cellát válassza ki.
- Hosszú, kanyargós folyosókat hoz létre sok zsákutcával (mint például egy mélység-első keresési labirintus).
- Az útvesztők általában hosszú átjárókkal rendelkeznek, és könnyen megoldhatók.
Véletlenszerű cella (Véletlenszerű prim algoritmusa):
- Minden alkalommal válasszon egy véletlenszerű cellát a listából.
- Egyenletesebben elosztott labirintust hoz létre összetett, kusza utakkal.
- Kevesebb hosszú folyosó és több elágazás.
Legrégebbi cella (sorszerű viselkedés):
- Mindig a legrégebbi cellát válassza a listából.
- Egyenletesebb elterjedésű labirintusokat hoz létre, mint például a szélesség-első keresési minta.
- Rövid, bokros átjárók sűrű kapcsolatokkal.
- (Ez az itt megvalósított verzió)
Hibrid megközelítések:
A különböző labirintus-jellemzők stratégiáinak kombinálása. Például:
- 90% legújabb, 10% véletlenszerű: többnyire úgy néz ki, mint egy rekurzív backtracker labirintus, de időnként hosszú folyosókat szakító ágakkal.
- 50% legújabb, 50% legrégebbi: Kiegyensúlyozza a hosszú folyosókat a bokros növekedéssel.