Advertisement
  1. Game Development
  2. Programming
Gamedevelopment

Generar Niveles de Cuevas Aleatorios Usando autómatas celulares

by
Difficulty:IntermediateLength:LongLanguages:

Spanish (Español) translation by Elías Nicolás (you can also view the original English article)

Los generadores de contenidos procedimentales son fragmentos de código escritos en tu juego que pueden crear nuevas piezas de contenido de juego en cualquier momento, incluso cuando el juego está en ejecución. Los desarrolladores de juegos han tratado de procesar generalizar todo, desde mundos 3D a bandas sonoras musicales. Añadir una cierta generación a su juego es una gran manera de conectar el valor adicional: los jugadores lo aman porque consiguen el contenido nuevo, impredecible y emocionante cada vez que juegan.

En este tutorial, veremos un gran método para generar niveles aleatorios y trataremos de estirar los límites de lo que se podría pensar que se puede generar.


¡Bienvenido a las cuevas!

En este tutorial, vamos a construir un generador de cuevas. Las cuevas son ideales para todo tipo de géneros y escenarios de juegos, pero me recuerdan particularmente a viejas mazmorras en juegos de rol.

Echa un vistazo a la demo a continuación para ver los tipos de salida que podrá obtener. Haga clic en "New World" para producir una nueva cueva para ver. Hablaremos de lo que los diferentes ajustes hacen a su debido tiempo.


Este generador realmente nos devuelve un gran array bidimensional de bloques, cada uno de los cuales es sólido o vacío. De hecho, podrías usar este generador para todo tipo de juegos además de los rastreadores de cuevas: niveles aleatorios para juegos de estrategia, cuadro de mapas para juegos de plataformas, tal vez incluso como arenas para un tirador multijugador. Si miras cuidadosamente, voltear los bloques sólidos y vacíos hace un generador de isla también. Todo utiliza el mismo código y salida, lo que hace que esta sea una herramienta muy flexible.

Empecemos haciendo una simple pregunta: ¿qué demonios es un autómata celular, de todos modos?


Introducción a las celulas

En la década de 1970, un matemático llamado John Conway publicó una descripción de El juego de la vida, a veces llamado simplemente Vida. "Vida" no era realmente un juego; Se parecía más a una simulación que tomaba una cuadrícula de células (que podían estar vivas o muertas) y les aplicaba algunas reglas sencillas.

Se aplicaron cuatro reglas a cada celda en cada paso de la simulación:

  1. Si una célula viva tiene menos de dos vecinos vivos, muere.
  2. Si una célula viva tiene dos o tres vecinos vivos, permanece viva.
  3. Si una célula viva tiene más de tres vecinos vivos, muere.
  4. Si una célula muerta tiene exactamente tres vecinos vivos, se vuelve viva.

¡Agradable y simple! Sin embargo, si usted prueba diferentes combinaciones de las redes de partida, puede obtener resultados muy extraños. Lazos infinitos, máquinas que escupen formas, y más. El Juego de la Vida es un ejemplo de un autómata celular - una cuadrícula de células que se rigen por ciertas reglas.

Vamos a implementar un sistema muy similar a la Vida, pero en lugar de producir patrones y formas divertidas, va a crear increíbles sistemas de cuevas para nuestros juegos.


Implementación de un autómata celular

Vamos a representar nuestra red celular como una matriz bidimensional de valores booleanos (true o false). Esto nos satisface porque sólo estamos interesados en si un azulejo es sólido o no.

Aquí estamos nosotros inicializando nuestra cuadrícula de células:

Consejo: Observe que el primer índice es la coordenada x de la matriz y el segundo índice es la coordenada y. Esto hace que el acceso a la matriz sea más natural en el código.

En la mayoría de los lenguajes de programación, esta matriz se inicializará con todos sus valores establecidos en false. Eso está bien para nosotros! Si un índice de matriz (x, y) es false, diremos que la celda está vacía; Si es true, ese azulejo será roca sólida.

Cada una de estas posiciones de matriz representa una de las "células" de nuestra red celular. Ahora necesitamos establecer nuestra red para que podamos comenzar a construir nuestras cuevas.

Vamos a empezar por establecer aleatoriamente cada célula a muertos o vivos. Cada celda tendrá la misma probabilidad aleatoria de ser vivificada, y deberías asegurarte de que este valor de probabilidad esté establecido en una variable en algún lugar, porque definitivamente queremos ajustarla más tarde y tenerla en algún lugar fácil de acceder nos ayudará con ese. Voy a usar el 45% para empezar.

Our random cave before any cellular automaton simulation steps
Nuestra cueva aleatoria antes de cualquier paso de simulación de autómatas celulares.

