Growing 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 má několik možností, jak bude výsledné bludiště vypadat. Tato zajímavost je docílena tím, že si uživatel může nastavit, které buňky se během generování budou vybírat s různou pravděpodobností. V momentě, kdy se vytvoří nová buňka bludiště, uloží se do kolekce a z této kolekce se poté vybírá buňka, ze které bude generování pokračovat. První možností je, že se z kolekce vybere buňka, která byla do kolekce přidaná jako poslední. Tato varianta poté generuje bludiště stejným způsobem jako algoritmus Recursive Backtracker. V případě výběru buňky náhodně algoritmus pracuje jako Primův algoritmus. Poslední samostatnou možností je výběr buňky, která byla vložena do kolekce jako první. Tato možnost generuje bludiště s velice dlouhými cestami bez zatáček. Proto se pro lepší výsledky bludiště využívají kombinace těchto zmíněných možností. První kombinací je rovnoměrná šance mezi výběrem nové nebo náhodné buňky z kolekce. Druhou kombinací je výběr mezi novou a nejstarší buňkou přidanou do kolekce.

Kroky algoritmu:

  1. Náhodně vybereme buňku z bludiště a vložíme ji do kolekce.
  2. Zvolíme buňku z kolekce jakýmkoliv zmíněným způsobem (nová, náhodná, stará, kombinace). Z této buňky se náhodně vygeneruje cesta směrem, kde se nenachází nenavštívená buňka. Tuto buňku také přidáme do kolekce. V případě že buňka v kolekci již neobsahuje žádné nenavštívené buňky, odstraníme ji z kolekce.
  3. Opakujeme bod 2 do té doby, než kolekce bude prázdná.
Growing Tree

Na obrázku je zobrazená jedna z možných variant tohoto algoritmu, kdy při generování je stejná pravděpodobnost pro výběr nově přidané buňky a náhodné buňky. Jak už název algoritmu napovídá, při generování se tedy tvoří strom a lze ho využít pro obě metody vytváření bludišť. Žádné tendence na výsledném bludišti nenalezneme, avšak nemůžeme ho označit za zcela uniformní, protože všechna možná bludiště nemají stejnou pravděpodobnost při generování. Do paměti si je potřeba uložit všechny buňky bludiště, proto je paměťová náročnost použití algoritmu vysoká.

Existuje zde také další varianta tohoto algoritmu s názvem Growing Binary Tree. V tomto případě se místo přidání jedné nové buňky přidávají rovnou dvě. Opět je zde několik modifikací s jakou pravděpodobností se přidají určité buňky. Vlastnosti tohoto algoritmu jsou však totožné s algoritmem Growing Tree.

Zdroje:

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