Primův algoritmus

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

Originální myšlenka tohoto algoritmu pracuje s ohodnocováním hran. Pro účely bludiště je vhodnější nahradit tento proces tím, že dané hrany budeme vybírat náhodně se stejnou pravděpodobností. Každá hrana bude tedy ohodnocena stejnou hodnotou. U větších rozměrů bludiště je tento algoritmus náročnější na paměť, která je potřeba ke generování. Začátek algoritmu začne v jedné náhodně vybrané buňce a každým krokem se bludiště náhodně zvětšuje do prostoru, až zaplní kompletní bludiště. Výsledkem algoritmu je bludiště, které neobsahuje dlouhé cesty, ale obsahuje mnoho slepých uliček.

Kroky algoritmu:

  1. Náhodně vybereme buňku z bludiště a vložíme ji do zásobníku.
  2. Náhodně vybereme jednu zeď dané buňky a odstraníme ji. Buňka za zdí však nesmí být již uložena v zásobníku.
  3. Nově zvolená buňka se stane aktuální a opakujeme bod 2 do té doby, než budeme mít uložené všechny buňky bludiště v zásobníku.
Recursive Backtracker

Primův algoritmus je téměř totožný s algoritmem Recursive Backtracker. Z obrázku 13 je však patrný rozdíl v nejdelší cestě, která je mnohem kratší než v případě Recursive Backtrackeru. Tento algoritmus je také schopný vygenerovat všechna možná bludiště, ale ne se stejnou pravděpodobností. Zbývající vlastnosti jsou již totožné. Během generování toto bludiště vytváří strom, algoritmus lze využít pro obě metody vytváření bludišť, výsledné bludiště nemá žádný sklon buněk a pro generování je potřeba uložit všechny buňky bludiště.

Zdroje:

  1. The Buckblog: Maze Generation: Prim's Algorithm [online]. Jamis Buck, 2011 [cit. 2017-03]. Dostupné z: http://weblog.jamisbuck.org/2011/1/10/maze-generation-prim-s-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.