Generación de misiones utilizando aprendizaje automático clásico y redes neuronales recurrentes en estado zombie

Quizás esté familiarizado con la generación de niveles de procedimiento; Bueno, en esta publicación, se trata de generación de misiones procesales. Analizaremos el panorama general de la generación de misiones utilizando el aprendizaje automático clásico y redes neuronales recurrentes para juegos roguelike.

¡Hola a todos! Mi nombre es Lev Kobelev y soy diseñador de juegos en MY.GAMES. En este artículo, me gustaría compartir mi experiencia en el uso de ML clásico y redes neuronales simples mientras explico cómo y por qué nos decidimos por la generación de misiones procedimentales, y también profundizaremos en la implementación del proceso en Zombie. Estado.

Los conceptos básicos de la “caja” de misiones: oleadas, apariciones y más

☝🏻 Primero, algo de terminología: “ arenas ”, “ niveles ” y “ ubicaciones ” son sinónimos en este contexto, así como “ área ”, “ zona ” y “ área de generación ”.

Ahora, definamos “ misión ”. Una misión es un orden predeterminado en el que los enemigos aparecen en un lugar según ciertas reglas . Como se mencionó, en Zombie State se generan ubicaciones, por lo que no estamos creando una experiencia "escenificada". Es decir, no colocamos enemigos en puntos predeterminados; de hecho, no existen tales puntos. En nuestro caso, un enemigo aparece en algún lugar cerca de un jugador o de una pared específica. Además, todas las arenas del juego son rectangulares, por lo que se puede jugar cualquier misión en cualquiera de ellas.

Introduzcamos el término " spawn ". El desove es la aparición de varios enemigos del mismo tipo según parámetros predeterminados en puntos de una zona designada . Un punto, un enemigo. Si no hay suficientes puntos dentro de un área, ésta se expande según reglas especiales. También es importante entender que la zona se determina sólo cuando se activa un engendro. El área está determinada por los parámetros de generación, y consideraremos dos ejemplos a continuación: una generación cerca del jugador y otra cerca de una pared.

El primer tipo de aparición está cerca del jugador . La apariencia cerca del jugador se especifica a través de un sector, que se describe mediante dos radios: externo e interno (R y r), el ancho del sector (β), el ángulo de rotación (α) con respecto al jugador, y el visibilidad (o invisibilidad) deseada de la apariencia del enemigo. Dentro de un sector se encuentran la cantidad necesaria de puntos para los enemigos, ¡y de ahí vienen!

El segundo tipo de engendro está cerca de la pared . Cuando se genera un nivel, cada lado está marcado con una etiqueta: una dirección cardinal. El muro con la salida siempre está en el norte. La apariencia de un enemigo cerca de una pared se especifica mediante la etiqueta, la distancia desde ella (o), la longitud (a), el ancho de una zona (b) y la visibilidad (o invisibilidad) deseada de la apariencia del enemigo. El centro de una zona se determina en relación con la posición actual del jugador.

Los engendros vienen en oleadas . Una ola es la forma en que aparecen los engendros, es decir, el retraso entre ellos; no queremos golpear a los jugadores con todos los enemigos a la vez. Las oleadas se combinan en misiones y se lanzan una tras otra, según cierta lógica. Por ejemplo, se puede lanzar una segunda oleada 20 segundos después de la primera (o si más del 90% de los zombies que hay dentro mueren). Entonces, una misión completa puede considerarse como una caja grande, y dentro de esa caja, hay cajas de tamaño mediano (olas), y dentro de las olas, hay cajas aún más pequeñas (generaciones).

Entonces, incluso antes de trabajar en las misiones propiamente dichas, ya hemos definido algunas reglas:

1. Para mantener una sensación de acción constante, asegúrate de generar zombis regulares con frecuencia cerca del jugador en puntos visibles.
2. Para resaltar la salida o empujar al jugador desde un lado determinado, esfuérzate por generar principalmente enemigos de batalla de largo alcance cerca de las paredes.
3. En ocasiones, genera enemigos especiales frente al jugador, pero en puntos invisibles.
4. Nunca generes enemigos a menos de X metros del jugador.
5. Nunca generes más de X enemigos al mismo tiempo

En un momento dado, teníamos alrededor de cien misiones listas, pero después de un tiempo, necesitábamos aún más. Los otros diseñadores y yo no queríamos gastar mucho tiempo y esfuerzo creando otras cien misiones, así que comenzamos a buscar un método rápido y económico para generar misiones.

Generación de misiones

Descomposición de la misión

