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

Tento algoritmus vylepšuje variantu Aldous – Broder. V tomto případě se také jedná o hledání kostry grafu, ale s tím rozdílem, že některé buňky jsou upřednostňovány před ostatními. Efektivita algoritmu je mnohem větší než v případě Aldous – Broder. Opět je zde zakomponován prvek náhodného procházení, ale zároveň je zvýšena pravděpodobnost vytvoření delších chodeb.

Kroky algoritmu:

  1. Náhodně si zvolíme buňku a uložíme ji do zásobníku.
  2. Náhodně si zvolíme buňku, která není uložena v zásobníku. Z této buňky začneme náhodně procházet bludiště do té doby, než narazíme na buňku, která je uložena v zásobníku.
  3. Vytvoříme cestu náhodným procházením mezi náhodně zvolenou buňkou a buňkou, na kterou jsme narazili procházením.
  4. Opakujeme bod 2 a 3 do té doby, než budou uložené všechny buňky v zásobníku.
Wilson's

Vlastnostmi je tento algoritmus velice podobný předešlému algoritmu Aldous-Broder. V každém kroku vytváření bludiště se tvoří strom, lze ho použít na vytváření bludišť použitím metod přidáváním či odstraňováním hran, vytváří bludiště, která nemají tendenci k žádnému sklonu buněk a můžeme ho označit jako uniformní. Rozdíl je tu však v paměťové náročnosti. Při použití tohoto algoritmu je potřeba si uložit do paměti všechny buňky bludiště. Algoritmy Wilson a Aldous-Broder jsou jedinými ze všech ostatních algoritmů, které vytvářejí všechna možná bludiště se stejnou pravděpodobností.

Zdroje:

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