Si ejecutamos este código, terminamos con una gran cuadrícula de celdas como la anterior que están aleatoriamente vivas o muertas. Es desordenado, y definitivamente no se parece a ningún sistema de cuevas que he visto. Entonces, ¿Qué sigue?


Creciendo Nuestras Cuevas

¿Recuerdas que las reglas que rigen las células en El Juego De La Vida? Cada vez que la simulación avanzaba un paso, cada célula vería las reglas de la Vida y vería si cambiaría a estar vivo o muerto. Vamos a utilizar exactamente la misma idea para construir nuestras cuevas - vamos a escribir una función ahora que los bucles de cada célula de la red, y aplica algunas reglas básicas para decidir si vive o muere.

Como veremos más adelante, vamos a usar este bit de código más de una vez, así que ponerlo en su propia función significa que podemos llamarlo tantas o tan pocas veces como nos plazca. Le daremos un buen nombre informativo como doSimulationStep(), también.

¿Qué debe hacer la función? Bueno, primero, vamos a hacer una nueva cuadrícula en la que podamos poner nuestros valores de celda actualizados. Para entender por qué necesitamos hacer esto, recuerde que para calcular el nuevo valor de una celda en la cuadrícula, necesitamos mirar a sus ocho vecinos:

gdt_1

Pero si ya hemos calculado el nuevo valor de algunas de las celdas y las hemos vuelto a colocar en la cuadrícula, entonces nuestro cálculo será una mezcla de datos nuevos y antiguos, como esto:

gdt_2

¡Vaya! Eso no es lo que queremos en absoluto. Así que cada vez que calculamos un nuevo valor de celda, en lugar de volver a colocarlo en el mapa antiguo, lo vamos a escribir a uno nuevo.

Comencemos a escribir esa función doSimulationStep(), entonces:

Queremos considerar cada celda en la cuadrícula a su vez, y contar cuántos de sus vecinos están vivos y muertos. Contando a sus vecinos en una matriz es uno de esos bits aburridos de código que tendrá que escribir un millón de veces. Esta es una implementación rápida de la misma en una función que he llamado countAliveNeighbours():

Un par de cosas acerca de esta función:

En primer lugar, los bucles for son un poco raro si no has hecho algo como esto antes. La idea es que queremos ver todas las células que están alrededor del punto (x, y). Si observa la siguiente ilustración, puede ver cómo los índices que queremos son uno menos, igual a, y uno más que el índice original. Nuestros dos bucles for nos dan exactamente eso, comenzando en -1, y pasando por +1. A continuación, agregamos que al índice original dentro del bucle for encontrar a cada vecino.

gdt_3

En segundo lugar, observe cómo si estamos comprobando una referencia de cuadrícula que no es real (por ejemplo, está fuera del borde del mapa) lo contamos como un vecino. Yo prefiero esto para la generación de cuevas porque tiende a ayudar a llenar los bordes del mapa, pero puede experimentar no hacer esto si lo desea.

Así que ahora, volvamos a nuestra función doSimulationStep() y añadimos algo más de código:

Esto recorre todo el mapa, aplicando nuestras reglas a cada celda de cuadrícula para calcular el nuevo valor y colocarlo en newMap. Las reglas son más simples que el Juego de la Vida - tenemos dos variables especiales, una para el nacimiento de células muertas (birthLimit) y otra para matar células vivas (deathLimit). Si las células vivas están rodeadas por menos que deathLimit las células de muerte, mueren y si las células muertas están cerca de birthLimit al menos las células de nacimiento, se vuelven vivas. ¡Agradable y simple!

Todo lo que queda al final es un toque final para devolver el mapa actualizado. Esta función representa un solo paso de nuestras reglas de autómatas celulares - el siguiente paso es entender lo que sucede cuando lo aplicamos una vez, dos o más veces a nuestro mapa de inicio inicial.


Ajustes y puesta a punto

Veamos ahora cómo se ve el código de generación principal, usando el código que hemos escrito hasta ahora.

El único bit de código realmente nuevo es un bucle for que ejecuta nuestro método de simulación un número determinado de veces. Una vez más, pop en una variable para que podamos cambiar, porque vamos a empezar a jugar con estos valores ahora!

Hasta ahora hemos establecido estas variables:

  • ChanceToStartAlive establece lo denso que es la cuadrícula inicial con las células vivas.
  • StarvationLimit es el límite inferior del vecindario en el cual las células comienzan a morir.
  • OverpopLimit es el límite de vecindad superior en el cual las células comienzan a morir.
  • birthNumber es el número de vecinos que causan que una célula muerta se vuelva viva.
  • NumberOfSteps es el número de veces que realizamos el paso de simulación.
