Es curioso echar un vistazo a Algoritmos para Laberintos, donde se muestran 15 formas de generar laberintos*. Aunque no todos son visualmente agraciados ni «complicados» desde el punto de vista de su resolución, explica todas las formas más o menos habituales de construirlos con un ordenador. Son algoritmos tanto clásicos como modernos, de código abierto y con animaciones paso a paso.
En total hay 15 algoritmos diferentes, cada uno con comportamientos y resultados claramente reconocibles. Se ofrecen en tres tamaños a partir de una retícula de 5×5, 15×15 y 25×25. Mis favoritos son el Recursive Backtracking y el Hunt and Kill. El resto me parece que generan caminos demasiado sencillos, que se acortan en uno o dos pasos y son casi triviales de resolver.
El código fuente completo está disponible públicamente en GitHub (CoffeeScript Mazes) y acompaña al libro Mazes for Programmers, que enseña los métodos desde un punto de vista práctico y que seguramente gustará a quienes les apasionen estos temas.
Entre los algoritmos incluidos hay enfoques deterministas, aleatorios e híbridos. Aparecen clásicos como Árbol binario y Sidewinder, métodos de caminatas aleatorias con garantías de uniformidad estadística como Aldous-Broder y Wilson y y técnicas recursivas. Hay combinaciones prácticas como el algoritmo de Houston, que mezcla el Aldous-Broder y el Wilson para ganar velocidad a costa de perder uniformidad.
_____
* Hay una diferencia sutil entre maze y labyrinth en inglés, palabras para las cuales solo usamos «laberinto» en castellano. Un labyrinth tiene una sola ruta sin bifurcaciones y no es difícil de seguir; solo tiene un entrada y una salida y pueden tener ciertas connotaciones «espirituales». En cambio los maze son más enrevesados, con muchas opciones y rutas que tomar, puede estar diseñado para ser más o menos difícil, quizá tenga varias entradas y salidas y son los que se utilizan en los experimentos científicos.
Relacionado:
- Un generador de laberintos y cuatro algoritmos para resolverlos
- El algoritmo de Wilson para generar laberintos
- Un algoritmo para crear laberintos «interesantes»
- Algoritmos de resolución de laberintos en acción
- Algoritmos para resolver laberintos
- Generador de laberintos
- Algorithms, de Erickson: más de 470 páginas sobre fundamentos e ideas
- Los algoritmos recursivos de vuelta atrás (backtracking)
