Generador de laberints de backtracker recursiu

L'algoritme recursiu de retrocés és realment una cerca en profunditat d'ús 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. Tendeix a produir laberints amb passadissos llargs i sinuosos i una solució molt llarga i sinuosa.

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 recursiu de retrocés és un mètode de cerca en profunditat per generar laberints perfectes (labirints sense bucles i amb un únic camí entre dos punts). És simple, 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 de manera iterativa utilitzant una cua LIFO (és a dir, una pila). Per a laberints molt grans, l'ús de la recursivitat és més probable que provoqui un desbordament de la pila de crides, depenent del llenguatge de programació i de la memòria disponible. Una cua LIFO es pot adaptar més fàcilment per gestionar 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'algoritme funciona mitjançant un enfocament de cerca en profunditat basat en pila. Aquí teniu el desglossament pas a pas:

1. Trieu una cel·la inicial i marqueu-la com a visitada.
2. Mentre hi ha cel·les no visitades: Mireu les cel·les veïnes que encara no s'han visitat. Si existeix almenys un veí no visitat: Trieu aleatòriament un dels veïns no visitats. Elimineu la paret entre la cel·la actual i el veí escollit. Moveu-vos 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: Retrocediu traient 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 a solucionador de laberints. Si l'executeu en un laberint ja generat i simplement us atureu quan arribeu al punt final decidit, la pila contindrà la solució del laberint.

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

Lectures addicionals

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

• Generador de laberints d'algoritmes d'Eller
• Caça i mata generador de laberints
• Generador de laberints d'algoritmes d'arbres en creixement