Generování bludiště

O(rows·cols)

Tohle staví bludiště rekurzivním backtrackerem — náhodným prohledáváním do hloubky. Každá buňka začíná jako plná zeď. Z levé horní místnosti vybere náhodného souseda dvě buňky daleko, probourá zeď mezi nimi a přesune se tam; když buňka nemá žádné nenavštívené sousedy, vrací se zpět, dokud nějakého nenajde. Protože se do každé buňky vstoupí přesně jednou, tvoří chodby kostru mřížky: „dokonalé“ bludiště s právě jednou cestou mezi libovolnými dvěma buňkami a bez smyček. Běží v čase lineárním k počtu buněk. Stejnou vyhloubenou mřížku pak mohou řešit algoritmy hledání cesty.

Klikni na buňku pro přepnutí zdi
Mřížka
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Začni s každou buňkou jako plnou zdí.
  2. Z aktuální buňky vyber náhodného nenavštíveného souseda dvě buňky daleko.
  3. Probourej zeď mezi nimi a přesuň se tam.
  4. Ve slepé uličce se vrať k poslední buňce s nenavštíveným sousedem — opakuj, dokud nejsou všechny vyhloubené.

Pseudokód

1recursiveBacktracker(grid):          # O(rows·cols)2  every cell starts solid3  carve(cell):4    mark cell as a passage5    for each neighbour 2 cells away, in random order:6      if neighbour not yet carved:7        knock out the wall between them8        carve(neighbour)              # recurse, backtrack at dead ends9  carve(top-left room)                # one path between any two cells