One avenue of research with great viability for the development of video games is that of methods that allow the generation of procedural content. In recent years, the use of the Wave Function Collapse algorithm to create this type of content stands out. Although the algorithm has been used mainly for texture generation and level creation, its application to other fields of video games has been less explored and has a higher margin of application. The work developed proposes its use to procedurally generate the behavior of the Non-Player Characters of a video game. The solution presented is based on the creation of behavioral structures such as decision trees. As an example of how the algorithm works, a simple video game has been created.
Los elementos básicos del algoritmo WFC son las variables, el dominio y las restricciones. Las variables son todos los elementos del problema a descubrir. En un sudoku, por ejemplo, serían cada una de las casillas que forman el tablero. A su vez, cada variable cuenta con su propio dominio, representado por los valores que puede adquirir. En el caso del sudoku, el dominio serían los números del uno al nueve. Por último, las restricciones, son las reglas que se establecen para modificar el comportamiento del algoritmo y adaptar el contenido generado a las características previstas. En el ejemplo del sudoku implicaría que no se repitiera el mismo número en una fila, en una columna ni en un cuadrante de este.
El algoritmo propuesto se basa en los mismos principios que para la creación de teselas utilizando
WFC [
El algoritmo se ha diseñado para que obtenga como resultado una matriz de comportamientos
aleatorios (de forma similar a como se generan imágenes de teselas [
(a) (b) Figura 1: Matriz de comportamientos (a) y árbol de decisión del comportamiento del NPC (b).
Figura 2: NPCs en el videojuego desarrollado.
El algoritmo se ha aplicado con éxito para generar comportamientos aleatorios en NPCs de un videojuego (ver figura 2). El juego tiene dos tipos de enemigos con los que hay que luchar: los arqueros y los espadachines. Cada uno de ellos, tiene cinco posibles comportamientos, tres son comunes y dos específicos:
Los comportamientos generales son: - Patrulla. Movimiento de ida y vuelta entre dos puntos. - Retirada. Movimiento de vuelta a la base.
- Posicionamiento estratégico. Movimiento hacia un lugar estratégico.
Los comportamientos específicos de los arqueros: - Alejarse de un objetivo. Movimiento en sentido contrario al objetivo.
- Disparar a distancia. Disparo al jugador a partir de una determinada distancia. Los comportamientos específicos de los espadachines: - Acercarse a un objetivo. Movimiento hacia uno de los objetivos.
- Ataque cercano. Atacar al jugador a corta distancia.
Tanto el jugador como los enemigos, se incluyen en una arena donde se produce el combate. Lo interesante del sistema es que permite ver comportamientos diferentes para cada uno de los enemigos ya que sus acciones han sido generadas de forma procedimental, evitando los comportamientos repetitivos y permitiendo que estos sean diferentes para cada partida.
Como ejemplo de los resultados obtenidos se presentan las matrices de comportamientos y los árboles de decisión asociados, para un NPC de tipo espadachín. De esta forma, se puede ver cómo el espadachín 1 puede comportarse con el árbol de decisión de la figura 1 y el espadachín 2 con el árbol de decisión de la figura 3.
(a) (b) Figura 3: Matriz de comportamientos (a) y árbol de decisión (b) del espadachín 2.
Un ejemplo de la generación aleatoria del comportamiento para el NPC tipo arquero se puede ver en la figura 4.
La estructura de estos árboles está totalmente determinada por las restricciones que se han establecido para combinar los bloques de comportamiento, por el tamaño máximo de la matriz que se ha utilizado como base y por el número de hijos máximo que se asignan a cada bloque de comportamiento. Estas variables pueden adaptarse a las necesidades del juego en el que queramos generar el contenido, afectando sólo el tiempo de procesamiento.
Como se ha descrito en este trabajo, el uso del algoritmo WFC se está extendiendo por la industria
a una gran velocidad y pueden encontrarse muchos proyectos que lo utilizan para la generación de
niveles [