Generador de laberintos de caza y matanza

El algoritmo Hunt and Kill es en realidad una versión modificada del Backtracker Recursivo. Esta modificación consiste en buscar sistemáticamente una nueva celda para continuar cuando ya no se puede avanzar más, a diferencia de una búsqueda recursiva real, que siempre regresa a la celda anterior en la pila.

Por ello, este algoritmo se puede adaptar fácilmente para generar laberintos con diferentes apariencias, simplemente activando el modo de "caza" con más frecuencia o siguiendo reglas específicas. La versión implementada aquí solo activa el modo de "caza" cuando no puede alejarse más 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 similar a una búsqueda en profundidad (es decir, el algoritmo Recursive Backtracker), excepto que, cuando no puede avanzar más desde la posición actual, explora sistemáticamente (o "caza") el laberinto para encontrar una nueva celda desde la que proceder. El algoritmo consta de dos fases principales: caminar y cazar.

Cómo funciona el algoritmo de cazar y matar 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 hasta 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 caza (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.

Lectura adicional

Si te ha gustado esta publicación, puede que también te gusten estas sugerencias:

• Generador de laberintos con retroceso recursivo
• Generador de laberintos del algoritmo de Wilson
• Generador de laberintos del algoritmo de Eller