Our random cave after two cellular automaton simulation steps
Nuestra cueva al azar después de dos pasos de simulación de autómatas celulares.

Puede jugar con estas variables en la demo en la parte superior de la página. Cada valor cambiará la demostración dramáticamente, así que tenga un juego alrededor y vea qué trajes.

Uno de los cambios más interesantes que puede hacer es la variable numberOfSteps. A medida que ejecuta la simulación para más pasos, la rugosidad del mapa desaparece, y las islas se suavizan en nada. He añadido en un botón para que pueda llamar a la función manualmente, y ver los efectos. Experimente un poco y encontrará una combinación de ajustes que se adapte a su estilo y el tipo de niveles que su juego necesita.

Our random cave after six cellular automaton simulation steps
Nuestra cueva aleatoria después de seis pasos de simulación de autómatas celulares.

Con eso, ya está. Felicitaciones - usted acaba de hacer un generador de nivel de procedimiento, ¡bien hecho! Siéntate, corre y vuelve a ejecutar tu código, y sonríe a los extraños y maravillosos sistemas de cuevas que salen. Bienvenido al mundo de la generación de procedimientos.


Llevandolo más lejos

Si usted está mirando fijamente a su encantador generador de cuevas y preguntándose qué más puedes hacer con él, aquí están un par ideas de 'crédito adicional':

Uso del relleno de inundación para realizar comprobaciones de calidad

El relleno de inundación es un algoritmo muy simple que puede utilizar para encontrar todos los espacios en una matriz que se conectan a un punto en particular. Al igual que el nombre sugiere, el algoritmo funciona un poco como verter un cubo de agua en su nivel - se extiende desde el punto de partida y se llena en todas las esquinas.

El relleno de la inundación es grande para los autómatas celulares porque usted puede utilizarlo para ver cómo es grande una cueva particular. Si ejecuta la demostración algunas veces se dará cuenta de que algunos mapas están formados por una gran cueva, mientras que otros tienen unas cuantas cuevas más pequeñas que están separadas entre sí. El relleno de inundación puede ayudarte a detectar la gran cueva que hay y luego regenerar el nivel si es demasiado pequeño o decidir dónde quieres que empiece el jugador si crees que es lo suficientemente grande. Hay un gran esquema de relleno de inundaciones en Wikipedia.

Colocación rápida y sencilla de tesoros

Colocar el tesoro en áreas a veces requiere mucho código, pero en realidad podemos escribir un poco de código para colocar el tesoro fuera del camino en nuestros sistemas de cuevas. Ya tenemos nuestro código que cuenta cuántos vecinos tiene un cuadrado, por lo que haciendo un bucle sobre nuestro sistema de cuevas terminado, podemos ver cómo rodeado por las paredes de un cuadrado particular.

Si una celda vacía está rodeada por un montón de paredes sólidas, probablemente esté al final de un pasillo o escondido en las paredes del sistema de cuevas. Este es un gran lugar para esconder el tesoro - por lo que haciendo una simple comprobación de nuestros vecinos podemos deslizar el tesoro en las esquinas y callejones.

Esto no es perfecto. A veces pone el tesoro en los agujeros inaccesibles en el sistema de la cueva, ya veces las manchas serán bastante obvias, también. Pero, en una pizca, es una gran manera de dispersar coleccionables alrededor en su nivel. ¡Pruébelo en la demo pulsando el botón placeTreasure()!


Conclusiones y lecturas adicionales

Este tutorial le mostró cómo construir un generador de procedimientos básico pero completo. Con sólo unos sencillos pasos escribimos código que puede crear nuevos niveles en un abrir y cerrar de ojos. Esperemos que esto le ha dado una prueba del potencial de la construcción de generadores de contenido de procedimiento para sus juegos!

Si desea leer más, Roguebasin es una gran fuente de información sobre los sistemas de generación de procedimientos. Se centra principalmente en juegos roguelike, pero muchas de sus técnicas se pueden utilizar en otros tipos de juego, y hay mucha inspiración para la generación de procedimientos también otras partes de un juego!

Si quieres más información sobre la generación de contenido procedural o los autómatas celulares, aquí tienes una gran versión en línea de El juego de la vida (aunque te recomiendo que escribas "Conway's Game Of Life" en Google). ¡Tal vez también te guste Wolfram Tones, un encantador experimento en el uso de autómatas celulares para generar música!

Advertisement
Advertisement
Looking for something to help kick start your next project?
Envato Market has a range of items for sale to help get you started.