Sidewinger

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 představuje složitější verzi Binary Tree algoritmu. Pro generování bludiště je zde potřeba si do paměti vždy uložit pouze jeden řádek bludiště. Výsledkem je tedy algoritmus velice paměťově nenáročný. Z každé buňky v takto vygenerovaném bludišti vede právě jedna cesta směrem nahoru až k prvnímu řádku bludiště. V takovémto bludišti nemůže existovat jeden typ buněk, a to slepé uličky se vchodem dolů. Bylo by to v rozporu právě s tím, že z každé buňky se generuje cesta k prvnímu řádku bludiště.

Kroky algoritmu:

  1. Postupně projdeme všechny řádky, nejprve však vyprázdníme první řádek.
  2. Na dalším řádku uložíme první buňku do množiny.
  3. Pro aktuální buňku, náhodně vybereme, zda uděláme cestu na východ nebo ne.
  4. Pokud jsme vytvořili cestu, nová buňka se stane aktuální a opakujeme body 2 a 3.
  5. Pokud jsme cestu nevytvořili, náhodně vybereme jednu buňku z množiny a vytvoříme na této buňce cestu na sever. Poté množinu vyprázdníme a uložíme do něj následující buňku a opakujeme body 2 – 5.
Sidewinger

Tento algoritmus má většinu totožných vlastností jako algoritmus Binary Tree. Během generování bludiště se buňky ukládají do množiny a až na konci generování utvoří strom. Lze ho použít pro vytváření bludišť metodami odstraňováním i přidáváním hran. Vytváří bludiště, která mají tendenci ke sklonu buněk, a proto ho nelze označit za uniformní. Paměťová náročnost je také stejná, protože je potřeba pracovat pouze s jednou aktuální buňkou. Z obrázku 9 je však patrný rozdíl oproti bludišti, které bylo vytvořeno použitím algoritmu Binary Tree. Z vyznačené nejdelší cesty je vidět tendence tohoto bludiště. Ve většině případů je začátek nejdelší cesty umístěn v levém spodním rohu, cesta pokračuje přes vrchní řady a poté končí v pravém dolním rohu bludiště.

Zdroje:

  1. The Buckblog: Maze Generation: Sidewinder algorithm [online]. Jamis Buck, 2011 [cit. 2017-03-02]. Dostupné z: http://weblog.jamisbuck.org/2011/2/3/maze-generation-sidewinder-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.