Articulo utilizando maquinas de estado finitas para programar videojuego de peleas - norman-ipn/Evolutivo GitHub Wiki

Desarrollo de un Videojuego en Tercera Persona utilizando Máquinas de Estado Finitas (FSM) y Pathfinding Jerárquico (HPA)

Abstract— El presente trabajo está enfocado a la implementación de algoritmos de inteligencia artificial en el desarrollo de juego del tipo Tercera Persona, los algoritmos de Màquina de Estado Finita (FSM) y Pathfinding Jerárquico A estrella (HPA) fueron utilizados. El soporte de software utiliado fue el Qt creator, el cual es un IDE creado para el desarrollo de aplicaciones con las librerías Qt mediante programación en C++. El juego desarrollado y expuesto en este trabajo está conformado de dos personajes enfrentados en un combate cada uno con un tipo de estrategia propia, el algoritmo FSM fue utilizado para modelar dichas estrategias. Para el movimiento y búsqueda realizado por cada personaje el algoritmo HPA fue utilizado. Los resultados de las simulaciones presentadas fueron producto de las pruebas del juego para diferentes situaciones puestas para los dos personajes generando condiciones iniciales aleatorias.

I. INTRODUCCIÓN Los videojuegos has pasado por una serie de evoluciones intensas en lo que respecta a la tecnología utilizada para su desarrollo, haciendo que se pase de una idea basada en el ocio hacia el público infantil como inicialmente se les tenía concebidos hacia un medio para el ejercicio de la mente del jugador e incluso del cuerpo para algunos casos, estas tecnologías no sólo se han caracterizado por el software utilizado (sean por ejemplo, motores de juegos, programas de diseño gráfico y animación, entre otras herramientas), sino también por el grado de “inteligencia” que se les ha dotado a cada elemento del juego sobre todo en las aplicaciones más recientes, lo cual proviene de la implementación de ciertos algoritmos de inteligencia artificial para llevar a cabo las acciones deseadas en el entorno del juego. El presente trabajo precisamente utiliza dos de esos algoritmos, el FSM utilizado para modelamiento de las acciones de un personaje y el HPA para el movimiento de cada personaje del juego así como el método de búsqueda.

II. DESCRIPCIÓN DEL JUEGO El juego desarrollado para el presente trabajo se caracteriza por ser un juego del tipo “tercera persona” (third-person game), en el cual el personaje es visto desde una perspectiva en tercera persona. En este juego se ha introducido a dos personajes, los cuales son enfrentados en un combate. Durante la ejecución del juego, cada personaje realizará determinadas acciones dependiendo de la estrategia que se le es programado (modelada mediante una máquina de estado), dichas acciones dependerán también de ciertas variables a considerar en el juego (lo cual se explicará en la siguiente sección) además de considerar también las características del entorno. Los algoritmos utilizados para el desarrollo del juego como bien se ha mencionado son los siguientes:

A. Máquinas de estado finitas (FSM):

Este es un algoritmo que utiliza estructuras simples para la representación del comportamiento de un sistema ante determinadas condiciones (o como se le llama también, ante determinados eventos) mediante un conjunto de estados (véase el ejemplo de la Fig.), se definen acciones que el personaje ha de realizar cuando se encuentra en cada uno de los estados. Además también se definen transiciones entre estados representados por condiciones las cuales se activan dependiendo de los valores de las variables utilizadas para pasar de un estado a otro.

Fig.1 Ejemplo de una máquina de estado finita (FSM)

B. Pathfinding Jerárquico (HPA)

Es un algoritmo diseñado especialmente para planificación de trayectorias, se toma como datos de entrada al algoritmo los puntos de partida y de llegada para un determinado móvil (sea por ejemplo, un auto o una persona), y se representa el terreno sobre el cual ha de desplazarse a través de grafos, es decir, como un conjunto de nodos representativos del terreno en cuestión. El algoritmo HPA particularmente se utiliza en los casos para los cuales se tiene un conjunto de nodos significativamente grande, entonces se procede a agrupar mediante clusters cada sub-conjunto de nodos, de modo que se establece otro nivel de búsqueda, con una cantidad de nodos menor sobre el cual se puede efectuar un planeamiento de ruta más sencillo (en el caso del HPA se utiliza el A* para la determinación de dicha ruta entre zonas), una vez que se establece la ruta a ese nivel, esta es refinada, es decir, se regresa al nivel inferior (o al inmediato inferior en caso se haya “clusterizado” más de una vez) para planificar una ruta dentro de cada cluster en el nivel dado, de ese modo se tiene una ruta más ordenada en un terreno amplio como se muestra en la Fig. 2.

