Generador de laberints de backtracker recursiu

L'algoritme de seguiment recursiu és realment una cerca en profunditat de propòsit general. Quan s'utilitza per a la generació de laberints, es modifica lleugerament per triar el camí a l'atzar, mentre que si s'utilitza per a finalitats de cerca reals, normalment es cercaria cada nivell en ordre lineal. Acostuma a produir laberints amb passadissos llargs i sinuosos i una solució molt llarga i retorçada.

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.

L'algoritme de seguiment recursiu és un mètode de cerca en profunditat per generar laberints perfectes (laberints sense bucles i un sol camí entre dos punts qualsevol). És senzill, eficient i produeix laberints visualment atractius amb passadissos llargs i sinuosos.

Malgrat el seu nom, no necessàriament s'ha d'implementar mitjançant recursivitat. Sovint s'implementa en un enfocament iteratiu utilitzant una cua LIFO (és a dir, una pila). Per a laberints molt grans, és més probable que l'ús de la recursivitat provoqui un desbordament de la pila de trucades, depenent del llenguatge de programació i de la memòria disponible. Una cua LIFO es pot adaptar més fàcilment per manejar grans quantitats de dades, fins i tot mantenint la cua al disc o en una base de dades si la memòria disponible és insuficient.

Com funciona

L'algorisme funciona utilitzant un enfocament de cerca en profunditat basat en la pila. Aquí teniu el desglossament pas a pas:

1. Trieu una cel·la inicial i marqueu-la com a visitada.
2. Tot i que hi ha cel·les no visitades:
   • Mireu les cel·les veïnes que encara no han estat visitades.
   • Si hi ha almenys un veí no visitat:
     • Trieu a l'atzar un dels veïns no visitats.
     • Elimina la paret entre la cel·la actual i el veí escollit.
     • Aneu al veí escollit i marqueu-lo com a visitat.
     • Empenyeu la cel·la actual a la pila.
   • Si no hi ha veïns no visitats:
     • Fes marxa enrere fent esclatar l'última cel·la de la pila.
3. Continueu aquest procés fins que la pila estigui buida.

Un fet interessant sobre aquest algorisme és que funciona tant com a generador de laberints com com a solucionador de laberints. Si l'executeu en un laberint ja generat i només us atureu quan arribeu al punt final decidit, la pila contindrà la solució del laberint.

De fet, tinc dues versions d'aquest algorisme en joc en aquest lloc: una basada en una cua LIFO per generar laberints en aquesta pàgina i una basada en recursivitat per resoldre laberints, també laberints generats per altres algorismes (així és com es fan els mapes amb les solucions). Tenir dues versions diferents és només per a esports perquè sóc un nerd que ho trobo interessant, qualsevol podria haver funcionat per a tots dos ;-)