En esta publicación describiré el algoritmo para la generación procesal de niveles de una mazmorra bidimensional con una estructura predeterminada. En la primera parte, se presentará una descripción general y, en la segunda, la implementación del algoritmo.
Introduccion
El algoritmo fue escrito como parte
de un trabajo de licenciatura y está basado en un artículo de
Ma et al (2014) . El objetivo del trabajo era acelerar el algoritmo y complementarlo con nuevas funciones. Estoy bastante contento con el resultado, porque creamos el algoritmo lo suficientemente rápido como para usarlo durante la ejecución del juego. Después de completar el trabajo de licenciatura, decidimos convertirlo en
un artículo y enviarlo a la conferencia Game-ON 2018.
Algoritmo
Para crear un nivel de juego, el algoritmo recibe como entrada un conjunto de bloques de construcción poligonales y un gráfico de conectividad de nivel (topología de nivel). Los nodos del gráfico indican las habitaciones, y los bordes determinan las conexiones entre ellos. El propósito del algoritmo es asignar a cada nodo del gráfico la forma y la ubicación de la habitación para que no se crucen dos formas de habitación, y cada par de habitaciones vecinas se pueden conectar por puertas.
(a)
(b)
(c)
(d)
Las figuras (c) y (d) muestran los diagramas generados a partir del gráfico de entrada (a) y los bloques de construcción (b).
Usando el gráfico de conectividad, un diseñador de juegos puede controlar fácilmente el flujo del juego. ¿Necesita una ruta común a la sala del jefe con varias rutas laterales opcionales? Simplemente comience con el gráfico de ruta y luego especifique algunos nodos en los que el jugador puede elegir: seguir la ruta principal o explorar la ruta lateral, con posibles tesoros y / o monstruos que lo esperan. ¿Necesitas cortar el camino? Simplemente seleccione los dos nodos en el gráfico y agregue un camino corto que los conecte. Las posibilidades de este esquema son infinitas.
Ejemplos de gráficos de entrada. La ruta principal se muestra en rojo, las rutas auxiliares son azules, la ruta corta es naranja.El algoritmo no solo permite a los diseñadores de juegos administrar la estructura de alto nivel de los mapas generados, sino que también proporciona la capacidad de controlar la apariencia de las habitaciones individuales y cómo conectarlas entre sí.
Diferentes formas para diferentes habitaciones.
Mencioné la habitación del jefe al final del nivel. No queremos que la sala del jefe se vea como cualquier otra sala común, ¿verdad? El algoritmo le permite establecer formularios para cada habitación. Por ejemplo, podemos crear una sala al comienzo del nivel y una sala de jefe, que debe tener sus propios conjuntos de formas de sala y un conjunto común para todas las demás salas.
Dos circuitos generados a partir del gráfico de entrada, en el que una forma especial de habitaciones está asociada con la habitación número 8.
Posiciones de puerta indicadas explícitamente
Imagine que tiene un guión de reunión de jefe de alta calidad y que necesitamos que el jugador ingrese a la sala del jefe desde un mosaico específico. O podemos tener una plantilla de habitación en la que algunos mosaicos están reservados para paredes y otros obstáculos. El algoritmo permite a los diseñadores establecer explícitamente posibles posiciones de puerta para formas de habitación individuales.
Pero a veces el objetivo puede ser lo contrario. Podemos crear plantillas de sala de tal manera que las puertas puedan estar en casi cualquier lugar. Debido a esto, imponemos menos restricciones al algoritmo; por lo tanto, a menudo se ejecuta más rápido y los circuitos generados pueden parecer menos monótonos y más orgánicos. Para tales situaciones, es posible simplemente indicar la longitud de las puertas y qué tan lejos deben estar de las esquinas. La distancia desde las esquinas es una especie de compromiso entre la disposición manual de todas las puertas y la presencia de puertas en cualquier lugar.
(a)
(b)
La figura (a) ilustra los diferentes tipos de colocación de puertas: una habitación cuadrada tiene 8 posiciones de puerta claramente definidas, y una habitación rectangular utiliza la longitud y la distancia desde las esquinas. La Figura (b) muestra un diagrama simple generado con las formas de las habitaciones en la Figura (a).
Pasillos entre habitaciones
Cuando hablamos de niveles de mazmorras, a menudo imaginamos habitaciones conectadas por pasillos estrechos. Me gustaría suponer que las conexiones en el gráfico de entrada indican los corredores, pero no lo son. Simplemente garantizan que todos los nodos vecinos se conectarán directamente por puertas. Si queremos que las habitaciones estén conectadas por corredores, entonces debemos insertar un nuevo nodo entre todos los pares de habitaciones vecinas y pretender que se trata de habitaciones de pasillo (con ciertas formas de habitaciones y posiciones de puertas dadas).
(a)
(b)
Una ilustración de cómo podemos modificar el gráfico de entrada para agregar corredores entre habitaciones. La figura (a) muestra el gráfico de entrada antes de agregar las habitaciones del corredor. La Figura (b) muestra el gráfico de entrada creado a partir de (a) al agregar nuevas habitaciones entre todas las habitaciones adyacentes del gráfico original.
Desafortunadamente, esto complica enormemente la tarea del algoritmo, porque a menudo el número de nodos se duplica. Por lo tanto, implementé una versión del algoritmo que tiene en cuenta los corredores, lo que permite reducir la disminución en el rendimiento al organizar las salas de los corredores. Por el momento, el algoritmo admite corredores entre todas las habitaciones o la ausencia total de corredores, pero en el futuro planeo hacerlo más flexible.
Ejemplos
Varios esquemas generados a partir de diferentes conjuntos de bloques de construcción y con corredores activados.Varios esquemas generados a partir de diferentes conjuntos de bloques de construcción con corredores activados y desactivados.En la segunda parte de la publicación hablaré sobre el funcionamiento interno del algoritmo.
También estoy trabajando en un complemento de Unity para la generación de mazmorras de procedimiento, que incluirá este algoritmo. Hago esto porque a pesar de la posibilidad de usar este algoritmo directamente en Unity (está escrito en C #), la conveniencia de trabajar con él está lejos de ser ideal. Se necesita mucho tiempo para crear plantillas de sala sin una GUI, y se necesita mucho código para convertir la salida del algoritmo a la representación utilizada dentro del juego.
Como yo mismo no soy un desarrollador de juegos, mi objetivo es hacer que el complemento sea lo suficientemente bueno para que otras personas lo usen. Si todo va bien, intentaré publicar actualizaciones cuando tenga algo interesante que decir. Ya tengo algunas ideas sobre el generador en sí y sobre cómo probar sus capacidades.
Capturas de pantalla del complemento Unity (el proyecto está en desarrollo)Parte 2. Implementación del algoritmo.
En esta parte, hablaré sobre las ideas básicas establecidas en la base del algoritmo descrito en la primera parte de la publicación. Inicialmente, quería describir los conceptos básicos junto con las principales mejoras necesarias para que el algoritmo sea lo suficientemente rápido. Sin embargo, resultó que incluso los conceptos básicos son más que suficientes para esta publicación. Por lo tanto, decidí revelar mejoras de rendimiento en un artículo futuro.
Motivación
Antes de pasar a la implementación, quiero mostrar el resultado de lo que haremos. El siguiente video muestra 30 circuitos diferentes generados a partir de un gráfico de entrada y un conjunto de bloques de construcción. El algoritmo siempre se detiene durante 500 ms después de generar el circuito, y luego intenta generar el siguiente.
Como funciona
El propósito del algoritmo es asignar la forma y la posición de la habitación a cada nodo en el gráfico para que no se crucen dos habitaciones y las habitaciones vecinas estén conectadas por puertas.
Una forma de lograr esto es probar todas las combinaciones posibles de formas de habitación y sus posiciones. Sin embargo, como puede suponer, esto será muy ineficiente y probablemente no podremos generar circuitos, incluso basados en gráficos de entrada muy simples.
En lugar de buscar todas las combinaciones posibles, el algoritmo calcula cómo conectar correctamente todas las habitaciones individuales (los llamados espacios de configuración) y utiliza esta información para dirigir la búsqueda. Desafortunadamente, incluso con esta información, todavía es bastante difícil encontrar el esquema correcto. Por lo tanto, para un estudio efectivo del espacio de búsqueda, utilizamos una técnica de optimización probabilística (en este caso, simulación de recocido). Y para una mayor aceleración de la optimización, dividimos la tarea de entrada en subtareas más pequeñas y fáciles de resolver. Esto se hace dividiendo el gráfico en partes más pequeñas (llamadas cadenas) con la creación posterior de esquemas para cada uno de ellos en orden.
Espacios de configuración
Para un par de polígonos en los que uno está fijo en su lugar y el otro puede moverse libremente, el espacio de configuración es el conjunto de posiciones de un polígono libre en el que dos polígonos no se cruzan y pueden conectarse por puertas. Cuando se trabaja con polígonos, cada espacio de configuración puede representarse como un conjunto de líneas posiblemente vacío y calcularse mediante herramientas geométricas simples.
(a)
(b)
Configuraciones espaciales. La figura (a) muestra el espacio de configuración (líneas rojas) de un rectángulo libre en relación con un polígono fijo en forma de L. Determina todas las ubicaciones del centro del cuadrado en el que los dos bloques no se cruzan y se tocan. La figura (b) muestra la intersección (puntos amarillos) de los espacios de configuración de un cuadrado en movimiento con respecto a dos rectángulos fijos.
El siguiente algoritmo se utiliza para calcular el espacio de configuración de un bloque fijo y uno libre. Seleccionamos un punto de referencia en el bloque móvil y consideramos todas las ubicaciones en
, de modo que al mover el polígono de modo que su punto de referencia esté ubicado en esta ubicación, tanto los bloques móviles como los fijos se tocan, pero no se cruzan. El conjunto de todos estos puntos forma el espacio de configuración de dos bloques (Figura (a) arriba). Para obtener el espacio de configuraciones del bloque móvil con respecto a dos o más bloques fijos, se calcula la intersección de los espacios de configuración individuales (Figura (b) anterior).
El algoritmo usa espacios de configuración de dos maneras. Primero, en lugar de probar las posiciones aleatorias de habitaciones individuales, usamos espacios de configuración para buscar posiciones que conduzcan al mayor número posible de habitaciones adyacentes conectadas por las puertas. Para hacer esto, necesitamos obtener la intersección máxima no vacía de los espacios de configuración de los vecinos. En segundo lugar, usamos espacios de configuración para verificar si todos los pares de habitaciones vecinas pueden conectarse con puertas. Esto se hace comprobando si la posición de la habitación está dentro del espacio de configuración de todos sus vecinos.
Dado que las formas de las salas no cambian durante la ejecución del juego, podemos calcular previamente los espacios de configuración de todos los pares de formas de salas antes de que comience el algoritmo. Gracias a esto, todo el algoritmo se acelera significativamente.
Esquema incremental
Al resolver un problema complejo, uno de los enfoques posibles es dividirlo en subtareas más pequeñas y más simples, y resolverlas ya. Esto es exactamente lo que haremos con la tarea de colocar habitaciones individuales. En lugar de organizar todas las habitaciones a la vez, dividimos el gráfico de entrada en subgráficos más pequeños e intentamos crear diagramas a partir de ellos uno por uno. Los autores del algoritmo original llaman a estos subgrafos "cadenas" debido al principio mismo de estos gráficos, en el que cada nodo no tiene más de dos vecinos, y por lo tanto, es bastante simple crear su esquema.
El circuito de salida final siempre es un componente conectado, por lo que no tiene sentido conectar los componentes individuales al circuito y luego intentar combinarlos, porque el proceso de combinación puede ser bastante complicado. Por lo tanto, después de colocar la cadena, la siguiente cadena conectada siempre será la que esté conectada a los vértices ya alineados en el circuito.
Layout GenerateLayout(inputGraph) { var emptyLayout = new Layout(); var stack = new Stack<Layout>(); stack.Push(emptyLayout); while(!stack.Empty()) { var layout = stack.Pop(); var nextChain = GetNextChain(layout, inputGraph); Layout[] partialLayouts = AddChain(layout, nextChain); if (!partialLayouts.Empty()) { if (IsFullLayout(partialLayouts[0])) { return partialLayouts[0]; } else { stack.Push(partialLayouts); } } } return null; }
Pseudocódigo que muestra un enfoque incremental para encontrar el esquema correcto.El pseudocódigo que se muestra arriba demuestra la implementación de un esquema incremental. En cada iteración del algoritmo (líneas 6-18), primero tomamos el último circuito de la pila (línea 7) y calculamos qué cadena agregar a continuación (línea 8). Esto se puede hacer simplemente almacenando el número del último circuito agregado a cada circuito parcial. En el siguiente paso, agregamos la siguiente cadena al circuito (línea 9), generando varios circuitos detallados y los guardamos. Si la fase de expansión falla, pero no se agregan nuevos esquemas parciales a la pila, y el algoritmo debe continuar con el último esquema parcial guardado. Llamamos a esta situación una búsqueda de retorno porque el algoritmo no puede extender el esquema parcial actual y debe regresar y continuar con otro esquema guardado. Esto generalmente es necesario cuando no hay suficiente espacio para conectar circuitos adicionales a los vértices ya compuestos en el circuito. Además, una búsqueda de retorno es la razón por la que siempre intentamos generar varios esquemas avanzados (línea 9). De lo contrario, no tendríamos nada a lo que volver. El proceso finaliza cuando generamos un circuito completo o la pila está vacía.
(a) Gráfico de entrada
(b) Diagrama parcial
(c) Diagrama parcial
(d) Esquema completo
(e) Esquema completo
Esquema incremental. Las figuras (b) y (c) muestran dos diagramas parciales después de planificar el primer circuito. La figura (d) muestra el circuito completo después de la expansión (b) por un segundo circuito. La figura (e) muestra el circuito completo después de la expansión (c) por un segundo circuito.
Para dividir el gráfico en partes, debe encontrar una incrustación plana del gráfico de entrada, es decir, un dibujo en el plano en el que los bordes se cruzan solo en los puntos finales. Este archivo adjunto se utiliza para obtener todas las caras del gráfico. La idea principal de la descomposición es que es más difícil crear un circuito a partir de ciclos, porque sus nodos tienen más restricciones. Por lo tanto, estamos tratando de organizar los ciclos al comienzo de la descomposición, de modo que se procesen lo antes posible y se reduzca la probabilidad de que sea necesario volver a las etapas posteriores. La primera cadena de descomposición está formada por la cara más pequeña del archivo adjunto, y las caras posteriores se agregan en el orden de búsqueda de amplitud. Si hay otras caras que se pueden seleccionar, se usa la más pequeña. Cuando no quedan caras, se agregan los componentes no cíclicos restantes. La Figura 4 muestra un ejemplo de descomposición en una cadena, que se obtuvo de acuerdo con estos pasos.
(a)
(b)
Descomposición en cadenas. La figura (b) muestra un ejemplo de cómo diseñar la figura (a) en un circuito. Cada color representa una cadena separada. Los números indican el orden en que se crean las cadenas.
(c) Buen diseño parcial
(d) Esquema completo
(a) Gráfico de entrada
(b) Gráfico parcial incorrecto
Búsqueda con retorno. La figura (b) muestra un ejemplo de un circuito parcial deficiente, porque no hay suficiente espacio en él para conectar los nodos 0 y 9. Para generar el circuito completo (d), es necesario un retorno a otro circuito parcial (c).
Recocido simulado
El algoritmo de simulación de recocido es una técnica de optimización probabilística cuyo propósito es estudiar el espacio de posibles circuitos. Fue elegido por los autores del artículo original porque resultó ser útil en situaciones similares en el pasado. Al implementar el algoritmo, decidí usar el mismo método, porque quería comenzar con lo que ya ha demostrado su efectividad para resolver este problema. Sin embargo, creo que puede ser reemplazado por otro método y mi biblioteca está escrita de tal manera que el proceso de reemplazo del método es bastante simple.
El algoritmo de simulación de recocido evalúa iterativamente pequeños cambios en la configuración o circuito actual. Esto significa que creamos una nueva configuración seleccionando aleatoriamente un nodo y cambiando su posición o forma. Si la nueva configuración mejora la función de energía, siempre se acepta. De lo contrario, hay pocas posibilidades de aceptar la configuración de todos modos. La probabilidad de tomar peores decisiones disminuye con el tiempo. La función de energía está diseñada de tal manera que impone grandes multas en los nodos que se cruzan y los nodos adyacentes que no se tocan entre sí.
A es el área de intersección total entre todos los pares de bloques en el diagrama. D es la suma de los cuadrados de las distancias entre los centros de los pares de bloques en el gráfico de entrada que son vecinos pero no se tocan entre sí. Valor
afecta la probabilidad de que el recocido simulado se permita ir a la peor configuración; Este parámetro se calcula a partir del área promedio de bloques de construcción.
Después de seleccionar un nodo para cambiar, cambiamos su forma o posición. ¿Cómo elegimos un nuevo puesto? Puede elegirlo al azar, pero esto a menudo degradará la función de energía y el algoritmo convergerá muy lentamente. ¿Podemos elegir una posición que sea más probable que aumente la función energética? ¿Ves a lo que me dirijo? Utilizamos espacios de configuración para seleccionar una posición que satisfaga los límites del mayor número de habitaciones vecinas.
Luego, para cambiar la forma, simplemente seleccione una de las formas de habitación disponibles. Si bien el algoritmo no intenta decidir qué forma es más probable que nos lleve al esquema correcto. Sin embargo, sería interesante probar esta función y ver si acelera el algoritmo.
List<Layout> AddChain(chain, layout) { var currentLayout = GetInitialLayout(layout, chain); var generatedLayouts = new List<Layout>(); for (int i = 1; i <= n, i++) { if () { break; } for (int j = 1; j <= m, j++) { var newLayout = PerturbLayout(currentLayout, chain); if (IsValid(newLayout)) { if (DifferentEnough(newLayout, generatedLayouts)) { generatedLayouts.Add(newLayout); } } if () { currentLayout = newLayout; } else if () { currentLayout = newLayout; } } } return generatedLayouts; }
Este es el pseudocódigo del método responsable de crear un circuito de circuito separado simulando el recocido.
Para acelerar todo el proceso, intentaremos encontrar la configuración inicial de baja energía. Para hacer esto, organizaremos los nodos en la cadena actual para una búsqueda de amplitud, comenzando por aquellos que son adyacentes a los nodos ya incluidos en el esquema. Luego, los nodos ordenados se colocan uno a la vez y para ellos se selecciona la posición con la energía más baja del espacio de configuración. Aquí no estamos retrocediendo: este es un proceso simple y codicioso.
Video de bonificación
El siguiente video muestra los diagramas generados a partir del mismo gráfico de entrada que en el primer video. Sin embargo, esta vez se muestra un enfoque incremental. Puede notar que el algoritmo agrega cadenas de nodos uno a la vez. También se ve que a veces hay dos circuitos parciales consecutivos con el mismo número de nodos. Esto sucede cuando el algoritmo regresa. Si los primeros intentos de agregar otro circuito al primer circuito parcial fallan, entonces el algoritmo intenta otro circuito parcial.
Materiales descargables
La implementación del algoritmo en .NET se puede encontrar en
mi github . El repositorio contiene la DLL de .NET y la aplicación GUI WinForms, controlada por los archivos de configuración de YAML.