Generador de laberintos de caza y matanza

El algoritmo Hunt and Kill es en realidad una versión modificada del algoritmo Recursive Backtracker. La modificación consiste en escanear sistemáticamente (o "cazar") una nueva celda desde la que continuar cuando no se puede avanzar más, a diferencia de una verdadera búsqueda recursiva, que siempre volverá a la celda anterior en la pila.

Por este motivo, este algoritmo se puede adaptar fácilmente para generar laberintos con un aspecto y una sensación diferentes, simplemente eligiendo entrar en el modo "cacería" con más frecuencia o según reglas específicas. La versión implementada aquí solo entra en el modo "cacería" cuando no puede ir más allá de la celda actual.

Un laberinto perfecto es un laberinto en el que hay exactamente un camino desde cualquier punto del laberinto a cualquier otro punto. Eso significa que no puedes acabar dando vueltas en círculo, pero a menudo te encontrarás con callejones sin salida que te obligarán a dar media vuelta y volver atrás.

Los mapas de laberintos generados aquí incluyen una versión por defecto sin posiciones de inicio y final, para que puedas decidirlas por ti mismo: habrá una solución desde cualquier punto del laberinto a cualquier otro punto. Si quieres inspirarte, puedes activar una posición inicial y final sugeridas, e incluso ver la solución entre ambas.

Acerca del algoritmo Hunt and Kill

El algoritmo Hunt and Kill es un método simple pero efectivo para generar laberintos. Es algo similar a una búsqueda en profundidad (es decir, el algoritmo Recursive Backtracker), excepto que cuando no puede ir más allá de la posición actual, escanea sistemáticamente (o "busca") el laberinto para encontrar una nueva celda desde la que continuar. El algoritmo consta de dos fases principales: caminar y cazar.

Cómo funciona el algoritmo de caza y matanza para la generación de laberintos

Paso 1: Comience en una celda aleatoria

• Encuentre una celda al azar en la cuadrícula y márquela como visitada.

Paso 2: Fase de caminata (caminata aleatoria)

• Elige un vecino no visitado al azar.
• Muévete hacia ese vecino, márcalo como visitado y crea un camino entre la celda anterior y la nueva.
• Repita hasta que no queden vecinos sin visitar.

Paso 3: Fase de búsqueda (retroceso mediante escaneo)

• Escanee la cuadrícula fila por fila (o columna por columna).
• Encuentre la primera celda no visitada que tenga al menos un vecino visitado.
• Conecta esa celda a un vecino visitado para reanudar la fase de caminata.
• Repita hasta que se hayan visitado todas las celdas.