Generatore di labirinti di caccia e uccisione

L'algoritmo Hunt and Kill è in realtà una versione modificata del Recursive Backtracker. La modifica consiste nella scansione sistematica (o "caccia") di una nuova cella da cui proseguire quando non è più possibile proseguire, a differenza di una vera ricerca ricorsiva, che torna sempre alla cella precedente nello stack.

Per questo motivo, questo algoritmo può essere facilmente adattato per generare labirinti con aspetto e funzionalità diversi, semplicemente scegliendo di entrare in modalità "caccia" più spesso o secondo regole specifiche. La versione implementata qui entra in modalità "caccia" solo quando non può allontanarsi ulteriormente dalla cella corrente.

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 Hunt and Kill

L'algoritmo Hunt and Kill è un metodo semplice ma efficace per generare labirinti. È in qualche modo simile a una ricerca in profondità (ovvero l'algoritmo Recursive Backtracker), con la differenza che, quando non può allontanarsi ulteriormente dalla posizione corrente, esegue una scansione sistematica (o "caccia") del labirinto per trovare una nuova cella da cui procedere. L'algoritmo si compone di due fasi principali: la fase di camminata e la fase di caccia.

Come funziona l'algoritmo Hunt and Kill per la generazione di labirinti

Passaggio 1: iniziare da una cella casuale

• Trova una cella a caso nella griglia e contrassegnala come visitata.

Fase 2: Fase di camminata (camminata casuale)

• Scegli un vicino casuale che non hai mai visitato.
• Spostati verso quel vicino, contrassegnalo come visitato e traccia un percorso tra la cella precedente e quella nuova.
• Ripetere l'operazione finché non ci saranno più vicini indesiderati.

Fase 3: Fase di caccia (backtracking tramite scansione)

• Esamina la griglia riga per riga (o colonna per colonna).
• Trova la prima cella non visitata che ha almeno un vicino visitato.
• Collega quella cella a un vicino visitato per riprendere la fase di camminata.
• Ripetere l'operazione finché non saranno state visitate tutte le celle.

Ulteriori letture

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

• Generatore di labirinti con algoritmo di Wilson
• Generatore di labirinti con backtracker ricorsivo
• Generatore di labirinti con algoritmo Growing Tree