Generatore di labirinti con algoritmo Growing Tree

L'algoritmo Growing Tree è interessante perché può emulare il comportamento di molti altri algoritmi, a seconda di come viene scelta la cella successiva durante la generazione. L'implementazione in questa pagina utilizza un approccio breadth-first, simile a una coda.

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 Growing Tree

L'algoritmo Growing Tree è un metodo flessibile e potente per generare labirinti perfetti. L'algoritmo è interessante perché può emulare il comportamento di diversi altri algoritmi di generazione di labirinti, come l'algoritmo di Prim, il backtracking ricorsivo e la divisione ricorsiva, a seconda di come si seleziona la cella successiva da elaborare.

Come funziona l'algoritmo Growing Tree

Fase 1: Inizializzazione

• Inizia con una griglia di celle non visitate.
• Scegli una cella di partenza casuale e aggiungila a un elenco.

Fase 2: Ciclo di generazione del labirinto

• Finché l'elenco delle celle non è vuoto: seleziona una cella dall'elenco in base a una strategia specifica (spiegata di seguito). Crea un passaggio dalla cella selezionata a una delle sue vicine non visitate (scelte casualmente). Aggiungi la vicina all'elenco poiché ora fa parte del labirinto. Se la cella selezionata non ha vicine non visitate, rimuovila dall'elenco.

Fase 3: Risoluzione

• L'algoritmo termina quando non ci sono più celle nell'elenco, il che significa che l'intero labirinto è stato scavato.

Strategie di selezione cellulare (flessibilità dell'algoritmo)

La caratteristica distintiva dell'algoritmo Growing Tree è la scelta della cella successiva da elaborare. Questa scelta influenza notevolmente l'aspetto del labirinto:

Cella più recente (comportamento simile a uno stack) – Backtracker ricorsivo:

• Selezionare sempre la cella aggiunta più di recente.
• Crea corridoi lunghi e tortuosi con molti vicoli ciechi (come un labirinto di ricerca in profondità).
• I labirinti tendono ad avere passaggi lunghi e sono facili da risolvere.

Cellula casuale (algoritmo di Prim randomizzato):

• Ogni volta seleziona una cella a caso dall'elenco.
• Crea un labirinto distribuito in modo più uniforme, con percorsi complessi e intricati.
• Meno corridoi lunghi e più diramazioni.

Cella più vecchia (comportamento simile a una coda):

• Scegli sempre la cella più vecchia nell'elenco.
• Genera labirinti con una distribuzione più uniforme, come un modello di ricerca in ampiezza.
• Corti e fitti passaggi con fitte connessioni.
• (Questa è la versione implementata qui)

Approcci ibridi:

Combina strategie per diverse caratteristiche del labirinto. Ad esempio:

• 90% più recente, 10% casuale: sembra per lo più un labirinto ricorsivo di backtracker, ma con rami occasionali che interrompono i lunghi corridoi.
• 50% più recente, 50% più vecchio: bilancia i lunghi corridoi con una vegetazione cespugliosa.

Ulteriori letture

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

• Generatore di labirinti di algoritmi di Eller
• Generatore di labirinti con backtracker ricorsivo
• Generatore di labirinti con algoritmo di Wilson