Generador de laberints d'algoritmes d'Eller

L'algoritme d'Eller és un algorisme de generació de laberints que produeix laberints perfectes (labirints sense bucles i amb un únic camí entre dos punts) de manera eficient utilitzant un enfocament fila per fila. Produeix laberints similars a l'algoritme de Kruskal, però ho fa generant només una fila a la vegada, sense necessitat d'emmagatzemar tot el laberint a la memòria. Això el fa útil per generar laberints molt grans en sistemes molt limitats i per a la generació de contingut procedimental.

Un laberint perfecte és un laberint en el qual hi ha exactament un camí des de qualsevol punt del laberint fins a qualsevol altre punt. Això vol dir que no pots acabar donant voltes, però sovint et trobaràs amb carrerons sense sortida, obligant-te a donar la volta i tornar enrere.

Els mapes de laberint generats aquí inclouen una versió predeterminada sense cap posició d'inici i d'arribada, de manera que les podeu decidir vosaltres mateixos: hi haurà una solució des de qualsevol punt del laberint fins a qualsevol altre punt. Si voleu inspiració, podeu activar una posició d'inici i d'arribada suggerida, i fins i tot veure la solució entre les dues.

Sobre l'algoritme d'Eller

L'algoritme d'Eller va ser introduït per David Eller.

L'algoritme destaca pel seu eficient mètode fila per fila per generar laberints, cosa que el fa ideal per a laberints infinits o laberints generats en temps real. Es cita habitualment en la literatura sobre generació de contingut procedimental i generació de laberints, però no he pogut trobar fonts primàries que detallin la seva publicació original.

Com funciona l'algoritme d'Eller per a la generació de laberints

L'algoritme d'Eller processa una fila a la vegada, mantenint i modificant conjunts de cel·les connectades. Assegura la connectivitat evitant els bucles i estén el laberint cap avall de manera eficient.

Teòricament es pot utilitzar per generar laberints infinits, però per assegurar-se que el laberint generat sigui realment resoluble, cal canviar a la lògica de "fila final" en algun moment per acabar el laberint.

Pas 1: Inicialitzar la primera fila

• Assigneu a cada cel·la de la fila un identificador de conjunt únic.

Pas 2: Uniu algunes cel·les adjacents horitzontalment

• Fusiona aleatòriament cel·les adjacents establint-les amb el mateix ID de conjunt. Això garanteix que hi hagi passatges horitzontals.

Pas 3: Crear connexions verticals amb la següent fila

• Per cada conjunt que apareix a la fila, com a mínim una cel·la s'ha de connectar cap avall (per garantir la connectivitat).
• Trieu aleatòriament una o més cel·les de cada conjunt per connectar-les a la següent fila.

Pas 4: Moure a la següent fila

• Continueu les connexions verticals assignant el mateix ID de conjunt a les cel·les corresponents a continuació.
• Assigneu nous identificadors de conjunt a qualsevol cel·la no assignada.

Pas 5: Repetiu els passos 2–4 fins que arribeu a l'última fila

• Continueu processant fila per fila.

Pas 6: Processar la fila final

• Assegureu-vos que totes les cel·les de l'última fila pertanyen al mateix conjunt fusionant els conjunts separats restants.

Lectures addicionals

Si t'ha agradat aquesta publicació, també et poden agradar aquests suggeriments:

• Generador de laberints d'algoritmes de Wilson
• Generador de laberints d'algoritmes de Kruskal
• Generador de laberints d'algoritmes d'arbres en creixement