Generador de laberints d'algoritmes d'Eller

L'algoritme d'Eller és un algorisme de generació de laberints que produeix de manera eficient laberints perfectes (laberints sense bucles i un sol camí entre dos punts qualsevol) mitjançant un enfocament fila per fila. Produeix laberints similars a l'algorisme de Kruskal, però ho fa generant només una fila alhora, 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 enfocament eficient fila per fila per a la generació de laberints, el que el fa ideal per a laberints infinits o generats en temps real. Es cita habitualment a la generació de contingut procedimental i la literatura de 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 bucles i amplia el laberint cap avall de manera eficient.

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

Pas 1: inicialitzeu la primera fila

• Assigna a cada cel·la de la fila un ID de conjunt únic.

Pas 2: uneix algunes cel·les adjacents horitzontalment

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

Pas 3: creeu connexions verticals a la fila següent

• Per a cada conjunt que apareix a la fila, almenys 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-vos a la fila següent.

Pas 4: aneu a la fila següent

• Continueu les connexions verticals assignant el mateix identificador de conjunt a les cel·les corresponents a continuació.
• Assigna els nous ID de conjunt a les cel·les no assignades.

Pas 5: repetiu els passos 2-4 fins que s'arribi a l'última fila

• Continueu processant fila per fila.

Pas 6: processeu la fila final

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