El otro día estaba en una fila aburrida, con el celular casi sin batería, e hice lo más analógico que existe: saqué la libretita que siempre llevo y empecé a garabatear un laberinto a mano. De esos de revista de pasatiempos. Y llegó la frustración de siempre: o dejaba un callejón sin salida en medio de la nada, o — peor — dibujaba sin querer un camino tan obvio que se podía resolver el laberinto antes de terminar de dibujarlo. Me quedé mirándolo y pensé: "¿cómo hace una computadora esto bien, todas las veces, sin hacer trampa?"
Llegué a casa y no pude soltar la idea. Investigué, reescribí el algoritmo desde cero, y el resultado está justo aquí abajo — vas a ver a la computadora derribando las paredes una a una, en vivo. Pero antes deja que te muestre el truco, porque es más simple (y más bonito) de lo que parece.
Qué es un laberinto "perfecto"
En la teoría de laberintos existe un término preciso para lo que yo intentaba (y fallaba en) dibujar a mano: el laberinto perfecto. La definición es elegante: entre dos puntos cualesquiera del laberinto existe exactamente un camino. Ni cero (nada de áreas aisladas, inaccesibles), ni dos o más (nada de atajos ni bucles). Uno, y solo uno.
Esto tiene una consecuencia preciosa: un laberinto perfecto no tiene ciclos ni rincones aislados. Si eres de exactas, ya lo hueles — esto es literalmente un árbol. Cada celda es un nodo, y los pasillos son las aristas que conectan nodos sin cerrar jamás un bucle. El problema "dibujar un laberinto perfecto" es, en el fondo, el problema "hacer crecer un árbol que cubra todas las celdas". Los matemáticos lo llaman árbol de expansión (spanning tree).
Cuando dibujaba a mano, fallaba justo aquí: sin darme cuenta, cerraba un bucle (creando dos caminos al mismo lugar) o dejaba una región suelta. La computadora no "tiene más cuidado" — solo sigue una regla que hace imposible equivocarse.
La idea: empieza con todo bloqueado y ve cavando
La forma más intuitiva de generar un laberinto perfecto empieza por lo opuesto de lo que uno imagina. En vez de dibujar caminos, empiezas con una cuadrícula donde todas las paredes existen — cada celda es una celda cerrada, amurallada por todos lados. Nada se conecta con nada.
Entonces "cavas". El algoritmo más encantador para esto es el backtracking recursivo (una búsqueda en profundidad, o DFS). Funciona así:
- Elige una celda para empezar y márcala como visitada.
- Mira sus vecinos que aún no han sido visitados.
- Si hay al menos uno, sortea uno, derriba la pared entre las dos celdas, muévete allí y apila la celda anterior.
- Si no hay ningún vecino sin visitar (estás en un callejón), retrocede (backtrack) desapilando hasta encontrar una celda que todavía tenga camino nuevo por explorar.
- Repite hasta que la pila se vacíe. Cuando se vacía, todas las celdas fueron visitadas — y el laberinto está listo.
El secreto que garantiza la perfección es una sola regla: solo derribas la pared hacia una celda aún no visitada. Como cada celda se visita una única vez, nunca creas un segundo camino hacia ella. Sin segundo camino, sin bucle. Sin bucle, árbol. Árbol = laberinto perfecto. Es casi imposible equivocarse — y eso es exactamente lo que le faltaba a mi libreta.
Es contraintuitivo, pero funciona: para garantizar un camino entre dos puntos cualesquiera, nunca piensas en los dos puntos. Solo sigues la regla local "no revisites a nadie" — y la propiedad global aparece gratis.
¿Por qué "recursivo", pero con pila?
La versión de libro es recursiva: la función se llama a sí misma para cada celda nueva. Bonita en el papel, pero en laberintos grandes la pila de llamadas del navegador desborda (Maximum call stack size exceeded — ya me la comí en la cara). La solución que usé aquí cambia la recursión de JavaScript por una pila explícita (un array). Es el mismo algoritmo, el mismo orden de visita, solo que manejo la pila a mano — y de paso es fácil animar: en cada cuadro doy un pasito y dibujo dónde están la celda actual y la pila.
Dos curiosidades que me encantaron
- El "sesgo" del algoritmo tiene cara. El backtracking recursivo produce laberintos con pasillos largos y sinuosos y pocas bifurcaciones — un estilo muy reconocible. Otros métodos tienen otras "firmas": el algoritmo de Prim hace laberintos llenos de callejones cortos; el de Wilson genera laberintos perfectamente "imparciales", sin sesgo alguno. Puedes reconocer qué algoritmo generó un laberinto con solo mirar su textura. Me parece precioso.
- Resolver es más fácil que generar. Como el laberinto perfecto es un árbol, hallar el camino de la entrada a la salida es trivial: no hay giro equivocado que cueste caro, porque no hay bucles que te atrapen dando vueltas. Una simple búsqueda encuentra el único camino. Puse un botón "resolver" en el juguete para que lo veas — enciende exactamente la única ruta.
Mi opinión honesta
Este es, de lejos, uno de mis algoritmos favoritos para mostrarle a quien está empezando — y eso que no tiene nada de matemática pesada. Captura una idea que uso todo el tiempo en el trabajo de verdad: reglas locales simples generan estructuras globales correctas. No necesitas orquestar el resultado entero desde arriba; defines bien el paso pequeño y la garantía emerge. Es el mismo principio detrás de la generación procedural de niveles en juegos, el ruteo automático de circuitos e incluso el enrutamiento de redes.
Y está el lado humano: fallaba a mano no por falta de inteligencia, sino por falta de una regla que me impidiera hacer trampa sin querer. Buena parte de programar bien es exactamente eso — diseñar restricciones que hagan imposible el error, en lugar de cruzar los dedos para no equivocarse.
Basta de charla — genera uno 👇
Abajo está el generador que escribí: JavaScript puro, en un <canvas>, sin ninguna biblioteca. Juega con los sliders de tamaño y de velocidad, presiona "generar de nuevo" cuantas veces quieras, y — si quieres ver el algoritmo trabajando — déjalo en modo animado para seguir la celda actual (resaltada) y la pila (el rastro) derribando pared por pared. Cuando termine, haz clic en "resolver" para ver encenderse el camino único.