Wilsonov generátor bludísk algoritmov

Wilsonov algoritmus je metóda náhodnej prechádzky s vymazanými slučkami, ktorá generuje rovnomerné kostry pre vytváranie bludísk. To znamená, že všetky možné bludiská danej veľkosti sa s rovnakou pravdepodobnosťou vygenerujú, čo z neho robí nestrannú techniku generovania bludísk. Wilsonov algoritmus možno považovať za vylepšenú verziu Aldous-Broderovho algoritmu, pretože generuje bludiská s identickými charakteristikami, ale beží oveľa rýchlejšie, takže som sa tu neobťažoval implementovať Aldous-Broderov algoritmus.

Dokonalé bludisko je bludisko, v ktorom existuje presne jedna cesta z ktoréhokoľvek bodu bludiska do ktoréhokoľvek iného bodu. To znamená, že nemôžete skončiť v kruhu, ale často narazíte na slepé uličky, ktoré vás prinútia otočiť sa a vrátiť sa späť.

Tu vygenerované mapy bludiska obsahujú predvolenú verziu bez počiatočnej a cieľovej pozície, takže si ich môžete určiť sami: z ľubovoľného bodu bludiska do ľubovoľného iného bodu bude existovať riešenie. Ak sa chcete inšpirovať, môžete zapnúť navrhovanú počiatočnú a cieľovú pozíciu - a dokonca si pozrieť riešenie medzi nimi.

O Wilsonovom algoritme

Wilsonov algoritmus na generovanie rovnomerných kostrových stromov pomocou náhodnej steny s vymazanou slučkou vytvoril David Bruce Wilson.

Wilson pôvodne predstavil tento algoritmus v roku 1996 pri výskume náhodných kostrov a Markovových reťazcov v teórii pravdepodobnosti. Hoci jeho práca bola primárne v oblasti matematiky a štatistickej fyziky, algoritmus sa odvtedy široko používa na generovanie bludísk vďaka svojej schopnosti vytvárať dokonale jednotné bludiská.

Ako Wilsonov algoritmus funguje na generovanie bludiska

Wilsonov algoritmus zaisťuje, že finálne bludisko je plne prepojené bez akýchkoľvek slučiek iteratívnym vyrezávaním ciest z nenavštívených buniek pomocou náhodných prechádzok.

Krok 1: Inicializácia

• Začnite s mriežkou vyplnenou stenami.
• Definujte zoznam všetkých možných buniek pasáže.

Krok 2: Vyberte náhodnú štartovaciu bunku

• Vyberte ľubovoľnú náhodnú bunku a označte ju ako navštívenú. Táto bunka slúži ako východiskový bod bludiska počas generovania.

Krok 3: Náhodná prechádzka s vymazaním slučky

• Vyberte si nenavštívenú bunku a začnite náhodnú prechádzku (pohyb v náhodných smeroch).
• Ak prechádzka dosiahne už navštívenú bunku, vymažte všetky slučky v ceste.
• Keď sa prechádzka spojí s navštívenou oblasťou, označte všetky bunky v ceste ako navštívené.

Krok 4: Opakujte, kým nenavštívite všetky bunky:

• Pokračujte vo výbere nenavštívených buniek a vykonávaní náhodných prechádzok, kým sa každá bunka nestane súčasťou bludiska.

Ďalšie čítanie

Ak sa vám tento príspevok páčil, možno sa vám budú páčiť aj tieto návrhy:

• Ellerov generátor bludísk algoritmov
• Rastúci strom Algoritmus bludisko generátor
• Generátor Bludiska Lov a Zabitie