Hunt and Kill labirintus generátor
Megjelent: 2025. február 16. 20:54:22 UTC
Labirintusgenerátor a Hunt and Kill algoritmus segítségével tökéletes labirintus létrehozásához. Ez az algoritmus hasonló a Rekurzív Backtrackerhez, de általában valamivel kevésbé hosszú, kanyargós folyosókkal rendelkező labirintusokat generál.Hunt and Kill Maze Generator
A Hunt and Kill algoritmus valójában a Recursive Backtracker módosított változata. A módosítás egy új cella szisztematikus kereséséből (vagy "vadászatából") áll, hogy folytassa, amikor már nem tud továbbmenni, szemben a valódi rekurzív kereséssel, amely mindig visszamegy a verem előző cellájába.
Emiatt ez az algoritmus könnyen adaptálható különböző megjelenésű és érzetű labirintusok létrehozására, csupán a „vadászat” módba való gyakrabban történő belépéssel vagy meghatározott szabályok szerint. Az itt megvalósított verzió csak akkor lép "vadászat" módba, ha nem tud továbbmenni az aktuális cellátó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 Hunt and Kill algoritmusról
A Hunt and Kill algoritmus egy egyszerű, de hatékony módszer labirintusok létrehozására. Ez némileg hasonlít a mélységi kereséshez (azaz a Rekurzív Backtracker algoritmushoz), kivéve, ha nem tud tovább menni az aktuális pozíciótól, szisztematikusan átkutatja (vagy "vadász") a labirintuson, hogy új cellát találjon a továbblépéshez. Az algoritmus két fő fázisból áll: séta és vadászat.
Hogyan működik a Hunt and Kill algoritmus a labirintusgenerációban
1. lépés: Kezdje egy véletlenszerű cellával
- Keressen egy véletlenszerű cellát a rácsban, és jelölje meg látogatottként.
2. lépés: Séta fázis (véletlenszerű séta)
- Válasszon egy véletlenszerűen nem látogatott szomszédot.
- Lépjen a szomszédhoz, jelölje meg látogatottként, és vágjon útvonalat az előző és az új cella közé.
- Addig ismételje, amíg nem marad meglátogatott szomszéd.
3. lépés: Vadászat fázis (visszakövetés szkenneléssel)
- Olvassa be a rácsot soronként (vagy oszloponként).
- Keresse meg az első nem látogatott cellát, amelynek legalább egy szomszédja van.
- Csatlakoztassa azt a cellát egy meglátogatott szomszédhoz a járási szakasz folytatásához.
- Ismételje meg mindaddig, amíg az összes cellát meg nem látogatta.