Wilsonov generátor bludísk algoritmov
Publikované: 16. februára 2025 o 19:33:55 UTC
Generátor bludiska pomocou Wilsonovho algoritmu na vytvorenie dokonalého bludiska. Tento algoritmus generuje všetky možné bludiská danej veľkosti s rovnakou pravdepodobnosťou, takže teoreticky môže generovať bludiská mnohých zmiešaných rozložení, ale keďže existuje viac možných bludísk s kratšími chodbami ako dlhšími, častejšie ich uvidíte.Wilson's Algorithm Maze Generator
Wilsonov algoritmus je metóda náhodnej prechádzky s vymazanou slučkou, ktorá generuje jednotné kostry na vytvorenie bludiska. To znamená, že je rovnako pravdepodobné, že sa vygenerujú všetky možné bludiská danej veľkosti, čo z toho robí nezaujatú techniku vytvárania bludísk. Wilsonov algoritmus možno považovať za vylepšenú verziu Aldous-Broderovho algoritmu, pretože generuje bludisko s rovnaký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 vymazanej slučkou vytvoril David Bruce Wilson.
Wilson pôvodne zaviedol tento algoritmus v roku 1996, keď skúmal náhodné kostry a Markovove reťazce v teórii pravdepodobnosti. Hoci jeho práca bola primárne v matematike a štatistickej fyzike, algoritmus bol odvtedy široko prijatý na vytváranie bludísk vďaka svojej schopnosti vytvárať dokonale jednotné bludisko.
Ako funguje Wilsonov algoritmus pre generáciu bludiska
Wilsonov algoritmus zaisťuje, že konečné 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: Inicializujte
- Začnite s mriežkou vyplnenou stenami.
- Definujte zoznam všetkých možných pasážovacích buniek.
Krok 2: Vyberte náhodnú počiatočnú bunku
- Vyberte ľubovoľnú náhodnú bunku a označte ju ako navštívenú. Toto slúži ako východiskový bod bludiska počas generovania.
Krok 3: Náhodná chôdza s vymazaním slučky
- Vyberte nenavštívenú bunku a začnite náhodnú prechádzku (pohybujte sa 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 pripojí k navštívenej oblasti, označte všetky bunky na ceste ako navštívené.
Krok 4: Opakujte, kým sa nenavštívia všetky bunky :
- Pokračujte vo výbere nenavštívených buniek a vykonávajte náhodné prechádzky, kým sa každá bunka nestane súčasťou bludiska.