Generador de laberints d'algoritmes d'arbres en creixement

L'algoritme Growing Tree és interessant, perquè pot emular el comportament de diversos altres algoritmes, depenent de com es tria la següent cel·la durant la generació. La implementació d'aquesta pàgina utilitza un enfocament d'amplitud primer, semblant a una cua.

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 de l'arbre creixent

L'algoritme Growing Tree és un mètode flexible i potent per generar laberints perfectes. L'algoritme és interessant perquè pot emular el comportament de diversos altres algoritmes de generació de laberints, com ara l'algoritme de Prim, el retrocés recursiu i la divisió recursiva, depenent de com seleccioneu la següent cel·la a processar.

Com funciona l'algoritme de l'arbre creixent

Pas 1: Inicialització

• Comença amb una quadrícula de cel·les no visitades.
• Trieu una cel·la inicial aleatòria i afegiu-la a una llista.

Pas 2: Bucle de generació de laberints

• Mentre la llista de cel·les no estigui buida: seleccioneu una cel·la de la llista basant-vos en una estratègia específica (que s'explica a continuació). Traceu un passatge des de la cel·la seleccionada fins a un dels seus veïns no visitats (escollits a l'atzar). Afegiu el veí a la llista, ja que ara forma part del laberint. Si la cel·la seleccionada no té veïns no visitats, elimineu-la de la llista.

Pas 3: Rescissió

• L'algoritme acaba quan no hi ha més cel·les a la llista, és a dir, s'ha esculpit tot el laberint.

Estratègies de selecció de cel·les (flexibilitat de l'algoritme)

La característica definidora de l'algoritme Growing Tree és com tries quina cel·la processar a continuació. Aquesta elecció afecta dràsticament l'aspecte del laberint:

Cel·la més nova (comportament similar a una pila): Retroseguidor recursiu:

• Seleccioneu sempre la cel·la afegida més recentment.
• Produeix passadissos llargs i sinuosos amb molts carrerons sense sortida (com un laberint de cerca en profunditat).
• Els laberints solen tenir passatges llargs i són fàcils de resoldre.

Cel·la aleatòria (algoritme de Prim aleatoritzat):

• Trieu una cel·la aleatòria de la llista cada vegada.
• Crea un laberint més uniforme amb camins complexos i enredats.
• Menys passadissos llargs i més ramificacions.

Cel·la més antiga (comportament similar a una cua):

• Trieu sempre la cel·la més antiga de la llista.
• Genera laberints amb una dispersió més uniforme, com un patró de cerca d'amplitud primer.
• Passadissos curts i frondosos amb connexions denses.
• (Aquesta és la versió implementada aquí)

Enfocaments híbrids:

Combina estratègies per a diverses característiques del laberint. Per exemple:

• 90% més nou, 10% aleatori: Sembla principalment un laberint recursiu de retrocés, però amb ramificacions ocasionals que trenquen llargs passadissos.
• 50% més nou, 50% més antic: Equilibra llargs corredors amb un creixement arbustiu.

Lectures addicionals

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

• Generador de laberints d'algoritmes de Kruskal
• Generador de laberints d'algoritmes de Wilson
• Generador de laberints de backtracker recursiu