Esta semana comencé a trabajar en un nuevo tema: la generación de mazmorras y cuevas. Utilicé particiones espaciales para generar habitaciones, algoritmos de generación de laberintos para generar corredores y autómatas celulares para dar a las cuevas un aspecto más natural.

División del espacio

Hay muchas formas de generar salas de mazmorras ( ubicación aleatoria , generación basada en agentes , utilizando el comportamiento de dirección de separación o un motor físico , etc.). Pero mi método favorito es dividir el espacio, porque es fácil de controlar y expandir.

También hay muchas formas de dividir el espacio: división en cuadrículas, división binaria del espacio, división del espacio por un árbol de cuadrantes, diagramas de Voronoi, etc. Decidí usar una partición binaria de espacio, porque es muy adecuada para generar habitaciones rectangulares. Este método ha ganado popularidad gracias a un artículo sobre RogueBasin.

La única complejidad de este algoritmo es la elección de la posición de separación. Si no imponemos una restricción en la posición de separación, obtendremos particiones extrañas del espacio:


Hay varias formas de evitar este comportamiento. Una de ellas es limitar la posición de separación a dos relaciones de aspecto, por ejemplo, en el rango de 30% a 70% o de 40% a 60%. Otra forma es usar una distribución normal o binomial en lugar de una distribución uniforme, lo que aumenta la probabilidad de separación en el centro del lado y no a lo largo de los bordes. Estos métodos solucionan el problema, pero es difícil entender cómo afectan exactamente los parámetros al resultado final.

Por lo tanto, utilicé otro método, cuya ventaja es que tiene un parámetro y se entiende fácilmente: la relación máxima permitida entre la longitud y el ancho de las celdas. Al muestrear una nueva división, primero calculo los valores mínimos y máximos que puede tener para que la proporción de dos celdas nuevas sea menor que el límite, y luego realizo un muestreo uniforme entre estos dos límites. Aquí está el resultado al variar la relación máxima permitida:


Se obtienen buenos resultados con una relación máxima de 2.0 a 3.0:

Generación de habitaciones

La siguiente etapa es la generación en cada celda de la habitación. Aquí no hay problemas especiales, solo establezco límites para que las habitaciones no sean demasiado pequeñas y no estén demasiado cerca de las paredes de las celdas.

Aquí están los resultados:

Selección de costillas

En los generadores de mazmorras de división binaria, el árbol binario utilizado en la etapa de división generalmente se reutiliza para generar corredores. No hice esto, porque ese enfoque me parece limitante.

En cambio, en la etapa de dividir el espacio, construyo la estructura de una lista de bordes doblemente conectada , lo que nos permite saber qué celdas están ubicadas una al lado de la otra. De esta manera obtengo los siguientes gráficos:


Hay tres ventajas en este enfoque. Primero: si en el futuro quiero cambiar la forma de dividir el espacio, el resto del generador seguirá siendo válido, ya que solo recibe una estructura de datos de semi-borde en la entrada. Segundo: ahora para seleccionar los bordes que se convertirán en corredores, puedo usar cualquier algoritmo para generar laberintos . Tercero: si quiero agregar bucles a la mazmorra, puedo implementar esto fácilmente.

Por ahora, solo uso el algoritmo de Kruskal y la distancia de las cuadras de la ciudad para seleccionar bordes. Aquí están los resultados:

Generación de corredor

El siguiente paso es generar corredores a partir de los bordes seleccionados. Esta es probablemente la parte más complicada del generador, porque tengo que tener cuidado para que ningún corredor se cruce con otro.

Aquí están los resultados:

Generación de cuevas

Los resultados anteriores fueron adecuados para crear mazmorras, criptas y otras estructuras hechas por el hombre, pero quería darle a las cuevas y minas un aspecto más natural. La forma clásica de generar cuevas es usar un autómata celular, como se describe en este artículo de RogueBasin. El gran problema con los autómatas celulares es que sus resultados no están completamente controlados.

De todos modos, decidí usar autómatas celulares para crear una apariencia natural, pero imponerles restricciones para obtener un resultado controlado. En lugar de solo dos estados: muerto y vivo, uso cuatro: absolutamente muerto, muerto, vivo, definitivamente vivo. Los estados "perfectamente precisos" no pueden cambiar en el proceso, se utilizan para limitar los resultados.

Las habitaciones y corredores generados en los pasos anteriores están llenos de celdas "exactamente vivas". Es decir, todavía tenemos salas de apoyo y garantizamos que estarán conectadas entre sí. Los bordes que no se han seleccionado se llenan con celdas "exactamente muertas" para que no aparezcan nuevas rutas entre las habitaciones. Finalmente, alrededor de habitaciones y corredores, aleatoriamente damos vida a algunas células. Aquí está la configuración inicial:


Entonces comenzamos el autómata celular:



Aquí hay algunos resultados de muestra más:


Más tarde agregaré un relleno para eliminar las partes inalcanzables.

Este es el primer paso en un largo viaje para crear un generador de mazmorras interesante. Estoy satisfecho con los resultados. Estoy especialmente orgulloso del método de autómatas celulares restringidos para crear cuevas controladas y naturales. También me gusta el hecho de que cada etapa de generación es independiente de las demás y puede modificarse individualmente.

Eliminar celdas aisladas

Luego implementé un relleno para eliminar celdas inaccesibles:

Múltiples pasillos entre habitaciones.

Al experimentar con los parámetros del generador, descubrí que si agregas un poco de ruido entre las habitaciones conectadas, obtienes resultados interesantes.

Aquí está la diferencia en los resultados antes de aplicar ruido a las habitaciones comunicadas e inmediatamente después, el parámetro cambia en solo una unidad:



Si hace que las habitaciones sean un poco más grandes, el resultado será aún más interesante:


Es genial que tengamos un accidente y surjan hermosas estructuras, pero al mismo tiempo, se conserva la estructura del gráfico y las designaciones de las habitaciones, lo que será útil:

Generación de azulejos para cuevas

Pasé la mayor parte de mi tiempo generando mosaicos. No es muy difícil, pero para la implementación correcta se necesitan algunos trucos.

Aquí hay resultados de muestra:


Lo mejor es que puedes cambiar fácilmente de una cueva de piedra a una arena o hielo:


Los próximos pasos para generar la mazmorra serán la adición de paisajes y monstruos.