Recursive backtracker

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 spjat s algoritmem prohledávání do hloubky, který prochází bludiště a hledá v něm cesty. Náhodně se vybere jedna buňka, od které začne procházení. Všechny buňky se při procházení postupně ukládají do zásobníku. V případě, kdy buňka nemá žádné nenavštívené sousedy, začne se vracet na buňky, které již byly navštíveny. V každém takovém kroku je buňka ze zásobníku odebrána. Pokud se nalezne buňka, které má nenavštívené sousedy, procházení tím pokračuje. Princip tohoto algoritmu lze využít i pro hledání řešení bludišť. Výsledkem je bludiště, které má málo slepých uliček, zato je však velice dlouhé. Obvykle je zde jedno velice dlouhé a klikaté řešení. Bludiště je tímto algoritmem vygenerováno velice rychle.

Kroky algoritmu:

  1. Náhodně vybereme buňku z bludiště a vložíme ji do zásobníku.
  2. Z nejnovější buňky v zásobníku se stane aktuální. Od této buňky náhodně vybereme sousední buňku, která ještě nebyla navštívena, a odstraníme cestu mezi nimi. Tuto buňku přidáme do zásobníku.
  3. Pokud všechny sousední buňky již byly navštíveny, vrátíme se na poslední navštívenou buňku a zopakujeme bod 2. Tuto buňku odstraníme ze zásobníku.
  4. Proces ukončíme ve chvíli, kdy jsme se vrátili až na startovací bod. Tím bude zásobník prázdný.
Recursive Backtracker

V každém kroku generování je toto bludiště kompletní, což znamená, že tvoří strom. Tento strom se tedy v každém kroku rozšíří o nový vrchol neboli buňku. Algoritmus lze použít pouze pro generování bludiště metodou odstraňování hran. Třetina buněk v bludišti jsou rovinky s rovnoměrným rozdělením rovinek horizontálních a vertikálních. Z obrázku 4 je patrné, že nejdelší cesta pokrývá více než polovinu bludiště, a tím je zajištěno velice dlouhé a klikaté řešení.

Tento algoritmus není označen jako uniformní, protože není schopen vygenerovat všechny možné případy bludišť. Při generování si program musí uložit do paměti všechny buňky bludiště, proto tento algoritmus patří mezi náročnější algoritmy.

Zdroje:

  1. The Buckblog: Maze Generation: Recursive Backtracking [online]. Jamis Buck, 2010 [cit. 2017-02-20]. Dostupné z: http://weblog.jamisbuck.org/2010/12/27/maze-generation-recursive-backtracking
  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.
  5. Labyrinth Algorithms: How to find a path between two points in the maze. [online]. Valentin Bryukhanov, 2015 [cit. 2017-07-29]. Dostupné z: http://bryukh.com/labyrinth-algorithms/