Bludiště — Wilson

O(rows·cols) expected

Wilsonův algoritmus je ten elegantní: vytvoří nezkreslené bludiště, kde je každé možné uspořádání přesně stejně pravděpodobné (rovnoměrná kostra). Zasadí bludiště jedinou místností a pak opakovaně začne náhodnou procházku z nějaké nenavštívené místnosti. Procházka volně bloumá; kdykoli zkříží svou vlastní cestu, smaže smyčku, kterou právě udělala, a ve chvíli, kdy narazí na existující bludiště, se zastaví a celá smyčky-zbavená cesta se vyhloubí. Rané procházky jsou dlouhé (bludiště je malé), ale zkracují se, jak se bludiště plní, což dává očekávaný lineární čas. Na rozdíl od backtrackeru a Prima — které mají charakteristické textury — Wilson nemá žádné zkreslení.

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

Jak to funguje

  1. Zasaď bludiště jednou místností.
  2. Z náhodné nenavštívené místnosti udělej náhodnou procházku.
  3. Kdykoli se procházka zacyklí, smaž smyčku.
  4. Když procházka dorazí k bludišti, vyhloubej celou její cestu; opakuj, dokud nějaká zbývá.

Pseudokód

1wilsonMaze(grid):                    # O(rows·cols) expected2  seed the maze with one room3  while unvisited rooms remain:4    random-walk from an unvisited room,5    erasing any loop the walk forms,6    until it reaches the maze7    carve the loop-erased path in8  # every maze equally likely (uniform spanning tree)