Generatore di labirinti con backtracker ricorsivo

L'algoritmo ricorsivo del backtracker è in realtà una ricerca depth-first di uso generale. Quando viene utilizzato per la generazione di labirinti, viene leggermente modificato per scegliere il percorso in modo casuale, mentre se viene utilizzato per scopi di ricerca effettivi, 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 depth-first per generare labirinti perfetti (labirinti senza loop e con un singolo percorso tra due punti qualsiasi). È semplice, efficiente e produce labirinti visivamente accattivanti con corridoi lunghi e tortuosi.

Nonostante il nome, non deve necessariamente essere implementato usando la ricorsione. Spesso viene implementato in un approccio iterativo usando una coda LIFO (ad esempio uno stack). Per labirinti molto grandi, usare la ricorsione ha più probabilità di causare un overflow dello stack di 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 mantenendo la coda su disco o in un database se la memoria disponibile è insufficiente.

Come funziona

L'algoritmo opera utilizzando un approccio di ricerca depth-first basato sullo stack. Ecco la ripartizione passo dopo 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 a caso uno dei vicini non visitati.
     • Rimuovi il muro tra la cella corrente e quella vicina scelta.
     • Spostati sul vicino scelto e contrassegnalo come visitato.
     • Sposta la cella corrente nella pila.
   • Se non ci sono vicini non visitati:
     • Torna indietro estraendo l'ultima cella dalla pila.
3. Continuare questo procedimento finché la pila non sarà vuota.

Un fatto interessante di questo algoritmo è che funziona sia come generatore di labirinti che come risolutore di labirinti. Se lo esegui su un labirinto già generato e ti fermi quando raggiungi il punto finale deciso, la pila conterrà la soluzione del labirinto.

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