Recursive Division

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 jediný ze všech zmíněných algoritmů, který generuje bludiště pouze metodou přidávání hran. Během každého kroku tohoto algoritmu je bludiště platné, pouze se postupně zvyšuje úroveň detailů bludiště. Tento algoritmus však hrany přidává místo toho, aby je mazal. Rekurzivně se v tomto algoritmu půlí plochy a na toto rozdělení se přidá nová stěna. V této stěně se náhodně vybere jedna cesta a vytvoří se. Pro lepší výsledek bludiště je vhodné si zvolit podle vybrané plochy, která může mít větší rozměr na výšku než na šířku a naopak, zda nově vygenerovaná stěna bude horizontální či vertikální. Ve výsledku je algoritmus velice rychlý, protože v jednom kroku se zpracuje několik buněk najednou.

Kroky algoritmu:

  1. Začneme s prázdným bludištěm.
  2. Náhodně rozdělíme bludiště vertikálně či horizontálně a vytvoříme novou dlouhou stěnu a náhodně na ní vytvoříme jednu cestu.
  3. Opakujeme bod 2 s plochami na každé straně stěny.
  4. Rekurzivně pokračujeme do té doby, než projdeme všechny plochy.
Recursive Division

Z obrázku je patrné, že v bludišti existuje mnoho velice dlouhých zdí, a tím je bludiště rozděleno na menší části. Tendence je v tomto bludišti vyrovnaná, avšak existují bludiště, která tento algoritmus nedokáže vygenerovat, a proto není označen jako uniformní. V každém kroku generování je bludiště kompletní, čímž tvoří strom. Paměťová náročnost je v tomto případě vyšší, do paměti je potřeba uložit celý řádek bludiště.

Zdroje:

  1. The Buckblog: Maze Generation: Recursive Division [online]. Jamis Buck, 2011 [cit. 2017-03-02]. Dostupné z: http://weblog.jamisbuck.org/2011/1/12/maze-generation-recursive-division-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.