Todos los generadores funcionan según un conjunto de reglas, y nuestras misiones creadas manualmente también se realizaron según ciertas recomendaciones. Entonces, se nos ocurrió una hipótesis sobre los patrones dentro de las misiones, y esos patrones actuarían como reglas para el generador.

✍🏻 Algunos términos que encontrarás en el texto:

• La agrupación es la tarea de dividir una colección determinada en subconjuntos (clústeres) que no se superponen, de modo que objetos similares pertenezcan al mismo grupo y los objetos de diferentes grupos sean significativamente diferentes.

• Las características categóricas son datos que toman un valor de un conjunto finito y no tienen una representación numérica. Por ejemplo, la etiqueta del muro de generación: Norte, Sur, etc.

• La codificación de características categóricas es un procedimiento para convertir características categóricas en una representación numérica de acuerdo con algunas reglas previamente especificadas. Por ejemplo, Norte → 0, Sur → 1, etc.

• La normalización es un método de preprocesamiento de características numéricas para llevarlas a una escala común sin perder información sobre la diferencia en rangos. Se pueden utilizar, por ejemplo, para calcular la similitud de objetos. Como se mencionó anteriormente, la similitud de objetos juega un papel clave en los problemas de agrupamiento.

  
  

Buscar todos estos patrones manualmente llevaría mucho tiempo, por lo que decidimos utilizar la agrupación. Aquí es donde el aprendizaje automático resulta útil, ya que maneja bien esta tarea.

La agrupación funciona en algún espacio de N dimensiones y ML funciona específicamente con números. Por lo tanto todos los engendros se convertirían en vectores:

• Se codificaron variables categóricas.
• Todos los datos fueron normalizados.

Entonces, por ejemplo, el engendro que se describió como “genera 10 tiradores de zombies en la pared norte en un área con una hendidura de 2 metros, un ancho de 10 y una longitud de 5” se convirtió en el vector [0.5, 0.25, 0.2 , 0,8,…, 0,5] (←estos números son abstractos).

Además, el poder del conjunto de enemigos se redujo al asignar enemigos específicos a tipos abstractos. Para empezar, este tipo de mapeo facilitó la asignación de un nuevo enemigo a un grupo determinado. Esto también hizo posible reducir el número óptimo de patrones y, como resultado, aumentar la precisión de la generación, pero hablaremos de eso más adelante.

El algoritmo de agrupamiento

Existen muchos algoritmos de agrupación: K-Means, DBSCAN, espectral, jerárquico, etc. Todos se basan en ideas diferentes pero tienen el mismo objetivo: encontrar grupos de datos. A continuación, verá diferentes formas de encontrar grupos para los mismos datos, según el algoritmo elegido.

El algoritmo K-Means funcionó mejor en el caso de engendros.

Ahora, una pequeña digresión para aquellos que no saben nada sobre este algoritmo (no habrá un razonamiento matemático estricto ya que este artículo trata sobre el desarrollo de juegos y no sobre los conceptos básicos de ML). K-Means divide iterativamente los datos en K grupos minimizando la suma de las distancias al cuadrado de cada característica al valor medio de su grupo asignado. El promedio se expresa mediante la suma intragrupo de distancias al cuadrado.

Es importante comprender lo siguiente sobre este método:

• No garantiza el mismo tamaño de los grupos; para nosotros, esto no fue un problema ya que la distribución de los grupos dentro de una misión puede ser desigual.
• No determina la cantidad de grupos dentro de los datos, pero requiere un cierto número K como entrada, es decir, la cantidad deseada de grupos. A veces, este número se determina de antemano y, a veces, no. Además, no existe ningún método generalmente aceptado para encontrar el "mejor" número de conglomerados.

Veamos ese segundo punto con un poco más de detalle.

El número de grupos

El método del codo se utiliza a menudo para seleccionar el número óptimo de grupos. La idea es muy simple: ejecutamos el algoritmo y probamos todos los K desde 1 hasta N, donde N es un número razonable. En nuestro caso, fueron 10; fue imposible encontrar más grupos. Ahora, encontremos la suma de las distancias al cuadrado dentro de cada grupo (una puntuación conocida como WSS o SS). Mostraremos todo esto en un gráfico y seleccionaremos un punto después del cual el valor en el eje y deja de cambiar significativamente.

Para ilustrar, usaremos un conjunto de datos bien conocido, el Conjunto de datos de flores de iris. . Ejecutemos el algoritmo con K de 1 a 10 y veamos cómo la estimación anterior cambia dependiendo de K. Aproximadamente en K=3, la estimación deja de cambiar mucho, y esa es exactamente la cantidad de clases que había en el conjunto de datos original.

