Recuerda que en las ciencias informáticas cualquier problema casi siempre tiene diversas soluciones, de igual modo nosotros aquí te mostramos lo mejor y más eficiente.
Solución:
Resulta que hay 11 algoritmos clásicos para generar laberintos “perfectos”. Un laberinto es perfecto si tiene una y sólo una solución. Aquí hay algunos enlaces a cada algoritmo, en orden aproximado de mi preferencia.
- de Kruskal
- Prim’s
- Rastreador recursivo
- Aldous Broder
- Árbol en crecimiento
- cazar y matar
- de wilson
- de Eller
- División recursiva (predecible)
- Sidewinder (predecible)
- Árbol binario (defectuoso)
Para obtener más información, consulte mazelib en GitHub, una biblioteca de Python que implementa todos los algoritmos estándar de generación y resolución de laberintos.
De http://www.astrolog.org/labyrnth/algrithm.htm
Rastreador de retroceso recursivo: Esto está algo relacionado con el método de resolución del rastreador de retroceso recursivo que se describe a continuación, y requiere una acumulación del tamaño del Laberinto. Al tallar, sea lo más codicioso posible y siempre corte en una sección sin hacer si hay una al lado de la celda actual. Cada vez que te muevas a una nueva celda, empuja la celda anterior en la pila. Si no hay celdas sin hacer al lado de la posición actual, mueva la pila a la posición anterior. El Laberinto se completa cuando sacas todo de la pila. Este algoritmo da como resultado laberintos con un factor de “río” lo más alto posible, con menos callejones sin salida pero más largos y, por lo general, una solución muy larga y sinuosa. Funciona bastante rápido, aunque el algoritmo de Prim es un poco más rápido. El retroceso recursivo no funciona como un sumador de pared, porque hacerlo tiende a dar como resultado una ruta de solución que sigue el borde exterior, donde todo el interior del Laberinto está unido al límite por un solo tallo.
Producen solo un 10% de callejones sin salida
es un ejemplo de un laberinto generado por ese método.
Una solución bastante sencilla podría ser asignar pesos aleatorios a los bordes del gráfico y aplicar el algoritmo de Kruskal para encontrar un árbol de expansión mínimo.
La mejor discusión sobre algoritmos de generación de laberintos: http://www.jamisbuck.org/presentations/rubyconf2011/index.html (estuvo en HN hace un par de días).