Fig. 2 Ejemplo de un pathfinding jerárquico

El entorno o terreno sobre el cual se desenvolverán los personajes en base a su programación es representado mediante formas geométricas simples para evaluar de forma sencilla el desempeño del algoritmo implementado en cada personaje, en el juego desarrollado para el presente trabajo se ha recurrido a utilizar cubos formandos aleatoriamente a través de una función programada en el Qt Creator. Por otra parte, el terreno también es considerado como un terreno invariante, es decir, no sufrirá cambios durante la ejecución del juego (no existen obstáculos móviles).

Para fines de simplicidad y para enfocarse más en los algoritmos a implementar en el juego que en la apariencia del mismo, se ha optado por desarrollar el juego en un ambiente en dos dimensión es, además que los personajes son representados cada uno mediante una figura simple. Para algunas otras aplicaciones es posible implementar el juego en cuestión en un ambiente en tres dimensiones con el fin de visualizar distintas perspectivas.

La programación del juego, es decir, de los personajes introducidos, las acciones que realizan y las condiciones iniciales fue llevado a cabo con el IDE Qt Creator, para el cual se explican sus características más destacadas a continuación.

III. DESCRIPCIÓN DEL QT CREATOR IDE Qt es una librería gráfica multiplataforma creada por Nokia. Esta librería posee como característica resaltante el uso de signals y slots; mecanismos que se utilizan para comunicar información entre funciones de distintas clases sin necesidad de acceder a la clase en sí. Tiene gran compatibilidad con clases estándar; provee funciones para hacer conversión entre tipos y en particular existe un tipo variante que permite convertir datos sin tantas operaciones. Brinda la posibilidad de realizar programación multitarea, por lo que se pueden independizar el procesamiento de algún código pesado de la interfaz gráfica. Utiliza un entorno de programación llamado Qt Creator. Este incluye documentación completa acerca del uso del programa.

Fig. 3 Entorno de programación Qt Creator

IV. MÁQUINAS DE ESTADO FINITAS (FSM)

A. Descripción de las variables utilizadas Antes de definir el modelo de máquina de estado correspondiente a casa personaje se establece que variables se va a manejar en el desarrollo del juego, las de interés para la máquina de estados. A continuación se enlistan las más importantes:

Puntos vitales (o energía del personaje).
Defensa: Cantidad de puntos de defensa o resistencia que posee el personaje.
Daño: Representa el daño recibido.
Distancia: Representa la distancia entre el personaje y su adversario (posición relativa).

Cada una de estas variables influye en la activación (o no activación) de cada transición entre estados, dependiendo de los valores “umbrales” (valores de comparación) asignados en cada transición, estos valores de hecho marcan las prioridades que posee cada estrategia en relación a las variables mencionadas. Es decir, un personaje puede priorizar el ataque constante contra el objetivo a costa de perder puntos vitales y sólo replegarse cuando éstos casi se agoten.

B. Modelamiento de las estrategias Para modelar el comportamiento de cada personaje ante una determinada situación en el juego se ha recurrido a utilizar un modelo compuesto por una serie de estados en las cuales puede encontrarse un determinado personaje, cada estado esta compuesto por un conjunto de acciones que realiza el personaje en cuestión dependiendo de las circunstancias en las cuales se encuentre y dependiendo además de la activación (cumplimiento) de ciertas condiciones representadas como transiciones de un estado a otro, estas transiciones están conformadas por una o más condiciones expresadas en forma matemática-lógica que hacen uso de los valores actuales de las variables a manejar en el juego.

Características de cada estrategia Lo que distingue a cada estrategia (cada una para un personaje) son los siguientes ítems:

