Generátor lovu a zabíjení bludiště

Algoritmus Hunt and Kill je ve skutečnosti upravenou verzí rekurzivního zpětného sledu. Modifikace spočívá v systematickém skenování (neboli „hledání“) nové buňky, od které se pokračuje, když už nemůže jít dál, na rozdíl od skutečného rekurzivního prohledávání, které se vždy vrací k předchozí buňce na zásobníku.

Díky tomu lze tento algoritmus snadno upravit pro generování bludišť s různým vzhledem a dojmem, a to pouhým výběrem častějšího vstupu do režimu „lovu“ nebo podle specifických pravidel. Zde implementovaná verze přejde do režimu „lovu“ pouze tehdy, když se nemůže dostat 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 Hunt and Kill

Algoritmus Hunt and Kill je jednoduchá, ale efektivní metoda pro generování bludišť. Je do jisté míry podobný prohledávání do hloubky (tj. algoritmu Recursive Backtracker), až na to, že když se nemůže dostat dále od aktuální pozice, systematicky prohledává (neboli „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 lovu.

Jak funguje algoritmus Hunt and Kill pro generování bludiště

Krok 1: Začněte v náhodné buňce

• Najděte v mřížce náhodnou buňku 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íveného souseda.
• Přesuňte se k tomuto sousedovi, označte ho jako navštíveného 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í pomocí skenování)

• Prohledejte 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.
• Pro obnovení fáze chůze připojte danou buňku k navštívenému sousedovi.
• Opakujte, dokud nebudou navštíveny všechny buňky.

Další čtení

Pokud se vám tento příspěvek líbil, mohly by se vám líbit i tyto návrhy:

• Wilsonův Algorithm Maze Generator
• Ellerův algoritmus bludiště generátor
• Kruskalův Algorithm Maze Generator