Generatore di labirinti di algoritmi di Eller

L'algoritmo di Eller è un algoritmo di generazione di labirinti che produce in modo efficiente labirinti perfetti (labirinti senza loop e con un singolo percorso tra due punti qualsiasi) utilizzando un approccio riga per riga. Produce labirinti simili all'algoritmo di Kruskal, ma lo fa generando solo una riga alla volta, senza la necessità di memorizzare l'intero labirinto in memoria. Ciò lo rende utile per generare labirinti molto grandi su sistemi molto limitati e per la generazione di contenuti procedurali.

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 Eller

L'algoritmo di Eller è stato introdotto da David Eller.

L'algoritmo è degno di nota per il suo efficiente approccio riga per riga alla generazione di labirinti, rendendolo ideale per labirinti infiniti o labirinti generati in tempo reale. È comunemente citato nella letteratura sulla generazione di contenuti procedurali e sulla generazione di labirinti, ma non sono riuscito a trovare fonti primarie che descrivano in dettaglio la sua pubblicazione originale.

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

L'algoritmo di Eller elabora una riga alla volta, mantenendo e modificando set di celle connesse. Garantisce la connettività evitando loop ed estende efficacemente il labirinto verso il basso.

In teoria può essere utilizzato per generare labirinti infiniti, tuttavia, per garantire che il labirinto generato sia effettivamente risolvibile, è necessario passare alla logica della "riga finale" a un certo punto per completare il labirinto.

Passaggio 1: inizializzare la prima riga

• Assegnare a ciascuna cella della riga un ID set univoco.

Passaggio 2: unire alcune celle adiacenti orizzontalmente

• Unisci casualmente le celle adiacenti impostandole sullo stesso ID set. Ciò assicura che ci siano passaggi orizzontali.

Passaggio 3: creare connessioni verticali alla riga successiva

• Per ogni set che appare nella riga, almeno una cella deve connettersi verso il basso (per garantire la connettività).
• Scegli casualmente una o più celle da ogni set per collegarle alla riga successiva.

Passaggio 4: passare alla riga successiva

• Proseguire le connessioni verticali assegnando lo stesso ID set alle celle corrispondenti sottostanti.
• Assegnare nuovi ID set a tutte le celle non assegnate.

Passaggio 5: ripetere i passaggi da 2 a 4 fino a raggiungere l'ultima riga

• Continua l'elaborazione riga per riga.

Fase 6: Elaborare la riga finale

• Assicuratevi che tutte le celle nell'ultima riga appartengano allo stesso set unendo tutti i set separati rimanenti.