La cantidad de estados está en función a la cantidad de acciones que pueda realizar el personaje dependiendo del tipo (vale decir, el modus operandi del personaje), se mostrará posteriormente en la sección A.1 el modelo planteado para los dos personajes introducidos en el juego.
Las transiciones entre estados de la misma índole comparando una estrategia con otra varía en cuento al hecho de agregar una condición adicional o variar los valores de las variables a comparar para la activación o no activación de las condiciones establecidas en dichas transiciones.
1. Modelos de estados de cada personaje: Se muestra a continuación los dos modelos utilizados como máquina de estado:
- Modelo 1: Personaje con ataques de largo alcance. En este modelo (mostrado en la Fig. 3) se han considerado cuatro estados: huir, buscar, disparar y defensa. Inicialmente el personaje estará en el estado buscar dado que al inicio no sabe en donde se encuentra el otro personaje inicialmente, por lo que aún no realiza las otras acciones (se le define como un estado por defecto), cuando el personaje logra ver a su objetivo (en este caso, el otro personaje) dado que es un personaje con ataques de largo alcance se dispondrá a atacar desde una determinada distancia, de perderlo de vista, sale del estado disparar para regresar al estado buscar, en el caso de que el personaje reciba una cierta cantidad de daño (en este caso un valor de 20), el personaje tenderá a defenderse para evitar que su energía vital disminuya, pero aún así la variable defensa para dicho personaje disminuye (se ha considerado que la defensa también es una variable sujeta a cambios producto del ataque del adversario), llegado un cierto valor de disminución de la defensa el personaje pasa al estado huir hasta que su defensa se haya recuperado y vea al objetivo (caso para el cual vuelve al estado defensa) o hasta que el objetivo se haya alejado y haya recuperado buena parte de su defensa (caso en el cual se pasa al estado buscar).

Fig. 4 Máquina de estado representativa de la estrategia de ataques de largo alcance

Modelo 2: Personaje con ataques de corto alcance. En este modelo (mostrado en la Fig. 4) se ha considerado seis estados: huir, buscar, defensa, perseguir, retroceder y atacar. Al igual que en modelo anterior, el estado por defecto será el de búsqueda por las mismas razones, el personaje inicialmente no conoce la ubicación de su adversario. Apenas logra ver a su objetivo pasa al estado de perseguir a menos que lo pierda de vista (regresa al estado buscar) debido a que es un personaje con ataques de corto alcance por lo tanto las acciones requeridas para el desenvolvimiento del personaje en un estado u otro cambian. Si el objetivo es alcanzado, se pasa al estado atacar hasta que se produzca una cierta cantidad de daño al oponente y se pase a un estado de retroceder temporalmente para luego retomar el ataque, o hasta que su oponente le cause un daño considerable (mayor al valor de comparación análogo en la otra máquina de estado), de presentar una baja defensa, el personaje procede a huir (estado huir), hasta que se haya recuperado parcialmente la defensa o el personaje adversario se encuentre relativamente alejado.

Fig. 5 Máquina de estado correspondiente a la estrategia de ataques de corto alcance

IV. PATHFINDING JERÁRQUICO (HPA) El terreno como bien se ha mencionado queda representado como un conjunto de nodos en un grafo, se determina entonces que el terreno quedará dividido en cuadrículas o casillas las cuales representarán dichos nodos. En consecuencia, cada nodo dispondrá entonces de cuatro nodos vecinos (ubicados de forma adyacente en las direcciones norte, sur, este y oeste). Se tomó en cuenta también que el terreno no es cambiante, es decir, no sufrirá alteraciones de ningún tipo durante el desenvolvimiento del juego, es decir, no se va a agregar, remover o movilizar obstáculos mientras el juego entre en ejecución, por lo tanto el planeamiento de ruta que realizará cada personaje se actualiza sólo en respuesta a un cambio de la posición relativa del personaje adversario (el nodo de llegada para cada uno cambia, entonces el algoritmo se replantea). Este algoritmo define agrupaciones de los nodos que componen el terreno basados en clusters, que son conjuntos de elementos (en este caso, los nodos) que los reúnen en base a un criterio simple de proximidad entre ellos, como bien se mencionó en la sección II.B se establecen uno o más niveles de clusters sobre los cuales se realiza el planeamiento de trayectoria, empezando por el nivel superior (con el número de clusters más pequeño o con el mapa más reducido) y luego se procede a refinar la ruta efectuando varios planeamientos entre clusters de niveles inferiores. Para visualizar adecuadamente el desempeño del algoritmo implementado, se construye un terreno de forma cuadrada de dimensiones medianas (del tamaño suficiente como para que se pueda apreciar la ejecución del algoritmo). Para que los estados planteados perseguir en el caso del personaje con ataques de corto alcance y el estado de huir pueda llevarse a cabo sin inconvenientes es que se incorpora esta técnica de inteligencia artificial para búsqueda. Tal y como se muestra en la Fig. 5 en el cual se ha hecho una prueba del algoritmo en entorno MATLAB, el algoritmo puede adaptarse a cualquier terreno amplio, por consiguiente también se ajustará a un terreno como el descrito para el juego desarrollado.

