Generatore di labirinti con algoritmo di Kruskal

L'algoritmo di Kruskal è un algoritmo di tipo "minimum spanning tree" che può essere adattato per la generazione di labirinti. È particolarmente efficace per la creazione di labirinti perfetti. Un'alternativa all'algoritmo di Kruskal è l'algoritmo di Prim, anch'esso un algoritmo di tipo "minimum spanning tree", ma poiché generano labirinti identici e quello di Kruskal è più veloce, non mi sono preoccupato di implementare quello di Prim.

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 di Kruskal

L'algoritmo di Kruskal fu creato da Joseph Bernard Kruskal, Jr., matematico, statistico e informatico statunitense. Descrisse l'algoritmo per la prima volta nel 1956 nel suo articolo "On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem".

L'algoritmo è progettato per trovare l'albero di copertura minimo (MST) di un grafico, assicurando che tutti i vertici siano collegati con il peso totale minimo possibile degli spigoli, evitando al contempo i cicli.

Come funziona l'algoritmo di Kruskal per la generazione di labirinti

Passaggio 1: inizializzazione

• Tratta ogni cella del labirinto come un insieme separato (un componente unico).
• Elenca tutte le pareti tra celle adiacenti come potenziali bordi.

Fase 2: Ordinare le pareti

• Mescola o ordina casualmente i muri. Se lo implementi come un vero algoritmo di Kruskal, ordina i muri in modo casuale (poiché la generazione del labirinto non richiede pesi).

Fase 3: pareti di processo

• Passa attraverso le pareti mescolate.
• Se le due celle divise dal muro appartengono a insiemi diversi (ovvero non sono ancora collegate nel labirinto), rimuovere il muro e unire gli insiemi.
• Se sono già nello stesso set, salta il muro (per evitare cicli).

Passaggio 4: continuare fino al completamento

• Ripetere questo processo finché tutte le celle non saranno collegate, formando un unico albero di copertura.
• Alla fine, ogni cellula è collegata alle altre senza anelli o sezioni isolate.

Poiché l'algoritmo di Kruskal si basa sulla fusione di insiemi, può essere ottimizzato utilizzando l'algoritmo Union-Find, che fornisce un modo efficiente per tracciare le celle connesse durante la generazione del labirinto. Potete vedere la mia implementazione PHP dell'algoritmo Union-Find qui: Link.

Ulteriori letture

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

• Generatore di labirinti con algoritmo Growing Tree
• Generatore di labirinti di caccia e uccisione
• Generatore di labirinti con backtracker ricorsivo