Ellerů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 patří k nejrychlejším algoritmům pro generování bludišť. Bludiště se vytváří po řádcích a algoritmus využívá množiny pro určení, zda jsou dané buňky propojené. Když se jeden řádek bludiště vygeneruje, algoritmus se na tento řádek už nemusí vracet. V žádném případě pro chod algoritmu není potřeba více informací než ty, které přečteme pouze z jednoho řádku. Z vygenerované řady se poté náhodně vygenerují cesty na jih dle jednotlivých množin a pokračuje se na dalším řádku. Počet cest vygenerovaných na jih je náhodný a závisí na velikosti množiny. Proto má tento algoritmus velký sklon buněk neboli tendenci.

Kroky algoritmu:

  1. Každé buňce v prvním řádku přiřadíme její vlastní množinu.
  2. Náhodně propojíme sousední buňky, ale pouze v případě, kdy buňky nejsou ve stejném seskupení. Při propojení buněk sjednotíme jejich množiny.
  3. Pro každé seskupení na řádku náhodně vytvoříme cestu na jih a danou buňku vložíme do dané množiny.
  4. Všechny zbylé buňky na dalším řádku přidáme do nových množin.
  5. Opakujeme body 2-4 do té doby, než dosáhneme posledního řádku.
  6. Na posledním řádku propojíme všechny buňky, které nejsou ve stejné množině. Tím nám vznikne jedna velká množina.
Eller

Z obrázku lze rozeznat tendenci bludiště, čímž se tento algoritmus řadí k algoritmům Binary Tree a Sidewinger, které jako jediné mají sklon buněk. Strom je v tomto případě vytvořen až na konci generování. Algoritmus je schopen vygenerovat všechna možná bludiště, ale ne se stejnou pravděpodobností. Pro generování je si potřeba do paměti uložit celý řádek bludiště, proto tento algoritmus může být zařazen mezi středně náročné algoritmy. Jako většinu algoritmů, tak i tento lze využít pro oba způsoby generování přidáváním nebo odebíráním hran.

Zdroje:

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