Miklix

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

Labirintusgenerátor a Növekvő fa algoritmus használatával tökéletes labirintus létrehozásához. Ez az algoritmus a Hunt and Kill algoritmushoz hasonló labirintusokat generál, de némileg eltérő tipikus megoldással.

Ezt az oldalt angolból gépi fordítással készítettük, hogy minél több ember számára elérhető legyen. Sajnos a gépi fordítás még nem tökéletes technológia, ezért előfordulhatnak hibák. Ha szeretné, itt megtekintheti az eredeti angol nyelvű változatot:

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.


Új labirintus létrehozása








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.

Oszd meg a Bluesky-nOszd meg a FacebookonOszd meg a LinkedIn-enOszd meg a Tumblr-enOszd meg X-enOszd meg a LinkedIn-enPin a Pinteresten

Mikkel Bang Christensen

A szerzőről

Mikkel Bang Christensen
Mikkel a miklix.com létrehozója és tulajdonosa. Több mint 20 éves tapasztalattal rendelkezik, mint hivatásos számítógépes programozó/szoftverfejlesztő, és jelenleg teljes munkaidőben dolgozik egy nagy európai informatikai vállalatnál. Amikor nem blogol, szabadidejét érdeklődési körének, hobbijainak és tevékenységeinek széles skálájával tölti, ami bizonyos mértékig tükröződhet a weboldalon tárgyalt témák sokféleségében.