Laberintos perfectos en una rejilla 40×28: recorrido recursivo, Wilson, Eller o Prim aleatorio; se resuelve con A* (Manhattan, 4-vecindad). Se pueden dibujar paredes y mover el inicio y la meta.
Sobre el modelo
Un laberinto perfecto es un árbol de expansión sobre la retícula de habitaciones: un solo camino entre celdas, mientras no se edite el campo. Se construye en la misma rejilla 40×28 que engineering/astar-dijkstra-grid. Las «habitaciones» son las celdas de índices impares (1,1)…; los pasillos abren tanto las habitaciones como la pared entre habitaciones vecinas, así que el laberinto queda conexo y sin ciclos hasta que se empiece a editar. Están el recorrido recursivo (pila DFS), Wilson (paseos al azar con borrado de bucles), Eller (fusión de conjuntos por filas con verticales al azar) y Prim aleatorio (el árbol crece desde un frente de aristas). Tras generar se lanza **A* con heurística de Manhattan y 4-vecindad** — el mismo modelo discreto que en el laboratorio de A*, sin diagonales ni celdas «caras». Se pueden añadir paredes, borrar pasillos y mover S/G; al moverlos, los extremos se fuerzan a ser transitables.
Para quién: Matemática discreta e informática: generadores de laberintos y camino más corto en una rejilla, junto a A*/Dijkstra.
Conceptos clave
laberinto perfecto
árbol de expansión
recorrido recursivo
algoritmo de Wilson
algoritmo de Eller
Prim aleatorio
búsqueda A*
heurística de Manhattan
Cómo funciona
Laberinto perfecto en 40×28: habitaciones en la retícula impar, los pasillos abren las paredes entre ellas — un árbol sin ciclos. Recorrido recursivo / Wilson / Eller / Prim dan distintos árboles aleatorios; luego el mismo A* de aula (4-vecindad, Manhattan) busca el camino más corto sobre las paredes ya hechas.
Preguntas frecuentes
¿Por qué los laberintos de Wilson y de Eller «se ven» distintos?
Ambos construyen árboles de expansión aleatorios sobre la misma retícula, pero otra aleatoriedad local (la raíz de Wilson, las decisiones horizontales de Eller) da un dibujo distinto a tamaño finito.
¿Es el mismo A* que en la página A* / Dijkstra?
Los mismos cuatro rumbos, la heurística de Manhattan y el costo unitario del paso por celdas libres. Aquí no hay diagonales, celdas con peso ni modos Dijkstra o voraz: solo el A* de aula.
¿Se puede romper la «perfección» del laberinto?
Sí: la goma crea un ciclo (un segundo camino entre regiones); paredes de más pueden romper la conexidad. A* mostrará la topología nueva; si no hay camino hasta G, no hay camino.