Hunt and kill

Rychlost generování:

Rozlišení bludiště:


Slepé uličky:

Zatáčky:

Křižovatky:

       - Trojsměrné:

       - Čtyřsměrné:

Rovinky:

       - Horizontální:

       - Vertikální:

Nejdelší cesta:

Složitost nejdelší cesty:


Popis algoritmu

Tento algoritmus je velice podobný algoritmu Recursive-Backtracker. Rozdíl přichází v momentě, kdy neexistují žádné buňky, na které bychom mohli vstoupit. V tu chvíli se spustí tzv. sken, který hledá novou výchozí buňku. Použitím tohoto algoritmu dochází daleko méně k vytváření dlouhých slepých cest. Pokud bychom sken volali častěji, nejenom v momentě, kdy neexistují žádné buňky, na které bychom mohli vstoupit, dlouhé slepé cesty bychom podstatně eliminovali. V tomto případě nepotřebujeme žádnou další paměť nebo zásobník pro uložení dat. Proto je tento algoritmus vhodný pro vytváření bludišť s většími rozměry.

Kroky algoritmu:

  1. Náhodně si zvolíme výchozí buňku.
  2. Z této buňky začneme náhodně procházet bludiště po nenavštívených buňkách do té doby, než výchozí buňka nebude mít žádné nenavštívené sousedy. Mezi těmito buňkami vymažeme hrany.
  3. Nyní začneme skenovat bludiště. Tento sken hledá nenavštívené buňky, které mají souseda, který již byl navštíven. Pokud najdeme takovou buňku, vytvoříme cestu mezi těmito buňkami. Zároveň se tato buňka stane novou výchozí buňkou.
  4. 4. Opakujeme bod 2 a 3 do té doby, než nezbydou žádné nenavštívené buňky.
Hunt and Kill

Tento algoritmus má velice podobné vlastnosti jako algoritmus Recursive Backtracker. V každém kroku vytváření bludiště se tvoří strom, lze ho použít na vytváření bludišť pouze metodou odstraňováním hran, vytváří bludiště, která nemají tendenci k žádnému sklonu buněk a za žádných okolností ho nejde označit jako uniformní. Rozdíl je zde však v paměťové náročnosti, kdy je při použití tohoto algoritmu potřeba uložit do paměti pouze mapu bludiště a aktuální buňku.

Z obrázku je patrné, že tato bludiště obsahují velice dlouhé nejdelší cesty. Algoritmy Recursive Backtracker a Hunt and Kill jsou jedinými ze všech ostatních algoritmů, které mohou vytvářet bludiště pouze metodou odstraňováním hran.

Zdroje:

  1. The Buckblog: Maze Generation: Hunt-and-Kill algorithm [online]. Jamis Buck, 2011 [cit. 2017-03-02]. Dostupné z: http://weblog.jamisbuck.org/2011/1/24/maze-generation-hunt-and-kill-algorithm.html
  2. Astrolog: Think Labyrinth: Maze Algorithms [online]. Walter D. Pullen, 2015 [cit. 2017-03-02]. Dostupné z: http://www.astrolog.org/labyrnth/algrithm.htm
  3. Algorithm" is Not a Four-Letter Word [online]. Jamis Buck, 2011 [cit. 2017-03-02]. Dostupné z: http://www.jamisbuck.org/presentations/rubyconf2011/index.html
  4. BUCK, Jamis, CARTER, Jacquelyn, ed. Mazes for Programmers: Code Your Own Twisty Little Passages. 1. Raleigh (North Carolina): The Pragmatic Bookshelf, 2015. ISBN 9781680500554.