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. [Crear tu propio Laberinto Wilson (y leer código en JS)](/files/generador-laberintos-wilson.html) * * * ## ¿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í: 1. **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. 2. **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. 3. **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. 4. **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”. [Crear tu propio Laberinto Wilson (y leer código en JS)](/files/generador-laberintos-wilson.html) * * * ## 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. [Crear tu propio Laberinto Wilson (y leer código en JS)](/files/generador-laberintos-wilson.html) * * * ## 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**. [Crear tu propio Laberinto Wilson (y leer código en JS)](/files/generador-laberintos-wilson.html) Idea sacada del artículo de [Cruz Dogar](https://cruzgodar.com/applets/wilsons-algorithm)