Generatorul de labirint al algoritmului lui Wilson

Algoritmul lui Wilson este o metodă de mers aleatoriu șters prin buclă care generează arbori uniformi care se întind pentru crearea labirintului. Aceasta înseamnă că toate labirinturile posibile de o anumită dimensiune au șanse egale de a fi generate, ceea ce face din aceasta o tehnică imparțială de generare a labirintului. Algoritmul lui Wilson poate fi considerat o versiune îmbunătățită a algoritmului Aldous-Broder, deoarece generează labirinturi cu caracteristici identice, dar rulează mult mai repede, așa că nu m-am deranjat să implementez algoritmul Aldous-Broder aici.

Un labirint perfect este un labirint în care există exact o singură cale de la orice punct din labirint la orice alt punct. Aceasta înseamnă că nu puteți ajunge să vă învârtiți în cerc, dar veți întâlni adesea fundături, forțându-vă să vă întoarceți.

Hărțile labirintului generate aici includ o versiune implicită fără poziții de început și de sfârșit, astfel încât să le puteți decide singuri: va exista o soluție din orice punct al labirintului către orice alt punct. Dacă doriți să vă inspirați, puteți activa o poziție de început și de sfârșit sugerată - și chiar să vedeți soluția între cele două.

Despre algoritmul lui Wilson

Algoritmul lui Wilson pentru generarea de arbori uniformi care se întinde folosind un perete aleator șters prin buclă a fost creat de David Bruce Wilson.

Wilson a introdus inițial acest algoritm în 1996, în timp ce cerceta arbori de întindere aleatoriu și lanțuri Markov în teoria probabilității. Deși munca sa a fost în primul rând în matematică și fizică statistică, algoritmul a fost adoptat pe scară largă pentru generarea labirintului datorită capacității sale de a produce labirinturi perfect uniforme.

Cum funcționează algoritmul lui Wilson pentru Maze Generation

Algoritmul lui Wilson asigură că labirintul final este complet conectat, fără bucle, sculptând în mod iterativ căi din celulele nevizitate folosind plimbări aleatorii.

Pasul 1: Inițializați

• Începeți cu o rețea plină cu pereți.
• Definiți o listă cu toate celulele de trecere posibile.

Pasul 2: Alegeți o celulă de pornire aleatorie

• Alegeți orice celulă aleatorie și marcați-o ca vizitată. Acesta servește drept punct de plecare al labirintului în timpul generării.

Pasul 3: Mers aleatoriu cu ștergerea buclei

• Alegeți o celulă nevizitată și începeți o plimbare aleatorie (deplasându-vă în direcții aleatorii).
• Dacă mersul ajunge la o celulă deja vizitată, ștergeți buclele din cale.
• Odată ce plimbarea se conectează la regiunea vizitată, marcați toate celulele din cale ca fiind vizitate.

Pasul 4: Repetați până când toate celulele sunt vizitate :

• Continuați să selectați celule nevizitate și să efectuați plimbări aleatorii până când fiecare celulă face parte din labirint.