Kruskalů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

Základem tohoto algoritmu je práce se stěnami bludiště. Tyto stěny si musíme uložit do kolekce a poté postupně s každou stěnou pracovat. U každé stěny se rozhodneme, zda stěnu vymažeme nebo ponecháme. Algoritmus je v tomto případě více paměťově náročný, protože se zde musí uložit informace o všech buňkách bludiště a informace o tom, v jaké kolekci jsou obsaženy. Samotné generování pak probíhá velice rychle. Výsledkem algoritmu je bludiště, které neobsahuje dlouhé cesty, ale obsahuje mnoho slepých uliček.

Kroky algoritmu:

  1. Všechny hrany bludiště si uložíme do kolekce.
  2. Náhodně vybereme jednu stěnu bludiště. Pokud stěna spojuje dvě buňky, které nejsou ve stejné kolekci, hranu odstraníme z bludiště i z kolekce. Pokud tyto buňky jsou ve stejné kolekci, hranu ponecháme, ale odstraníme ji z kolekce.
  3. Proces opakujeme, dokud nezbydou žádné hrany v kolekci.
Kruskal

Z obrázku lze rozeznat, že výsledné bludiště nemá žádnou tendenci a obsahuje poměrně dlouhou nejdelší cestu. Algoritmus je schopný vygenerovat všechna možná bludiště, ta ovšem nemají stejnou pravděpodobnost vygenerování. Tento algoritmus si potřebuje uložit do paměti všechny buňky bludiště, proto patří mezi paměťově náročnější algoritmy pro generování dokonalých bludišť. Každým krokem si z buněk vytváří množinu a až na konci generování je utvořen strom. Tento algoritmus je možné využít jak v případě přidávání, tak i odebírání hran.

Zdroje:

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