Növekvő fa algoritmus labirintus generátor

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.