Si no puede ver el codo, puede utilizar el método Silhouette, pero está fuera del alcance de este artículo.

Todos los cálculos anteriores y siguientes se realizaron en Python utilizando bibliotecas estándar para ML y análisis de datos: pandas, numpy, seaborn y sklearn. No compartiré el código ya que el objetivo principal del artículo es ilustrar las capacidades en lugar de entrar en detalles técnicos.

Analizando cada cluster

Una vez obtenido el número óptimo de clusters, se debe estudiar cada uno de ellos en detalle. Necesitamos ver qué engendros se incluyen en él y los valores que toman. Creemos nuestra propia configuración para cada clúster para su uso en futuras generaciones. Los parámetros incluyen:

• Pesos enemigos para calcular la probabilidad. Por ejemplo, un zombie normal = 5 y un zombie con casco = 1. Por lo tanto, la probabilidad de que sea normal es 5/6 y la de un zombie con casco es 1/6. Las pesas son más cómodas de operar.
• El valor limita, por ejemplo, el ángulo mínimo y máximo de rotación de la zona o su ancho. Cada parámetro se describe mediante su propio segmento, cuyo valor es igualmente probable.
• Los valores categóricos, por ejemplo, una etiqueta de pared o la visibilidad de un punto, se describen como configuraciones del enemigo, y esto se hace mediante pesos.

Consideremos la configuración del grupo, que puede describirse verbalmente como "la aparición de enemigos simples en algún lugar cerca del jugador, a una distancia corta y, muy probablemente, en puntos visibles".

Tabla del grupo 1

Aquí hay dos trucos útiles:

• No se especifica un número fijo del enemigo, sino un segmento del cual se seleccionará su número. Esto ayuda a operar con el mismo enemigo en diferentes grupos pero en diferentes cantidades.
• No se especifica el radio exterior (R), sino el delta (R-delta) con respecto al radio interior (r), de modo que se respeta la regla R > r. Por lo tanto, R-delta se suma a r aleatorio, r+R-delta > r para cualquier R-delta > 0, lo que significa que todo está bien.

Esto se hizo con cada grupo y había menos de 10, por lo que no tomó mucho tiempo.

Algunas cosas interesantes sobre la agrupación

Sólo hemos tocado un poco este tema, pero aún quedan muchas cosas interesantes por estudiar. Aquí hay algunos artículos como referencia; Proporcionan una buena descripción de los procesos de trabajo con datos, agrupación y análisis de resultados.

• Pokmean — Agrupación de KMean en Pokedex
• Agrupación de juegos de League of Legends
• Agrupación de jugadores de campo FIFA20

Hora de una misión

Además de los patrones de generación, decidimos estudiar la dependencia de la salud total de los enemigos dentro de una misión del tiempo esperado de finalización para poder utilizar este parámetro durante la generación.

En el proceso de creación de misiones manuales, la tarea era establecer un ritmo coordinado para el capítulo: una secuencia de misiones: corta, larga, corta, nuevamente corta, y así sucesivamente. ¿Cómo puedes obtener la salud total de los enemigos dentro de una misión si conoces el DPS esperado del jugador y su tiempo?

💡 La regresión lineal es un método para reconstruir la dependencia de una variable de otra o de varias otras variables con una función de dependencia lineal. Los siguientes ejemplos considerarán exclusivamente la regresión lineal de una variable: f(x) = wx + b.

Introduzcamos los siguientes términos:

• HP es la salud total de los enemigos en la misión.
• DPS es el daño esperado del jugador por segundo.
• El tiempo de acción es la cantidad de segundos que el jugador pasa destruyendo enemigos en la misión.
• El tiempo libre es el tiempo adicional dentro del cual el jugador puede, por ejemplo, cambiar el objetivo.
• El tiempo esperado de misión es la suma de acción y tiempo libre.

Entonces, HP = DPS * tiempo de acción + tiempo libre. Al crear un capítulo del manual, registramos el tiempo esperado de cada misión; Ahora necesitamos encontrar tiempo para actuar.

Si conoce el tiempo esperado de la misión , puede calcular el tiempo de acción y restarlo del tiempo esperado para obtener tiempo libre : tiempo libre = tiempo de misión - tiempo de acción = tiempo de misión - HP * DPS. Luego, este número se puede dividir por el número promedio de enemigos en la misión y obtendrás tiempo libre por enemigo. Por lo tanto, todo lo que queda es simplemente construir una regresión lineal desde el tiempo esperado de la misión hasta el tiempo libre por enemigo.

