Generatore di labirinti con backtracker ricorsivo

L'algoritmo di backtracking ricorsivo è in realtà una ricerca in profondità di uso generale. Quando viene utilizzato per la generazione di labirinti, viene leggermente modificato per scegliere il percorso in modo casuale, mentre se utilizzato per scopi di ricerca veri e propri, in genere si cerca ogni livello in ordine lineare. Tende a produrre labirinti con corridoi lunghi e tortuosi e una soluzione molto lunga e tortuosa.

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.

L'algoritmo ricorsivo del backtracker è un metodo di ricerca in profondità per generare labirinti perfetti (labirinti senza loop e con un unico percorso tra due punti qualsiasi). È semplice, efficiente e produce labirinti visivamente accattivanti con corridoi lunghi e tortuosi.

Nonostante il nome, non è necessariamente implementato utilizzando la ricorsione. Spesso viene implementato con un approccio iterativo utilizzando una coda LIFO (ovvero uno stack). Per labirinti molto grandi, l'utilizzo della ricorsione ha maggiori probabilità di causare un overflow dello stack delle chiamate, a seconda del linguaggio di programmazione e della memoria disponibile. Una coda LIFO può essere adattata più facilmente alla gestione di grandi quantità di dati, anche mantenendola su disco o in un database se la memoria disponibile è insufficiente.

Come funziona

L'algoritmo funziona utilizzando un approccio di ricerca in profondità basato sullo stack. Ecco la suddivisione passo passo:

1. Scegli una cella di partenza e contrassegnala come visitata.
2. Finché ci sono celle non visitate: Guarda le celle vicine che non sono ancora state visitate. Se esiste almeno un vicino non visitato: Scegli casualmente uno dei vicini non visitati. Rimuovi il muro tra la cella corrente e il vicino scelto. Spostati sul vicino scelto e contrassegnalo come visitato. Spingi la cella corrente nella pila. Se non esistono vicini non visitati: Torna indietro estraendo l'ultima cella dalla pila.
3. Continuare questo processo finché la pila non sarà vuota.

Un aspetto interessante di questo algoritmo è che funziona sia come generatore di labirinti che come risolutore di labirinti. Se lo si esegue su un labirinto già generato e ci si ferma quando si raggiunge il punto finale prefissato, la pila conterrà la soluzione del labirinto.

In realtà ho due versioni di questo algoritmo in gioco su questo sito: una basata su una coda LIFO per generare i labirinti su questa pagina e una basata sulla ricorsione per risolvere i labirinti, anche quelli generati da altri algoritmi (è così che vengono create le mappe con le soluzioni). Avere due versioni diverse è solo per gioco, perché sono un nerd che lo trova interessante, entrambe avrebbero potuto funzionare per entrambi ;-)

Ulteriori letture

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

• Generatore di labirinti con algoritmo Growing Tree
• Generatore di labirinti di algoritmi di Eller
• Generatore di labirinti di caccia e uccisione