Generátor lovu a zabíjení bludiště
Vydáno: 16. února 2025 v 20:51:50 UTC
Generátor bludiště pomocí algoritmu Hunt and Kill k vytvoření dokonalého bludiště. Tento algoritmus je podobný Rekurzivnímu Backtrackeru, ale má tendenci vytvářet bludiště s poněkud méně dlouhými, klikatými chodbami.Hunt and Kill Maze Generator
Algoritmus Hunt and Kill je ve skutečnosti upravená verze rekurzivního backtrackeru. Modifikace spočívá v systematickém skenování (nebo "lovu") pro novou buňku, aby pokračovala od chvíle, kdy už nemůže jít dále, na rozdíl od skutečného rekurzivního vyhledávání, které se vždy vrátí k předchozí buňce v zásobníku.
Z tohoto důvodu lze tento algoritmus snadno upravit tak, aby generoval bludiště s odlišným vzhledem a dojmem, a to pouhým zvolením častějšího vstupu do režimu „lov“ nebo podle specifických pravidel. Zde implementovaná verze vstoupí do „loveckého“ režimu pouze tehdy, když nemůže jít dále od aktuální buňky.
Dokonalé bludiště je bludiště, ve kterém existuje přesně jedna cesta z kteréhokoli bodu bludiště do kteréhokoli jiného bodu. To znamená, že nemůžete skončit v kruhu, ale často narazíte na slepé uličky, které vás donutí se otočit a vrátit se zpět.
Zde vygenerované mapy bludiště obsahují výchozí verzi bez počátečních a cílových pozic, takže si je můžete určit sami: z jakéhokoli bodu v bludišti do jakéhokoli jiného bodu existuje řešení. Pokud se chcete inspirovat, můžete zapnout navrhovanou startovní a cílovou pozici - a dokonce si prohlédnout řešení mezi nimi.
O algoritmu lovu a zabíjení
Algoritmus Hunt and Kill je jednoduchá, ale účinná metoda pro generování bludišť. Je to do jisté míry podobné prohledávání do hloubky (tj. algoritmu Recursive Backtracker), až na to, že když nemůže jít dále od aktuální pozice, systematicky prohledává (nebo „loví“) bludiště, aby našel novou buňku, ze které by mohl pokračovat. Algoritmus se skládá ze dvou hlavních fází: chůze a lov.
Jak funguje algoritmus lovu a zabíjení pro generování bludišť
Krok 1: Začněte v náhodné buňce
- Najděte náhodnou buňku v mřížce a označte ji jako navštívenou.
Krok 2: Fáze chůze (náhodná chůze)
- Vyberte si náhodného nenavštěvovaného souseda.
- Přesuňte se k tomuto sousedovi, označte jej jako navštívený a vytvořte cestu mezi předchozí a novou buňkou.
- Opakujte, dokud nezůstanou žádní nenavštívení sousedé.
Krok 3: Fáze lovu (zpětné sledování prostřednictvím skenování)
- Naskenujte mřížku řádek po řádku (nebo sloupec po sloupci).
- Najděte první nenavštívenou buňku, která má alespoň jednoho navštíveného souseda.
- Připojte tuto buňku k navštíveného souseda a obnovte fázi chůze.
- Opakujte, dokud nebudou navštíveny všechny buňky.