Binary Tree

Rychlost generování:

Rozlišení bludiště:

Zvolte typ algoritmu:


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 jedním z nejzákladnějších a nejjednodušších algoritmů pro generování bludišť. Jako jediný dokáže generovat bludiště s použitím pouze jedné buňky v daném kroku. To má za následek velice rychlé generování a malou paměťovou náročnost. Existují zde čtyři možné varianty použití tohoto algoritmu, kdy si uživatel může vybrat směr výsledného bludiště. Možnosti algoritmu jsou: severní a západní cesta (North-West), severní a východní cesta (North-East), jižní a západní cesta (South-West) a jižní a východní cesta (South-East).

Na každé buňce se náhodně vybere, zda se vytvoří cesta z možností, které si uživatel vybral. Vedlejším efektem tohoto algoritmu je velice nakloněný směr výsledného bludiště. Také zde budou existovat dvě dlouhé cesty podél stran. Umístění těchto dlouhých cest je opět závislé na variantě algoritmu.

Kroky algoritmu:

  1. Zvolíme si buňku se souřadnicemi (0,0), můžeme však buňku vybrat i náhodně.
  2. Dle směru generování náhodně vybereme jeden směr, kudy se vytvoří cesta, a přejdeme na další buňku.
  3. Opakujeme bod 2 do té doby, než projdeme všechny buňky v bludišti.
Binary Tree

Rozdíl mezi tímto algoritmem a předešlými algoritmy je ten, že při generování se netvoří strom. Buňky se ukládají do množiny, která až po vygenerování bludiště utvoří strom. Z obrázku 8 je patrná tendence bludiště jedním směrem. Z toho vyplývá, že tento algoritmus ani není schopný některá bludiště vygenerovat, a proto ho nemůžeme označit za uniformní. Dle kroků algoritmu si je do paměti potřeba uložit vždy pouze jednu buňku, tím pádem je použití tohoto algoritmu velice paměťově nenáročné. Je zde možné také využít jak variantu přidávání, tak i odebírání hran.

Zdroje:

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