Generatore di labirinti con algoritmo di Kruskal

L'algoritmo di Kruskal è un algoritmo di albero di copertura minimo che può essere adattato per la generazione di labirinti. È particolarmente efficace per creare labirinti perfetti. Un'alternativa all'algoritmo di Kruskal è l'algoritmo di Prim, che è anche un algoritmo di albero di copertura minimo, ma poiché generano labirinti identici e quello di Kruskal funziona più velocemente, 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 è stato creato da Joseph Bernard Kruskal, Jr., un matematico, statistico e informatico americano. Descrisse per la prima volta l'algoritmo 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 minimo peso totale 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: Ordina le pareti

• Mescola o ordina casualmente i muri. Se lo implementi come un vero algoritmo di Kruskal, ordina i muri in ordine 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 fino a quando tutte le celle 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 set, può essere ottimizzato utilizzando l'algoritmo Union-Find, che fornisce un modo efficiente per tracciare le celle connesse durante la generazione del labirinto. Puoi vedere la mia implementazione PHP dell'algoritmo Union-Find qui: Insieme disgiunto (algoritmo Union-Find) in PHP