Bludiště — Prim

O(rows·cols)

Randomizovaný Primův algoritmus staví bludiště tak, jak Prim staví kostru, ale s náhodnými volbami. Začne z jedné vyhloubené místnosti a udržuje "frontu" — množinu místností dvě buňky od bludiště. Každý krok vybere náhodnou frontovou místnost, probourá zeď spojující ji s jejím sousedem v bludišti, vyhloubí ji a přidá její vlastní nové frontové místnosti. Protože růst vyzařuje ven odkudkoli je fronta, výsledek mívá mnoho krátkých větví a rovnoměrnější texturu než dlouhé klikaté chodby rekurzivního backtrackeru. Pořád je to dokonalé bludiště — jedna jedinečná cesta mezi libovolnými dvěma buňkami.

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

Jak to funguje

  1. Vyhloubej startovní místnost a přidej její sousedy do fronty.
  2. Vyber náhodnou frontovou místnost a probourej zeď k jejímu sousedovi v bludišti.
  3. Vyhloubej tu místnost a přidej její nenavštívené sousedy do fronty.
  4. Opakuj, dokud není fronta prázdná — každá místnost je v bludišti.

Pseudokód

1primMaze(grid):                      # O(rows·cols)2  carve one start room; add its walls to a frontier3  while frontier not empty:4    pick a random frontier room5    knock out the wall to its maze neighbour6    carve the room; add its new frontier rooms7  # frontier-driven growth → branchy perfect maze