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 molti 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:
  • Selezionare una cella dall'elenco in base a una strategia specifica (come spiegato di seguito).
  • Crea un passaggio dalla cella selezionata a una delle celle vicine non visitate (scelte casualmente).
  • Aggiungi il vicino alla lista poiché ora fa parte del labirinto.
  • Se la cella selezionata non ha vicini non visitati, rimuoverla dall'elenco.

Fase 3: Risoluzione

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

Strategie di selezione cellulare (flessibilità dell'algoritmo)

La caratteristica distintiva dell'algoritmo Growing Tree è il modo in cui scegli quale cella elaborare per prima. 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 (simili a 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, simile a un modello di ricerca in ampiezza.
• Passaggi brevi e fitti di vegetazione, con fitte connessioni.
• (Questa è la versione implementata qui)

Approcci ibridi:

Combina strategie per varie caratteristiche del labirinto. Ad esempio:

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