Además, construiremos una regresión de la proporción de tiempo de acción respecto del tiempo de misión.

Veamos un ejemplo de cálculos y veamos por qué se utilizan estas regresiones:

1. Ingrese dos números: tiempo de misión y DPS como 30 y 70
2. Vea la regresión del porcentaje de tiempo de acción respecto del tiempo de misión y obtenga la respuesta: 0,8
3. Calcule el tiempo de acción como 30*0,8=6 segundos
4. Calcular HP como 6*70=420
5. Vea la regresión del tiempo libre por enemigo desde el tiempo de la misión y obtenga la respuesta, que es 0,25 segundos.

He aquí una pregunta: ¿por qué necesitamos saber el tiempo libre del enemigo? Como se mencionó anteriormente, los engendros se organizan por tiempo. Por lo tanto, el tiempo del i-ésimo desove se puede calcular como la suma del tiempo de acción del (i-1)ésimo desove y el tiempo libre dentro de él.

Y aquí surge otra pregunta: ¿por qué la proporción de tiempo de acción y tiempo libre no es constante?

En nuestro juego, la dificultad de una misión está relacionada con su duración. Es decir, las misiones cortas son más fáciles y las largas, más difíciles. Uno de los parámetros de dificultad es el tiempo libre por enemigo. Hay varias líneas rectas en el gráfico anterior y tienen el mismo coeficiente de pendiente (w), pero un desplazamiento diferente (b). Por lo tanto, para cambiar la dificultad, basta con cambiar el desplazamiento: aumentar b hace que el juego sea más fácil, disminuirlo lo hace más difícil y se permiten números negativos. Estas opciones le ayudan a cambiar la dificultad de un capítulo a otro.

Creo que todos los diseñadores deberían profundizar en el problema de la regresión, ya que a menudo ayuda a deconstruir otros proyectos:

• Tutorial de regresión lineal
• Proyecto de aprendizaje automático básico: regresión lineal
• Regresión lineal de aprendizaje Scikit para principiantes

Generando nuevas misiones

Entonces, logramos encontrar las reglas para el generador y ahora podemos pasar al proceso de generación.

Si piensas de manera abstracta, entonces cualquier misión se puede representar como una secuencia de números, donde cada número refleja un grupo de generación específico. Por ejemplo, misión: 1, 2, 1, 1, 2, 3, 3, 2, 1, 3. Esto significa que la tarea de generar nuevas misiones se reduce a generar nuevas secuencias numéricas. Después de la generación, simplemente necesita "expandir" cada número individualmente de acuerdo con la configuración del grupo.

Enfoque básico

Si consideramos un método trivial para generar una secuencia, podemos calcular la probabilidad estadística de que un engendro particular siga a cualquier otro engendro. Por ejemplo, obtenemos el siguiente diagrama:

La parte superior del diagrama es un grupo al que conduce, un vértice, y el peso del borde es la probabilidad del grupo de ser el siguiente.

Al recorrer dicho gráfico, podríamos generar una secuencia. Sin embargo, este enfoque tiene una serie de desventajas. Estos incluyen, por ejemplo, la falta de memoria (sólo conoce el estado actual) y la posibilidad de "quedarse atrapado" en un estado si tiene una alta probabilidad estadística de volverse a sí mismo.

✍🏻 Si consideramos este gráfico como un proceso, obtenemos una cadena de Markov simple.

Redes neuronales recurrentes

Pasemos a las redes neuronales, es decir, a las recurrentes, ya que no tienen las desventajas del enfoque básico. Estas redes son buenas para modelar secuencias como caracteres o palabras en tareas de procesamiento del lenguaje natural. En pocas palabras, la red está entrenada para predecir el siguiente elemento de la secuencia en función de los anteriores.

Una descripción de cómo funcionan estas redes está más allá del alcance de este artículo, ya que es un tema muy amplio. En lugar de ello, veamos lo que se necesita para la formación:

• Un conjunto de N secuencias de longitud L.
• La respuesta a cada una de las N secuencias es una uno-caliente vector, es decir, un vector de longitud C que consta de C-1 ceros y un 1, que indica la respuesta.
• C es la potencia del conjunto de respuestas.

Un ejemplo sencillo con N=2, L=3, C=5. Tomemos la secuencia 1, 2, 3, 4, 1 y busquemos subsecuencias de longitud L+1 dentro de ella: [1, 2, 3, 4], [2, 3, 4, 1]. Dividamos la secuencia en una entrada de L caracteres y una respuesta (objetivo): el (L+1)ésimo carácter*.* Por ejemplo, [1, 2, 3, 4] → [1, 2, 3] y [ 4]. Codificamos las respuestas en vectores one-hot, [4] → [0, 0, 0, 0, 1].

