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 continuare quando non può andare oltre, al contrario di una vera ricerca ricorsiva, che tornerà sempre alla cella precedente sullo stack.

Per questo motivo, questo algoritmo può essere facilmente adattato per generare labirinti con aspetto e sensazioni diversi, semplicemente scegliendo di entrare in modalità "caccia" più spesso o in base a regole specifiche. La versione implementata qui entra in modalità "caccia" solo quando non può andare oltre la 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à (ad esempio l'algoritmo Recursive Backtracker), tranne per il fatto che quando non può andare oltre la posizione corrente, esegue una scansione sistematica (o "caccia") del labirinto per trovare una nuova cella da cui procedere. L'algoritmo consiste di due fasi principali: camminare e cacciare.

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 sul vicino, contrassegnalo come visitato e traccia un percorso tra la cella precedente e quella nuova.
• Ripetere la procedura 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 fino a quando tutte le celle non saranno state visitate.