Inteligencia artificial para videojuegos/Tácticas y estrategias

En el momento en el que un videojuego requiere de varios NPCs y/o enemigos que tomen decisiones de forma autónoma e individual, o con visión de conjunto sobre la situación, surge la idea de estrategia y táctica.

Los videojuegos que destacan por tener mayor requisitos en cuanto a estrategia y táctica son los RTS, por lo general todos necesitan planificación de rutas, máquinas de estado, gestión de recursos y toma de decisiones. Aunque carecía de IA enemigo , uno de los primeros juegos en implementar esto fue Utopia (1981), que para algunos está considerado como el precursor de los RTS. El género ha ido evolucionando hasta dejarnos juegos tan relevantes en el campo de la IA como los de las sagas Civilization, Starcraft o XCOM entre muchas otras.

La estrategia, siguiendo términos militares, es el planteamiento general de la batalla. Y, por otra parte, la táctica es la ejecución concreta de dicho planteamiento. Además, se complementan, entre otras cosas, con el mantenimiento, la gestión de recursos, el transporte, el movimiento y la comunicación del ejército.

Normalmente en los videojuegos la estrategia suele estar prediseñada. Sin embargo, la táctica es tratada simplemente por la IA en ciertos casos.

Puntos de ruta tácticos

Los puntos de ruta tácticos permiten que los agentes de la IA se formulen preguntas “inteligentes” sobre su entorno (cómo o dónde ocultarse o atacar, por ejemplo). Los puntos habituales los pone el diseñador como alternativa o complemento a los espacios abiertos.

Pueden tener información de movimiento, como zonas de salto o en las que hay que agacharse, o información táctica, con la que los personajes conocerían puntos de reunión o retirada, zonas con cobertura u ocultación e incluso peligros que deben evitar. Y, aunque a menudo puede bastar con información táctica primitiva, si se usa una información táctica compuesta se pueden definir cualidades de los puntos para que los agentes los localicen mejor según sus necesidades. Por ejemplo, si se desea encontrar un buen punto de emboscada sería interesante encontrar un lugar oscuro, con cobertura y que a su vez esté cerca de otro sin cobertura.

En vez de tener un grafo diferente para los puntos de ruta tácticos, se puede enriquecer el grafo habitual con información táctica. Es más, un buen análisis topológico del grafo va a aportar información táctica que los agentes van a poder usar para, por ejemplo, buscar rutas de huida o conseguir un buen posicionamiento. De esta forma, la utilidad de un punto de ruta táctico es muy sensible al contexto. Una acción como ir a buscar munición podría mejorar el estado del agente, pero si para conseguirla debe cruzar una zona peligrosa quizá deba sopesarlo. Para que el agente tenga más datos para poder tomar una decisión se puede guardar información extra como la utilidad del escondite para cada dirección cardinal o hacer cálculos extra como valorarlo proyectando rayos y conociendo su entorno.

Un NPC puede darles uso a estos puntos de distintas formas. Puede tomar primero la decisión y luego elegir el punto de ruta táctico donde realizar la acción escogida, o puede considerar la táctica desde la toma de decisión. Podrá usar la Teoría de la Decisión, que contempla lo probable y útil, y valorar rápidamente la utilidad táctica de un conjunto de puntos cercanos, mediante distancia euclídea o planificando una ruta reducida. Y, si se combina con planificación de rutas, podría parecer un análisis táctico.

Generación del grafo

Para generar el grafo con la información de los puntos de ruta tácticos se puede hacer de varias formas.

La primera y más sencilla, en la que el diseñador anota los grafos a mano, preferiblemente con herramientas visuales. Otra forma es procesando el nivel al principio o generándolo sobre la marcha. Esto es especialmente útil en casos donde el mapa es dinámico y el grafo tiene la capacidad de cambiar en ejecución, por ejemplo en un juego donde elementos del terreno pueden ser destruidos o donde la zona de ocultación varía. También se pueden registrar partidas entre jugadores para extraer de ellas un conjunto variado de puntos.

Normalmente los puntos se valoran proyectando rayos, que indican si es una buena cobertura o punto de alcance, o cualquier otra cosa propia de cada sistema de juego. Estos rayos pueden ir desde los puntos vecinos al cuerpo del personaje, viendo posibles ángulos de ataque, o desde los ojos del personaje hasta los puntos vecinos distantes.

Por otro lado, para conocer los puntos de ocultación o sombra hay que leer la iluminación del nivel, ya sea de forma global, dinámica o de cualquier otro tipo, y medir justo en la zona más iluminada.

Finalmente, se generan muchos puntos, se reducen con un algoritmo de condensación y se supervisan y corrigen a mano.

Análisis táctico

Con los juegos de estrategia en tiempo real, o RTS, surgen técnicas de análisis del entorno para poder generar tácticas que lleven a los agentes a conseguir su objetivo. Son los llamados mapas de influencia, que permiten que la IA reconozca zonas de influencia para cada uno de los ejércitos que se hallan en el escenario, muy similar a lo visto en puntos de ruta tácticos.

