Generatorul de labirint al algoritmului lui Wilson

Algoritmul lui Wilson este o metodă de mers aleatoriu cu ștergere a buclelor care generează arbori de acoperire uniformi pentru crearea de labirinturi. Aceasta înseamnă că toate labirinturile posibile de o anumită dimensiune au aceeași probabilitate de a fi generate, ceea ce îl face 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 rapid, așa că nu m-am obosit 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 de întindere folosind un perete aleatoriu ș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 acoperire aleatorie și lanțuri Markov în teoria probabilităților. Deși munca sa a fost în principal în matematică și fizică statistică, algoritmul a fost adoptat pe scară largă pentru generarea de labirinturi datorită capacității sale de a produce labirinturi perfect uniforme.

Cum funcționează algoritmul lui Wilson pentru generarea labirintului

Algoritmul lui Wilson asigură că labirintul final este complet conectat fără bucle, prin sculptarea iterativă a unor căi din celule nevizitate folosind mersuri aleatorii.

Pasul 1: Inițializare

• Începeți cu o grilă umplută 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ă. Aceasta servește drept punct de plecare al labirintului în timpul generării.

Pasul 3: Mers aleatoriu cu ștergerea buclelor

• Alegeți o celulă nevizitată și începeți o plimbare aleatorie (mișcare în direcții aleatorii).
• Dacă traseul ajunge la o celulă deja vizitată, ștergeți orice bucle din cale.
• Odată ce plimbarea se conectează la regiunea vizitată, marcați toate celulele din cale ca vizitate.

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

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

Lectură suplimentară

Dacă ți-a plăcut această postare, s-ar putea să-ți placă și aceste sugestii:

• Generatorul de labirint al algoritmului lui Kruskal
• Generator de labirint al algoritmului de creștere a arborilor
• Recursive Backtracker Maze Generator