Generador de laberints d'algoritmes d'arbres en creixement

L'algoritme Growing Tree és interessant, perquè pot emular el comportament de diversos altres algorismes, depenent de com s'esculli la següent cel·la durant la generació. La implementació d'aquesta pàgina utilitza un enfocament semblant a l'amplitud, semblant a la 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 creixement de l'arbre

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

Com funciona l'algoritme de creixement de l'arbre

Pas 1: Inicialització

• Comenceu amb una graella de cel·les no visitades.
• Trieu una cel·la inicial aleatòria i afegiu-la a una llista.

Pas 2: Bucle de generació del laberint

• Mentre la llista de cel·les no estigui buida:
  • Seleccioneu una cel·la de la llista en funció d'una estratègia específica (que s'explica a continuació).
  • Talla un passatge de la cel·la seleccionada a un dels seus veïns no visitats (triat aleatòriament).
  • Afegiu el veí a la llista ja que ara forma part del laberint.
  • Si la cel·la seleccionada no té veïnes no visitades, elimineu-la de la llista.

Pas 3: Terminació

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

Estratègies de selecció cel·lular (flexibilitat de l'algorisme)

La característica que defineix l'algoritme Growing Tree és com trieu quina cel·la processar a continuació. Aquesta elecció afecta de manera espectacular l'aspecte del laberint:

Cel·la més recent (comportament semblant a una pila) - Backtracker 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 aleatori):

• Escolliu una cel·la aleatòria de la llista cada vegada.
• Crea un laberint més uniformement distribuït amb camins complexos i embullats.
• Menys passadissos llargs i més ramificació.

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

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

Enfocaments híbrids:

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

• 90% més recent, 10% aleatori: sembla principalment un laberint de retrocés recursiu, però amb branques ocasionals que trenquen llargs passadissos.
• 50% més recent, 50% més antic: equilibra els llargs passadissos amb un creixement arbustiu.