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 unico percorso tra due punti qualsiasi) utilizzando un approccio riga per riga. Produce labirinti simili all'algoritmo di Kruskal, ma lo fa generando una sola riga alla volta, senza la necessità di memorizzare l'intero labirinto in memoria. Questo 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, che lo rende ideale per labirinti infiniti o 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 ne dettaglino la 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 insiemi di celle connesse. Garantisce la connettività evitando loop e allunga 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 di set. Questo garantisce la presenza di 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 a caso 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

• Continuare l'elaborazione riga per riga.

Fase 6: Elaborare la riga finale

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

Ulteriori letture

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

• Generatore di labirinti con algoritmo Growing Tree
• Generatore di labirinti con algoritmo di Wilson
• Generatore di labirinti con backtracker ricorsivo