A continuación, puedes esbozar una red neuronal simple en Python usando tensorflow o pytorch. Puede ver cómo se hace esto utilizando los enlaces a continuación. Ya sólo queda iniciar el proceso de formación con los datos descritos anteriormente, esperar y... ¡luego ya podrás pasar a producción!

Los modelos de aprendizaje automático tienen ciertas métricas, como la precisión. La precisión muestra la proporción de respuestas dadas correctamente. Sin embargo, hay que verlo con cautela ya que puede haber desequilibrios de clase en los datos. Si no hay ninguno (o casi ninguno), entonces podemos decir que el modelo funciona bien si predice respuestas mejor que el azar, es decir, precisión > 1/C; si está cerca de 1, funciona muy bien.

En nuestro caso, el modelo mostró buena precisión. Una de las razones de estos resultados es la pequeña cantidad de grupos que se lograron gracias al mapeo de los enemigos según sus tipos y su equilibrio.

Aquí hay más materiales sobre RNN para aquellos interesados:

• Guía para principiantes sobre la generación de texto utilizando LSTM
• Abordar las sustancias tóxicas utilizando Keras
• Explorando los juegos avanzados de Gameboy

Proceso de generación

Configuración del generador

El modelo entrenado es fácilmente serializado , para que puedas usarlo como un activo en el motor, en nuestro caso, Unity. En consecuencia, el generador accede al modelo a través de una API y crea una secuencia de forma iterativa. El resultado se expande y se guarda en un archivo CSV independiente.

Para interactuar con el modelo, se crea una ventana personalizada en Unity donde los diseñadores del juego pueden configurar todos los parámetros necesarios de la misión:

• Nombre
• Duración
• Enemigos disponibles, ya que los enemigos aparecen gradualmente.
• Número de oleadas en la misión y distribución de la salud entre ellas.
• Modificadores de peso específicos del enemigo, que ayudan a seleccionar ciertos enemigos con más frecuencia, por ejemplo, otros nuevos.
• Etcétera

Después de ingresar a la configuración, solo queda presionar un botón y obtener un archivo que se puede editar si es necesario. Sí, quería generar misiones con antelación, y no durante el juego, para poder modificarlas.

Las etapas de la generación.

Veamos el proceso de generación:

1. El modelo recibe una secuencia como entrada y produce una respuesta: un vector de probabilidades de que el i-ésimo grupo sea el siguiente. El algoritmo tira los dados, si el número es mayor que la probabilidad de error , tomamos el más probable, en caso contrario es aleatorio. Este truco añade un poco de creatividad y variedad.
2. El proceso continúa hasta un número determinado de iteraciones. Es mayor que la cantidad de apariciones en cualquiera de las misiones creadas manualmente.
3. La secuencia continúa; es decir, cada número accede a los datos guardados del clúster y recibe valores aleatorios de ellos.
4. La salud dentro de los datos se resume y todo lo que es mayor que la salud esperada se elimina de la secuencia (su cálculo se analizó anteriormente).
5. Los engendros se dividen en oleadas dependiendo de la distribución de salud especificada y luego se dividen en grupos (para que aparezcan varios enemigos a la vez), y su tiempo de aparición se da como la suma de la acción y el tiempo libre del grupo de engendros anterior.
6. ¡La misión está lista!

Conclusiones

Entonces, esta es una buena herramienta que nos ayudó a acelerar varias veces la creación de misiones. Además, esto ayudó a algunos diseñadores a superar el miedo al "bloqueo del escritor", por así decirlo, ya que ahora se puede obtener una solución lista para usar en unos segundos.

En el artículo, utilizando el ejemplo de la generación de misiones, intenté demostrar cómo los métodos clásicos de aprendizaje automático y las redes neuronales pueden ayudar en el desarrollo de juegos. Hoy en día existe una gran tendencia hacia la IA generativa, pero no nos olvidemos de otras ramas del aprendizaje automático, ya que también son capaces de hacer muchas cosas.

¡Gracias por tomarse el tiempo de leer este artículo! Espero que te hagas una idea tanto del planteamiento de las misiones en ubicaciones generadas como de la generación de misiones. ¡No tengas miedo de aprender cosas nuevas, desarrollarte y crear buenos juegos!

Ilustraciones de shabbyrtist