Generatore di labirinti con algoritmo di Wilson

L'algoritmo di Wilson è un metodo di random walk con loop cancellato che genera alberi di copertura uniformi per la creazione di labirinti. Ciò significa che tutti i possibili labirinti di una data dimensione hanno la stessa probabilità di essere generati, rendendolo una tecnica di generazione di labirinti imparziale. L'algoritmo di Wilson può essere considerato una versione migliorata dell'algoritmo di Aldous-Broder, in quanto genera labirinti con caratteristiche identiche, ma è molto più veloce, quindi non mi sono preoccupato di implementare l'algoritmo di Aldous-Broder qui.

Un labirinto perfetto è un labirinto in cui esiste esattamente un percorso da qualsiasi punto del labirinto a qualsiasi altro punto. Ciò significa che non si può finire per girare in tondo, ma spesso si incontrano vicoli ciechi che costringono a tornare indietro.

Le mappe del labirinto qui generate includono una versione predefinita senza posizioni di partenza e di arrivo, in modo che possiate deciderle da soli: ci sarà una soluzione da qualsiasi punto del labirinto a qualsiasi altro punto. Se volete trarre ispirazione, potete attivare una posizione di partenza e una di arrivo suggerite e persino vedere la soluzione tra le due.

Informazioni sull'algoritmo di Wilson

L'algoritmo di Wilson per la generazione di alberi di copertura uniformi utilizzando un muro casuale cancellato tramite loop è stato creato da David Bruce Wilson.

Wilson introdusse originariamente questo algoritmo nel 1996, mentre svolgeva ricerche sugli alberi di copertura casuali e sulle catene di Markov in teoria della probabilità. Sebbene il suo lavoro fosse principalmente in matematica e fisica statistica, l'algoritmo è stato da allora ampiamente adottato per la generazione di labirinti grazie alla sua capacità di produrre labirinti perfettamente uniformi.

Come funziona l'algoritmo di Wilson per la generazione di labirinti

L'algoritmo di Wilson garantisce che il labirinto finale sia completamente connesso, senza alcun loop, ricavando iterativamente percorsi dalle celle non visitate utilizzando passeggiate casuali.

Passaggio 1: inizializzazione

• Inizia con una griglia piena di muri.
• Definisci un elenco di tutte le possibili celle di passaggio.

Passaggio 2: scegli una cella di partenza casuale

• Scegli una cella a caso e contrassegnala come visitata. Questa fungerà da punto di partenza del labirinto durante la generazione.

Fase 3: Passeggiata casuale con cancellazione del ciclo

• Scegli una cella non visitata e inizia una passeggiata casuale (muovendoti in direzioni casuali).
• Se la passeggiata raggiunge una cella già visitata, cancella tutti i loop nel percorso.
• Una volta che la passeggiata si collega alla regione visitata, contrassegna tutte le celle del percorso come visitate.

Passaggio 4: ripetere fino a quando tutte le celle non saranno state visitate:

• Continua a selezionare le celle non visitate ed esegui passeggiate casuali finché ogni cella non fa parte del labirinto.

Ulteriori letture

Se ti è piaciuto questo post, potrebbero piacerti anche questi suggerimenti:

• Generatore di labirinti di algoritmi di Eller
• Generatore di labirinti con backtracker ricorsivo
• Generatore di labirinti con algoritmo di Kruskal