Wilsonův Algorithm Maze Generator

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

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 překlenovacích stromů pomocí smyčky vymazané náhodné stěny vytvořil David Bruce Wilson.

Wilson původně zavedl tento algoritmus v roce 1996, když zkoumal náhodné kostry a Markovovy řetězce v teorii pravděpodobnosti. Ačkoli jeho práce byla primárně v matematice a statistické fyzice, algoritmus byl od té doby široce přijat pro generování bludiště díky své schopnosti produkovat dokonale jednotná bludiště.

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

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

Krok 1: Inicializujte

• Začněte mřížkou vyplněnou stěnami.
• Definujte seznam všech možných pasážových buněk.

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

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

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

• Vyberte nenavštívenou buňku a začněte náhodnou procházku (pohybujte se v náhodných směrech).
• Pokud procházka dosáhne již navštívené buňky, vymažte všechny smyčky v cestě.
• Jakmile se procházka připojí k navštívené oblasti, označte všechny buňky na cestě jako navštívené.

Krok 4: Opakujte, dokud nebudou navštíveny všechny buňky :

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