Para ello, el mapa o entorno deberá representarse en regiones o celdas, normalmente de un mismo tamaño, usando algún esquema de división. Se pueden usar las mismas técnicas usadas en planificación habitual de rutas, sobre todo las que heredan de los RTS: grafo de baldosas o teselación de Dirichlet, que se centran más en un entorno dividido. Pero también pueden usarse puntos de visibilidad o mallas de navegación.

Mapas de influencia

Una vez dividido el entorno, los factores básicos de cada región del mapa son lo próximo que estén de ellas otras unidades y/o base de un ejército, además de su poder militar relativo al otro.

Aunque resulta simple y eficaz, este método tiene una complejidad

O(unidades * regiones) que necesitará ser optimizada. Para conseguirlo se pueden limitar las zonas en las que ya no hay influencia con un radio de efecto limitado, de forma que se ahorra calcular dicha influencia. Con filtros de convolución la utilidad táctica de una región se calculará más rápidamente en función de sus vecinas. Y si se quiere rapidez, aunque un poco tosco o imperfecto, puede usarse el método de inundación del mapa, que copia el mismo valor en todo el radio de influencia de la unidad.

Análisis de terreno

Como parte de este análisis táctico se puede estudiar el terreno de juego, de forma que se busque el mejor camino para desplazarse, la mejor zona desde donde disparar, etc. Habitualmente se distinguen distintos tipos de terreno y se combinan con la altura de la región, lo que afectará a la accesibilidad y otras acciones de distinta forma. También se suele medir el alcance de una región, que determina el número de regiones que son visibles desde ese punto.

Además, si se registran distintas partidas se pueden hacer mapas de bajas que darán lugar a cierto aprendizaje, ya que la utilidad táctica de cierta región subirá si desde allí se matan enemigos, y bajará si es un punto en el que unidades enemigas matan a otra.

Análisis táctico multicapa

Útil cuando se proponen multitud de factores tácticos en el diseño, a veces a distinto nivel incluso. Para ello se calculan los mapas de influencia referentes a los factores que influyen en la utilidad de un agente (seguridad, alcance, distancia a otras unidades…) y luego se combinan para hallar la utilidad táctica final.

A veces, incluso, se crea un servidor de análisis táctico para ayudar a los desarrolladores con la muestra de mapas para depurar, una API, etc.

Planificación táctica de rutas

Es una planificación de rutas normal, pero a la que se le añade información táctica en su coste. Esta ha de estar dada por el sumatorio de factores, pesando los tácticos en relación con la distancia.

Sin embargo, los puntos de ruta tácticos y el análisis sólo aportan información táctica del punto o de la región.  Debido a esto, hay que crear conexiones entre regiones, a veces incluso superponiendo el grafo táctico al normal. Y es el coste de dichas conexiones lo que suele dar lugar a la media de la utilidad táctica de ambos puntos o regiones unidos. Teniendo en cuenta que se ha de forzar que el coste sea siempre positivo y se ha de procurar usar heurísticas válidas, evitando así que se formen resultados incorrectos que den lugar a acciones no deseadas en los agentes de la IA. Además, este coste positivo y el uso de heurísticas válidas ha de producirse mientras los factores tácticos fluctúan constantemente durante la ejecución del juego.

Acción coordinada

Es momento de unificarlo todo, orientándolo a un grupo de NPCs o enemigos que actúan en conjunto y de forma coordinada. La llamada táctica del movimiento global, debida por NPCs autónomos que coordinan sus acciones, por NPCs que obedecen órdenes explícitas del jugador o que interpretan sus intenciones.

Puede plantearse un sistema multicapa, de forma que no sólo se coloca una IA detrás de cada NPC, sino también de cada grupo o incluso de todo el ejército. Cada capa toma sus propias decisiones, planifica rutas a su nivel, realiza movimientos y demás acciones. Y para simplificar, el NPC con más limitaciones se toma como “cuello de botella” del grupo. Pero este sistema multicapa va a necesitar de mecanismos de comunicación y de gestión de ejecución para su correcto funcionamiento.

Ocasionalmente se llega a conseguir que haya cooperación emergente entre los NPCs simplemente tomando decisiones que tienen en cuenta a sus compañeros de grupo, con lo que no haría falta una IA táctica por encima de todos los NPCs, solo de algunos de ellos.

Los comportamientos de direccionamiento siempre van a escalar mejor que las máquinas de estados. Sin embargo, cuando todo es impredecible o surgen muchos interbloqueos se acaba por meter algo de IA por encima que logre evitarlo.

Finalmente, una manera muy creíble de realizar acciones en grupo es guionizándolas, regirlas por el propio diseño previo. Normalmente se programan estos guiones con dos acciones para coordinar cambios de estado, animaciones, movimientos y acciones de alto nivel.  Dichas acciones son el envío de señales a otros NPCs y la espera de señales de otros NPCs. Y estos guiones pueden tener partes genéricas para todos y otras específicas para determinados grupos o NPCs.

Participantes

Daniel Pérez Luque

Gabriel Aramis Sardaneta del Collado
Daniel Álvarez Castro