Pocas cosas parecen tan caóticas —y, a la vez, tan hipnóticas— como un buen laberinto. Lo que para el lector es un pasatiempo de domingo, para matemáticos e informáticos es un terreno fértil donde poner a prueba ideas sobre aleatoriedad, grafos y recorridos. Entre todas las técnicas para generarlos, una destaca por su elegancia y por la garantía que ofrece: el algoritmo de Wilson, presentado en 1996 por el matemático David Bruce Wilson. Su promesa es contundente: producir laberintos perfectos y verdaderamente aleatorios.
A diferencia de métodos populares que tienden a “favoritismos” invisibles —por ejemplo, corredores demasiado rectos o sesgos hacia esquinas—, Wilson asegura que todas las configuraciones válidas para una cuadrícula dada tienen la misma probabilidad de aparecer. No hay trucos, no hay patrones repetidos: solo aleatoriedad uniforme sobre el conjunto de árboles generadores.
A continuación, una guía para entender qué lo hace especial, cómo funciona y por qué su influencia va más allá de los pasatiempos.
¿Qué significa “laberinto perfecto”?
En jerga de grafos, un laberinto perfecto es aquel que puede verse como un árbol de expansión (spanning tree) del grafo subyacente: hay exactamente un camino entre cualquier par de celdas. No hay ciclos (bucles) ni islas inaccesibles. Esta propiedad convierte al laberinto en un desafío “justo”: todo es alcanzable y no existen atajos redundantes que rompan el encanto del recorrido.
Generar árboles de expansión no es difícil; hacerlo de forma uniforme sí lo es. El algoritmo de Wilson aporta justamente eso: uniformidad. Cada árbol posible del grafo (piense en su cuadrícula) es equiprobable.
La idea clave: caminatas aleatorias con borrado de bucles
La técnica descansa sobre un objeto precioso de la probabilidad moderna: las caminatas aleatorias con borrado de bucles (loop-erased random walks, LERW). Imagine que recorre la cuadrícula al azar. Si alguna vez vuelve a pisar una celda que ya había visitado, habrá formado un bucle. El “truco Wilson” es borrar ese bucle por completo de la trayectoria —eliminando todos los pasos entre la primera y la segunda visita a la celda— y seguir caminando desde ahí. El resultado es una traza sin ciclos.
Con esa herramienta, el algoritmo se construye así:
- Elija una celda semilla. En una cuadrícula vacía (todas las celdas “negras”), marque una al azar como parte del laberinto (ponga esa celda “blanca”). Es la primera pieza del árbol.
- Arranque una caminata aleatoria desde otra celda. Tome al azar una celda negra y empiece a caminar al azar (arriba, abajo, izquierda, derecha). Mantenga un registro de su trayectoria. Si la caminata se cruza consigo misma, borre el bucle: retroceda en el registro hasta la primera aparición del cruce y elimine los pasos intermedios.
- Conecte y consolide. Siga así hasta que la caminata toque alguna celda blanca (parte ya del laberinto). En ese instante, todos los pasos de la caminata (tras borrar bucles) se fijan: se vuelven “blancos” y se incorporan al laberinto.
- Repita. Elija otra celda negra y repita el proceso. Cuando todas las celdas sean blancas, habrá construido un árbol de expansión de la cuadrícula: su laberinto perfecto.
La magia está en que, aunque la caminata individual es azarosa y local, el resultado global —al consolidar sucesivas LERW contra el árbol— reparte la probabilidad de forma uniforme sobre todos los árboles de expansión posibles del grafo. No hay configuraciones “privilegiadas”.
Por qué funciona (sin entrar en fórmulas)
Detrás del telón, el algoritmo se apoya en una conexión profunda entre LERW y los árboles generadores uniformes (uniform spanning trees, UST). Esa conexión, explorada en la década de 1990, garantiza que el procedimiento “semilla + LERW hasta el árbol” muestra exactamente la distribución uniforme de árboles. Traducción: si imagináramos todas las formas de tender caminos sin ciclos que conecten la cuadrícula completa, Wilson recorre ese catálogo sin favoritismos.
Un detalle operativo importante: el algoritmo solo fija un trayecto cuando toca el árbol ya construido. Antes de eso, la caminata es tentativa y borra cualquier bucle que aparezca. Esa disciplina evita que se formen ciclos y asegura que cada consolidación suma ramas al árbol sin cerrarlo sobre sí mismo.
¿Cómo se compara con otros generadores de laberintos?
- Búsqueda en profundidad (DFS) con retroceso: muy popular por su sencillez y velocidad. Produce laberintos perfectos, pero suele mostrar corredores largos y pocas bifurcaciones; es sesgado hacia ciertos patrones.
- Prim/Kruskal “aleatorizados”: variantes de estos clásicos para mínimos árboles de expansión también generan laberintos perfectos. En la práctica, si la aleatoriedad no se maneja con cuidado, suelen favorecer determinadas estructuras (por ejemplo, Prim tiende a “expander” desde una frontera, Kruskal a unir componentes dispersos).
- Aldous–Broder: otro algoritmo que utiliza caminatas aleatorias para obtener uniformidad. Es conceptualmente simple, pero menos eficiente: tarda más pasos en cubrir el grafo.
- Wilson: mantiene la uniformidad de Aldous–Broder con un comportamiento práctico muy competitivo gracias al borrado de bucles. En cuadrículas grandes ofrece tiempos esperados sólidos y escalables.
En resumen, si busca uniformidad garantizada, Wilson y Aldous–Broder son la elección. Entre ambos, Wilson suele ser la opción más eficiente para cuadrículas y grafos estructurados.
Implementarlo no es (tan) difícil: consejos prácticos
Aunque su sustento teórico es rico, implementarlo en código es asequible. Algunas pautas útiles:
- Estructuras de datos simples: mantenga un mapa de celdas “en el árbol” y una lista (o stack) para la caminata actual. Un diccionario que recuerde “desde dónde llegué a esta celda” ayuda a borrar bucles.
- Detección de bucles eficiente: use un hash (con las coordenadas de celda) para comprobar si la caminata ha visitado una celda antes. Si sí, borre desde la primera visita hasta la posición actual.
- Parada clara: la caminata se consolida cuando pisa cualquier celda del árbol. No necesita volver al origen.
- Selección aleatoria imparcial: en una cuadrícula 4-conexa (N, S, E, O), elija direcciones con probabilidad uniforme. Si algunas celdas están “bloqueadas”, descarte movimientos fuera de la cuadrícula.
- Visualización y depuración: dibujar el camino provisional en un color y el árbol en otro ayuda a comprobar que los bucles se borran y las ramas se fijan correctamente.
- Parámetros: el algoritmo generaliza a otras topologías: hexagonales, triangulares, grafos arbitrarios. Solo cambian los vecinos de cada nodo.
Un pseudocódigo compacto (a alto nivel):
árbol ← {celda_semilla}
mientras existan celdas fuera del árbol:
c ← celda_aleatoria no en árbol
camino ← [c]
visitadas_en_camino ← {c}
mientras c no esté en árbol:
c' ← vecino_aleatorio_de(c)
si c' ∈ visitadas_en_camino:
borrar el lazo desde la primera aparición de c' en camino
si no:
añadir c' a camino y a visitadas_en_camino
c ← c'
añadir todas las aristas de camino al árbol
Más allá del pasatiempo: dónde se usa de verdad
- Videojuegos: generación procedural de mazmorras, niveles y mapas donde se necesita jugabilidad (todo conecta) y variedad sin patrones obvios.
- Simulaciones en física: percolación, difusión, campos aleatorios; los árboles uniformes y las LERW conectan con fenómenos que modelan cómo “avanza” algo en un medio.
- Ciencias de la computación: redes y ruteo; a veces se requiere muestrear árboles de expansión con distribuciones uniformes para evaluar algoritmos o robustez.
- Matemáticas: estudio de estructuras aleatorias en grafos, límites de LERW (relación con curvas SLE en planos continuos) y propiedades de árboles uniformes.
Velocidad, memoria y tamaño: preguntas que siempre aparecen
La complejidad exacta depende del grafo, pero en cuadrículas regulares el algoritmo se comporta muy bien en la práctica. Es lineal en el número de celdas “más un factor suave” asociado a las caminatas aleatorias y a los bucles que borra. Además, su consumo de memoria es moderado: basta con guardar el árbol construido y el camino activo.
Para tamaños “de pasatiempo” (por ejemplo, 50 × 50 o 100 × 100 celdas) la generación es instantánea en máquinas actuales. Para cuadrículas mucho mayores, conviene prestar atención a la calidad del generador aleatorio y a la eficiencia en la detección/borrado de bucles.
Variantes y extensiones: cuando el purista cede al diseñador
Wilson, en su forma canónica, asegura uniformidad. Pero en videojuegos o arte generativo puede interesar sesgar levemente el resultado:
- Pesos direccionales: dar más probabilidad a ciertas direcciones (corredores “ventilados”, estética concreta).
- Obstáculos: celdas prohibidas o “caros” que obliguen a la caminata a rodear.
- Semillas múltiples: arrancar con varias celdas “blancas” (árboles iniciales), aunque esto altera la distribución.
Cada cambio implica renunciar a la uniformidad estricta; pero también es cierto que controlar la mano del azar puede ser deseable en determinados contextos estéticos o de diseño de niveles.
Un poco de historia, y por qué no fue “el primero”
Antes de Wilson, Aldous–Broder (finales de los 80 / principios de los 90) ya ofrecía una receta para obtener árboles uniformes con una sola caminata aleatoria que cubre toda la cuadrícula. ¿La pega? Que, sin borrar bucles, la caminata puede perder muchísimo tiempo revisitando nodos ya incorporados, lo que lo hace ineficiente en muchos grafos prácticos.
Wilson tomó la idea del paseante y le añadió el borrado de bucles, que ahorra trabajo y guía la consolidación hacia el árbol en construcción. El resultado es uniformidad con un rendimiento mucho más atractivo para cuadrículas y grafos “de la vida real”.
Una puerta de entrada a la aleatoriedad bien domada
En el algoritmo de Wilson conviven dos fuerzas que rara vez se llevan bien: la aleatoriedad pura y la estructura. La primera garantiza que no hay “maña” escondida; la segunda asegura que del caos no sale un amasijo de paredes, sino un laberinto perfecto, con un único camino entre cualquier dos puntos.
Esa alianza lo convierte en un ejemplo canónico de cómo las matemáticas no solo describen el azar: también lo canalizan para construir objetos útiles y bellos.
Preguntas frecuentes (FAQ)
¿Cómo implementar el algoritmo de Wilson en Python paso a paso?
A alto nivel, basta con: 1) representar la cuadrícula y sus vecinos; 2) elegir una semilla y marcarla en el árbol; 3) repetir: seleccionar una celda fuera del árbol, lanzar una caminata aleatoria con borrado de bucles hasta tocar el árbol, y consolidar esa traza; 4) terminar cuando todas las celdas estén en el árbol. Use un set para detectar visitas y una lista para el camino. Para visualizar, dibuje muros eliminando los que atraviesa el árbol.
¿En qué se diferencia Wilson de Prim/Kruskal para generar laberintos perfectos?
Prim/Kruskal “aleatorizados” también generan laberintos perfectos, pero su distribución no es uniformemente aleatoria a menos que se controlen muchos detalles. Suelen mostrar sesgos de estructura. Wilson (como Aldous–Broder) sí garantiza uniformidad sobre los árboles de expansión, con un rendimiento práctico mejor en cuadrículas gracias al borrado de bucles.
¿Por qué el algoritmo de Wilson produce laberintos “verdaderamente aleatorios”?
Porque su mecánica (caminatas con borrado de bucles que se consolidan al tocar el árbol) está demostrada para muestrear árboles de expansión con distribución uniforme. En una cuadrícula dada, cada árbol posible tiene la misma probabilidad de aparecer.
¿Dónde se usa el algoritmo de Wilson en videojuegos y generación procedural?
En mazmorras y mapas donde se busca que todo conecte (sin zonas muertas) y que las partidas no repitan patrones. Wilson es ideal para roguelikes, puzles, niveles con exploración, e incluso para distribuir habitaciones o pasillos con garantía de accesibilidad y variedad sin sesgos.
Si alguna vez se pierde entre paredes de papel, quizá haya detrás un caminante aleatorio borrando bucles con precisión quirúrgica. Y si le apetece construir sus propios laberintos, Wilson ofrece una puerta de entrada perfecta: pocas líneas de código, mucha teoría debajo y resultados impecables.
Idea sacada del artículo de Cruz Dogar