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, poiché genera labirinti con caratteristiche identiche, ma funziona molto più velocemente, 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 conduceva ricerche su alberi di copertura casuali e catene di Markov nella teoria della probabilità. Sebbene il suo lavoro fosse principalmente in matematica e fisica statistica, da allora l'algoritmo è stato 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 da celle non visitate utilizzando passeggiate casuali.

Passaggio 1: Inizializzazione

• Inizia con una griglia piena di muri.
• Definire 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. Questo funge da punto di partenza del labirinto durante la generazione.

Fase 3: Passeggiata casuale con cancellazione del loop

• Scegli una cella non visitata e inizia una passeggiata casuale (muovendoti in direzioni casuali).
• Se il percorso raggiunge una cella già visitata, cancella tutti i loop presenti 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.