Wilsonův Algorithm Maze Generator

Wilsonův algoritmus je metoda náhodné procházky s vymazanou smyčkou, která generuje uniformní kostry pro vytváření bludišť. To znamená, že všechna možná bludiště dané velikosti budou vygenerována se stejnou pravděpodobností, což z něj činí nestrannou techniku generování bludišť. Wilsonův algoritmus lze považovat za vylepšenou verzi Aldous-Broderova algoritmu, protože generuje bludiště se stejnými vlastnostmi, ale běží mnohem rychleji, takže jsem se zde neobtěžoval implementovat Aldous-Broderův algoritmus.

Dokonalé bludiště je bludiště, ve kterém existuje přesně jedna cesta z kteréhokoli bodu bludiště do kteréhokoli jiného bodu. To znamená, že nemůžete skončit v kruhu, ale často narazíte na slepé uličky, které vás donutí se otočit a vrátit se zpět.

Zde vygenerované mapy bludiště obsahují výchozí verzi bez počátečních a cílových pozic, takže si je můžete určit sami: z jakéhokoli bodu v bludišti do jakéhokoli jiného bodu existuje řešení. Pokud se chcete inspirovat, můžete zapnout navrhovanou startovní a cílovou pozici - a dokonce si prohlédnout řešení mezi nimi.

O Wilsonově algoritmu

Wilsonův algoritmus pro generování uniformních kostrových stromů pomocí náhodné zdi s vymazanou smyčkou vytvořil David Bruce Wilson.

Wilson tento algoritmus původně představil v roce 1996 při výzkumu náhodných kostrových stromů a Markovových řetězců v teorii pravděpodobnosti. Ačkoli se jeho práce zaměřovala především na matematiku a statistickou fyziku, algoritmus se od té doby široce používá pro generování bludišť díky své schopnosti vytvářet dokonale jednotná bludiště.

Jak Wilsonův algoritmus funguje pro generování bludiště

Wilsonův algoritmus zajišťuje, že finální bludiště je plně propojené bez jakýchkoli smyček iterativním vyřezáváním cest z nenavštívených buněk pomocí náhodných procházek.

Krok 1: Inicializace

• Začněte s mřížkou vyplněnou stěnami.
• Definujte seznam všech možných buněk průchodu.

Krok 2: Vyberte náhodnou počáteční buňku

• Vyberte libovolnou náhodnou buňku a označte ji jako navštívenou. Ta slouží jako výchozí bod bludiště během generování.

Krok 3: Náhodná procházka s mazáním smyčky

• Vyberte si nenavštívenou buňku a začněte náhodnou procházku (pohyb v náhodných směrech).
• Pokud cesta dosáhne již navštívené buňky, smažte všechny smyčky v cestě.
• Jakmile se trasa napojí na navštívenou oblast, označte všechny buňky v trase jako navštívené.

Krok 4: Opakujte, dokud nenavštívíte všechny buňky:

• Pokračujte ve výběru nenavštívených buněk a provádění náhodných procházek, dokud se každá buňka nestane součástí bludiště.

Další čtení

Pokud se vám tento příspěvek líbil, mohly by se vám líbit i tyto návrhy:

• Rekurzivní Backtracker Maze Generator
• Rostoucí strom Algoritmus bludiště generátor
• Generátor lovu a zabíjení bludiště