Generador de Laberintos

Construye un laberinto perfecto (un único camino entre dos celdas cualesquiera, sin bucles) sobre una rejilla rectangular, con uno de tres algoritmos clásicos. El retroseso recursivo produce pasillos largos y sinuosos, Prim produce un árbol más frondoso y ramificado, Kruskal produce un árbol equilibrado con longitudes de rama aproximadamente uniformes en todo el laberinto. Semilla opcional para un laberinto reproducible, superposición de solución opcional y descarga SVG / PNG. Todos los cálculos se ejecutan en tu navegador — nada se sube.

—

Celdas —

Muros en pie —

Longitud de la solución —

Solución / máximo —

Acerca de los algoritmos

Un laberinto perfecto es un árbol de expansión sobre el grafo de la rejilla: cada celda es alcanzable desde cualquier otra, y existe exactamente un camino entre dos celdas cualesquiera — por lo que el laberinto no tiene bucles. Los tres algoritmos difieren en la "forma" de ese árbol.

El retroseso recursivo es en profundidad: desde una celda inicial camina hacia un vecino aleatorio sin visitar, aplica recursión y vuelve atrás cuando se queda atascado. El resultado son pasillos largos y serpenteantes con giros pronunciados ocasionales.

El algoritmo de Prim es en anchura con una frontera aleatoria: rastrea el conjunto de muros que podrían derribarse a continuación, elige uno al azar y hace crecer el laberinto radialmente. El resultado es más frondoso, con ramas más cortas.

El algoritmo de Kruskal itera sobre una lista mezclada de cada muro interior y lo derriba si une dos regiones previamente desconectadas. El resultado es un árbol equilibrado donde cada rama tiene aproximadamente la misma longitud.

La misma semilla siempre produce el mismo laberinto, por lo que puedes fijar una semilla favorita y reconstruir el mismo puzle. La solución es un BFS desde la celda superior izquierda hasta la celda inferior derecha.