Generador y solucionador de laberintos

Los generadores de laberinto crean laberintos aleatorios y solvables utilizando diversos algoritmos, cada laberinto que produce características visuales distintivas y la dificultad de resolver. Esto es una herramienta y un rompecabezas — el jugador puede generar laberintos frescos de cualquier tamaño y tratar de resolverlos, o ver la generación y resolver algoritmos funcionan en tiempo real. Comprender algoritmos de generación diferente añade una dimensión educativa, ya que cada método produce laberintos con propiedades únicas: pasillos largos, muchos extremos muertos, ramas altas o patrones similares al río.

Reglas

1. Seleccione un tamaño de laberinto (anchura y altura) y un algoritmo de generación.
2. Genera el laberinto. El resultado es siempre un laberinto perfecto: exactamente un camino entre cualquier dos células, sin bucles, y sin áreas inalcanzables.
3. Resolver el laberinto encontrando el camino desde el principio (típicamente superior izquierda) hasta el final (típicamente inferior derecha).
4. Opcionalmente, vea la generación o solución algoritmo animado paso a paso.
5. Compare diferentes algoritmos para ver cómo afectan laberinto dificultad y apariencia.

Algoritmos de generación

• Recursive Backtracker (DFS): Comienza desde una célula aleatoria, talla un camino hacia un vecino no visto al azar, y retroceder cuando está atrapado. Produce pasillos largos y de viento con relativamente pocas ramas. Crea laberintos que se sienten orgánicos y son moderadamente difíciles de resolver.
• El Algoritmo del Príncipe Mantiene una frontera de los candidatos de la pared y selecciona aleatoriamente las paredes para quitar, creciendo el laberinto hacia fuera como un árbol. Produce laberintos con extremos muertos más cortos y más ramificados, creando una apariencia más arbustiva.
• El Algoritmo de Krishna. Aleatoriamente elimina las paredes entre las células en diferentes componentes conectados hasta que toda la red esté conectada. Produce laberintos muy uniformes sin sesgo aparente o patrón.
• División Recursiva: Comienza con una cuadrícula vacía y agrega repetidamente paredes con pasajes de una sola célula. Produce laberintos con paredes largas rectas y una apariencia distintiva de corte cruzado. Tendencias para ser más fácil de resolver.
• Aldous-Broder Algorithm: Un paseo aleatorio que talla pasajes a células no visibles. Produce laberintos perfectamente uniformes (todo el laberinto posible es igualmente probable) pero es muy lento para grandes rejillas.
• Algoritmo de Wilson: Usa paseos aleatorios de hojas de bucle para producir laberintos de árboles uniformes. Matemáticamente elegante y produce resultados imparciales, aunque con tiempo de generación variable.

El Algoritmo de Eller. Genera el laberinto una fila a la vez usando el seguimiento de conjuntos. Memoria-eficiente y puede generar laberintos infinitamente largos, ya que sólo necesita almacenar la fila actual.

• Árbol Benario: Cada célula se conecta a su vecino norte o oriental (elegido al azar). Extremadamente rápido y sencillo pero produce un sesgo diagonal notable. Cada laberinto tiene pasillos claros a lo largo de dos bordes.

Algoritmos de resolución

Siga la pared izquierda o derecha. Funciona para todos los laberintos simplemente conectados. Simple pero no óptimo.

• Breadth-First Search (BFS): Explora todas las células a distancia N antes de moverse a distancia N+1. Garantiza el camino más corto.

Depth-First Search (DFS): Explora lo más profundo posible antes de retroceder. Encuentra un camino (no necesariamente más corto) rápidamente.

• A* Buscar: Utiliza una distancia heurística (típicamente Manhattan al objetivo) para priorizar la exploración hacia la salida. Encuentra el camino más corto mientras explora menos células que BFS.
• Dead-End Filling: Identifica todos los extremos muertos y los llena hacia el cruce más cercano. El camino que queda sin llenar es la solución.
• El Algoritmo de Tremaux Un método sistemático para resolver cualquier laberinto marcando pasajes. Puede ser realizado por un humano caminando a través de un laberinto físico.

El estudio matemático de laberintos data siglos atrás, pero la generación algoritmo de laberintos comenzó con el advenimiento de las computadoras. Uno de los primeros algoritmos de generación de laberinto conocidos apareció en la década de 1970, cuando programadores hobbyistas en microcomputadoras tempranas como el Commodore PET y Apple II escribió programas simples para mostrar laberintos aleatorios en pantalla. El algoritmo "Binary Tree" fue uno de los primeros utilizados debido a su extrema sencillez — se puede implementar en sólo unas pocas líneas de BASIC.

El estudio formal de algoritmos de generación de laberinto conecta profundamente con la teoría del gráfico. Un laberinto perfecto (uno con exactamente un camino entre cualquier dos células) es matemáticamente equivalente a un árbol de la cuadrícula . Los diversos algoritmos de generación de laberinto son, de hecho, diferentes métodos para computar árboles aleatorios. Esta conexión fue formalizada en los años noventa, cuando los investigadores probaron que el algoritmo de Wilson y el algoritmo de Aldous-Broder producen árboles uniformes de azotes, lo que significa que cada laberinto posible es igualmente probable que se genere.

La generación de laberintos se convirtió en un elemento básico de la programación de la educación y la informática recreativa. Libros como "Mazes for Programmers" de Jamis Buck (2015) exploran sistemáticamente docenas de algoritmos de laberinto con implementaciones, y el tema es un ejercicio común en cursos de informática para enseñar algoritmos de gráficos, recursión y estructuras de datos. El atractivo visual de ver algoritmos genera laberintos paso a paso los hace populares en herramientas de visualización de algoritmos y tutoriales de programación.

En el mundo del juego, la generación de laberinto procesal es fundamental para el género pícaro, donde cada juego presenta una mazmorra generada aleatoriamente. Juegos como "Rogue" (1980), "NetHack" (1987), y títulos modernos como "Hades" (2020) y "Dead Cells" (2018) usan variantes de algoritmos de generación de laberinto para crear diseños de nivel repetibles. El campo sigue evolucionando, con investigadores que exploran la generación de laberinto 3D, cuadrículas no-rectangulares (hexagonal, triangular, circular) y algoritmos de generación que producen laberintos con características específicas de dificultad.