V. RESULTADOS Se realizaron pruebas de la ejecución del juego determinando por programa las condiciones iniciales para cada jugador, esto para evaluar cómo responden las estrategias de cada jugador, en otras palabras cómo se va desenvolviendo durante el juego cada máquina de estados. Luego, cuando los personajes se encuentren en los estados que implican acciones de movimiento o búsqueda, interviene el algoritmo de planeamiento de ruta HPA, como se muestra en la Fig. 6 se tiene el terreno programado con Qt Creator, representado mediante casillas cada una de las cuales es un nodo dentro del grafo, y los obstáculos son generados aleatoriamente por programa y antes de que los personajes sean insertados en el juego (también en ubicaciones aleatorias dentro del terreno).

Fig. 6 Terreno del juego y personajes programados en el Qt Creator

También se muestra en la Fig. 6 a los personajes dispuestos en ubicaciones iniciales aleatorias, de modo que se monitorea la respuesta de las estrategias de cada personaje a cada momento (en base a sus estados y transiciones entre ellos), se muestra por programa a todo momento los puntos vitales (o energía) de cada personaje además de los puntos de defensa, de modo que se tiene un panorama mejor descrito del desarrollo del juego.

Fig. 7 Situación de ataque entre personajes

Como se aprecia en la Fig. 7 cada personaje queda representado mediante figuras geométricas sencillas para visualizar su movimiento, dirección del movimiento e incluso el estado en el cual se encuentra sobre todo si está atacando o defendiéndose como también se podrá apreciar en dicha figura. Se muestra además el conteo de puntos tanto de energía como de defensa, los cuales van disminuyendo a medida que un personaje ataca a otro, en cuanto a la defensa, esta se incrementa en una unidad (de puntos de defensa) tras cada unidad de tiempo, como una recuperación, sin embargo, los ataques del personaje adversario pueden hacer de que aún con una recuperación de la defensa, esta siga cayendo, lo cual implica entonces que el mecanismo de recuperación de la defensa para cada personaje deba estar en función de variables consideradas para el juego mismo pero no contempladas para dicho fin.

IV.CONCLUSIONES Las máquinas de estado son muy utilizadas en el campo de los videojuegos debido a que muestran una estructura sencilla para la cual no se requiere una vasta experiencia en inteligencia artificial para su interpretación, este algoritmo nos permite modelar el comportamiento de los personajes del juego, e incluso para otras aplicaciones, del terreno (para cuando se desea este sea cambiante de acuerdo a ciertos lineamientos), de obstáculos móviles o en el caso de juegos de aventura, marionetas o “enemigos pequeños”, evaluando para cada uno de ellos acciones que componen una estrategia propia de cada personaje o componente del juego ante cualquier circunstancia. Para el movimiento, búsqueda y trazado de rutas, el algoritmo HPA ofrece toda una serie de ventajas, destacando sobre todo su aplicación en terrenos amplios permitiendo una ruta más accesible y ordenada, esta es la razón por la cual también se aplica no sólo en videojuegos sino también en aplicaciones tales como la robótica móvil.

REFERENCIAS [1] I. Millington and J. Funge, Artificial Intelligence for Games, 2nd ed., Ed. Elsevier, 2009. [2] B. Schwab., AI Game Engine Programming, 1st Ed., Ed. HINGHAM,