Aldous Broder

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

Algoritmus Aldous - Broder patří k jednodušším algoritmům pro generování bludišť. Je pojmenovaný po dvou vědcích - D. Aldous a A. Broder. Ti pracovali nezávisle na sobě na hledání rovnoměrné kostry v grafu. Kostra je strom, který spojuje všechny vrcholy v grafu. Rovnoměrná kostra znamená, že všechny vrcholy mají stejnou pravděpodobnost při zapojení do výsledné kostry. Aldous - Broder algoritmus pracuje na stejném principu.

Implementace tohoto algoritmu je ze všech algoritmů generování bludišť nejjednodušší. Tento algoritmus je ale zároveň velice neefektivní. Při větších rozměrech bludiště může docházet k velice dlouhému generování. Náhodně se prochází kompletní bludiště, proto kroky pro vygenerování bludiště jsou poté v řádech tisíců. Všechny buňky mají stejnou pravděpodobnost navštívení.

Kroky algoritmu:

  1. Náhodně si zvolíme výchozí buňku.
  2. Navštívíme náhodného souseda a přesuneme se na jeho pozici.
  3. Pokud tento soused ještě nebyl navštíven, vymažeme cestu mezi nimi. Pokud však už soused byl navštíven, opakujeme bod 2.
  4. Proces ukončíme ve chvíli, kdy jsou navštíveny všechny buňky bludiště.
Aldous-Broder

Předností tohoto algoritmu je fakt, že ho je možné označit jako uniformní. Všechny možné případy bludiště mají při generování stejnou pravděpodobnost. Pro chod algoritmu je potřeba si do paměti uložit pouze mapu celého bludiště a aktuální buňku. Bludiště nemá žádný sklon, proto tento algoritmus nemá žádnou tendenci. Algoritmus lze využít pro metodu odstraňování i přidávání hran a v každém kroku generování je opět tvořen strom.

Kroky algoritmu:

  1. Náhodně si zvolíme výchozí buňku.
  2. Navštívíme náhodného souseda a přesuneme se na jeho pozici.
  3. Pokud tento soused ještě nebyl navštíven, vymažeme cestu mezi nimi. Pokud však už soused byl navštíven, opakujeme bod 2.
  4. Proces ukončíme ve chvíli, kdy jsou navštíveny všechny buňky bludiště.

Zdroje:

  1. Astrolog: Think Labyrinth: Maze Algorithms [online]. Walter D. Pullen, 2015 [cit. 2017-03-02]. Dostupné z: http://www.astrolog.org/labyrnth/algrithm.htm
  2. "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
  3. The Buckblog: Maze Generation: Aldous-Broder algorithm [online]. Jamis Buck, 2011 [cit. 2017-03-02]. Dostupné z: http://weblog.jamisbuck.org/2011/1/17/maze-generation-aldous-broder-algorithm
  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.