Inteligencia Artificial
por Javi Agenjo
javi.agenjo@gmail.com
Inteligencia
Cualquier juego que tenga agentes no controlados por el jugador necesitará de algún sistema de inteligencia artificial que los guíe.
El campo de la inteligencia artificial en videojuegos es quizá el menos ortodoxo ya que cada juego implementa la IA que más le conviene.
A diferencia que en gráficos donde existen unos algoritmos estándar que todo juego tiene, en IA lo mejor es que el juego dicte el tipo de algoritmos que se van a usar en función de las necesidades del juego en particular.
Sin embargo sí que existen ciertas herramientas que podemos utilizar para facilitar el proceso. A lo largo de esta presentación las iremos viendo.
Inteligencia Artificial
La idea de programar una IA es dotar de comportamiento a las entidades de nuestro juego, y que dicho comportamiento se adapte a la situación del juego.
Por lo general el campo de la IA en videojuegos suele tratar temas relacionados con:
Percepción
Percepción
Por percepción nos referimos a toda la información relevante de la que dispone una entidad sobre el mundo que habita.
Más allá de su propio estado (su posición, la vida que le queda, cuantas balas tiene, etc), una entidad puede necesitar información de su entorno como:
De cara a desarrollar nuestra IA necesitaremos que esa información esté disponible en todo momento.
Line of Sight (1/2)
Solemos necesitar saber si un objeto o personaje queda dentro del campo de visión de un agente.
Para determinar si algo es visible por un agente tenemos que hacer dos pasos:
Para el punto uno basta con mirar si el vector front del personaje y el vector toTarget (vector normalizado que va de la cabeza del agente a la posicion del target) forman un ángulo demasiado grande, en cuyo caso queda fuera del cono de visión.
Para ello podemos usar el dotProduct entre ambos vectores, sabiendo que si es 1 es que estan alineados, 0 si son perpendiculares y -1 si son opuestos. Asi que si el dot(Front,toTarget) > 0.5 entonces queda dentro del cono de 90grados que hay frente al personaje.
Line of Sight (2/2)
Pero saber si queda dentro del cono no es suficiente, necesitamos saber si hay alguna oclusión (si algún objeto tapa la vista).
La manera más simple es lanzar un rayo desde la posición del agente hasta su target, y comprobar si dicho rayo colisiona con objetos del escenario (testear colisión rayo mesh para cada objeto), si existe alguna colisión entonces asumimos que el agente no puede ver ese objeto.
Esta aproximación es muy fácil de implementar pero tiene defectos y es fácil que el player se aproveche de ello.
Comportamiento
Comportamiento
Por comportamiento entendemos decidir qué acción toca realizar en cada momento.
Lo habitual es que las entidades tengan una serie de posibles acciones que podrían realizar (ir a un lugar, atacar, huir, etc), y elija la más adecuada para cada momento, en función de la información de la que dispone (estado del mundo, estado interno de la entidad).
La manera como cada IA decida cuál es la acción más adecuada es algo abierto al programador.
Programando comportamientos
A la hora de programar comportamientos hay dos métodos habituales que se suelen usar:
Maquina de estados
Podemos modelar el comportamiento de una entidad como una máquina de estados. Cada estado define un comportamiento, y mientras estamos en dicho estado debemos ceñirnos a ese comportamiento.
Pero debemos controlar si se ha cumplido alguna condición de las que nos lleva a algún estado vecino, y si es así transicionar.
Por ejemplo, si estoy en el estado Luchar debo disparar, pero si me quedo sin munición debo pasar al estado Huir.
Implementando un máquina de estados
Una manera rápida de implementarlo es tener un enum con todos los estados posibles y en cada update evaluamos si toca cambiar a otro estado. Si no, entonces realizamos la acción pertinente para este estado.
El problema de utilizar máquinas de estados es que tenemos que programar todas las posibles transiciones entre estados, y si el número de estados es muy grande puede ser mucho trabajo.
enum eActions { SEARCH, ATTACK, FLEE };�
void Behaviour::update()
{
if( state == SEARCH )� {� if( ICanSeeTarget() )
state = ATTACK;� else
searchTarget();
}
else if( state == ATTACK )� {
if( IHaveAmmo() )� shoot();
else
state = FLEE;
}
//...
}
Arbol de comportamiento
En un Arbol de comportamiento (Behaviour Tree) en lugar de guardar el estado, lo recalculamos cada vez en función a la información que tenemos.
Esta aproximación es ligeramente más lenta en ejecución pero nos reduce el trabajo de controlar todas las posibles transiciones entre estados.
La idea es recorrer el árbol y si es un nodo rama, este evalúa una condición (p.e. Tengo un enemigo a tiro?), si se cumple bajamos a los hijos de dicha rama, sino pasamos al siguiente nodo.
Y los nodos hoja son los que definen qué acción tenemos que hacer.
La ventaja es que podemos dar más prioridad a ciertas acciones poniendolas mas a la izquierda en el arbol.
Implementando un Behaviour Tree
Para implementar un behaviour tree rápido lo que hacemos es ir anidando condiciones.
Si tras realizar una acción no tiene sentido seguir recorriendo el árbol, salimos de la función con un return.
No necesitamos evaluar el árbol en cada update, podemos hacerlo cada X frames para evitar sobrecargar la CPU (o evaluar cada frame el de un agente diferente, en lugar de todos a la vez).
if( energy < 0.1 ) //hurt
{
flee();
return;
}
if( ICanSeeTarget() ) //attack�{� if( IsTargetNear() )
shoot();
else
follow();
return;
}
//search�searchTarget();
Realización
Acciones
Una vez hemos determinado qué acción toca hacer, ahora es momento de ponerla en práctica.
Algunas son fáciles de realizar (p.e. dispara) otras requieren dividirlas en acciones más pequeñas (p.e. Buscar enemigo)
Una de las acciones más habituales son las relacionadas con navegación, es decir, encontrar el camino que lleva del punto A al punto B.
Navegación
En nuestros juegos es habitual que un agente tenga un objetivo hasta el que tiene que desplazarse.
La manera más simple tanto si estamos en 2D como si estamos en 3D es orientar nuestro agente en la dirección más corta hasta el objetivo y moverse en esa dirección.
El problema es que lo más probable es que se tope con algún obstáculo y se quede bloqueado en esa posición.
Así que necesitamos alguna manera de que nuestros agentes se muevan de una manera un poco más inteligente por el entorno.
Navegación autonoma
La primera opción es dotar a nuestro agente de sensores para detectar su entorno y tomar decisiones de manera acorde (por ejemplo lanzar tres rayos y ver a qué distancia colisionan con el entorno).
El problema es que usando información local del agente es difícil que encuentre una solución óptima al problema y puede acabar bloqueado.
Se usa en juegos de conducción donde no hay que buscar un camino, basta con evitar colisionar con las paredes.
Simplificaciones del entorno
Si queremos que nuestros agentes sean algo mas inteligentes como si un jugador los controlase, necesitamos ayudar a los agentes dandoles información extra sobre el entorno.
Podemos simplificar el mundo marcando por qué zonas se puede transitar y por cuales no.
En el caso de 2D se trabaja con rejillas donde cada celda representa un area de nuestro entorno y si es transitable.
Para 3D usamos grafos donde cada nodo es un punto de paso y cada arista un camino.
Búsqueda de caminos
Si queremos que nuestra entidad vaya del punto A al punto B necesitamos determinar cuál es el camino más corto. En el mundo real no disponemos de esa información así que tenemos que ir probando caminos o memorizar los que ya hemos visitado antes.
Sin embargo en el mundo de las IAs es habitual darle a las entidades más información de la que dispone el player para compensar que no sean tan inteligentes.
En el caso de la búsqueda de caminos podemos asumir que las IAs ya se conocen todo el mapa y por lo tanto pueden saber cual es el camino más corto entre dos puntos.
Podemos precalcular esos caminos mediante algún proceso offline y guardarlo junto con el mapa, o calcularlo en tiempo real conforme lo necesiten nuestros agentes.
Búsqueda de caminos
Cuando queremos encontrar el camino más corto entre dos puntos lo que hacemos es ir explorando cada posible camino partiendo del origen y mirando si nos acercamos más o menos al destino, y repetimos el proceso siempre expandiendo aquel camino que nos acerque más al destino.
Aquí hay un listado de algoritmos para buscar caminos:
Podéis verlos en funcionamiento en este enlace:
Ejemplo Pathfinders
//the map info should be an array W*H of bytes where 0 means block, 1 means walkable�uint8* map = new uint8[W*H];�//here we must fill the map with all the info�//...�//when we want to find the shortest path, this array contains the shortest path, every value is the Nth position in the map, 100 steps max�int output[100];��//we call the path function, it returns the number of steps to reach target, otherwise 0�int path_steps = AStarFindPathNoTieDiag(� start.x, start.y, //origin (tienen que ser enteros)� target.x, target.y, //target (tienen que ser enteros)� map, //pointer to map data� W, H, //map width and height� output, //pointer where the final path will be stored� 100); //max supported steps of the final path��//check if there was a path�if( path_steps != -1 )�{� for(int i = 0; i < path_steps; ++i)� std::cout << "X: " << (output[i]%W) << ", Y: " << floor(output[i]/W) << std::endl;�}��
La librería pathfinders es muy simple de utilizar para entornos 2D, basta pasar inicio y final y la info del mapa (zonas transitables, ancho y alto) y te retorna el camino más corto como una secuencia de (x,y) que define paso a paso cómo llegar:
Búsqueda de caminos en 3D
Cuando queremos buscar caminos en 3D podemos extrapolar la búsqueda de caminos 2D usando grids a 3D, pero el consumo de recursos sería demasiado elevado, así que optamos por simplificar el mapa 3D en elementos que definan puntos por donde se puede transitar.
Podemos definir waypoints (zonas de paso) en nuestro mapa manualmente, y construir caminos o incluso grafos.
Cuando necesitamos mover nuestros agentes, las forzamos a moverse entre estos puntos y así garantizamos que no se pierden, además de que es muy fácil encontrar el camino mas optimo entre dos waypoints usando búsquedas de caminos en grafos como vimos anteriormente.
class Waypoint {� public:� Vector3 position;� std::vector<Waypoint*> neightbours;�};��class Graph {� public:� std::vector<Waypoint*> waypoints;� std::vector<Waypoint*> findPath( Waypoint* a, Waypoint* b );�};
Explorando un grafo
Una vez tenemos una estructura básica para definir un grafo, necesitaremos una función que nos encuentre el camino más corto entre dos nodos.
Para grafos grandes esa función tendrá que usar algoritmos eficientes Dijkstra (aqui teneis una implementación explicada), pero si nuestros grafos no son muy grandes y no tenemos un número elevado de entidades, podemos hacer una implementación por fuerza bruta.
Esta libreria trae implementados algunos algoritmos y es fácil de integrar.
NavMeshes
El problema de los waypoints es que los agentes no llenan todo el espacio disponible sino que se mueven siguiendo líneas (como si fueran hormigas).
Si queremos que empleen todo el espacio podemos extender la idea de los grafos a NavMeshes.
Una NavMesh es una mesh donde cada triángulo representa una zona donde una entidad puede caminar. El agente sólo puede moverse dentro del área de un triángulo o pasar a otro si comparten una arista. A efectos prácticos son como grafos pero menos lineales. Podemos convertir la mesh en un grafo fácilmente recorriendo los triángulos y sus vecinos y aplicar algoritmos de pathfinding para movernos entre triángulos.
Estos grafos pueden ser creados mediante herramientas o generados proceduralmente.
Orientar una entidad
En algunos casos cuando nuestro mundo no tiene obstáculos nos basta con hacer que las entidades se dirijan hacia el punto directamente en línea recta, para ello basta con ir rotando la entidad en la dirección apropiada y avanzar.
Cuando queremos orientar una entidad hacia un punto necesitamos hacer varios cálculos geométricos.
Primero necesitamos calcular el ángulo de rotación y segundo el eje de rotación.
Veamos cómo podemos calcularlo.
Orientar en 2D
En 2D es muy simple, basta calcular el vector toTarget que va de A a B:
Vector2 toTarget = normalize( B - A );��Y calcular el ángulo que forma con el eje Y usando atan2:��float angle_in_rad = atan2( toTarget.x, toTarget.y );��Ahora ya sabemos el ángulo (yaw) que debería seguir nuestro agente para alcanzar el objetivo. Podemos interpolar entre nuestro yaw actual y el yaw objetivo, o podemos calcular la diferencia y aplicar dicha rotacion. Ojo que interpolar angulos no es trivial, ya que el camino mas corto entre 10 grados y 350 grados no deberia pasar por 180 grados.
Para evitar giros bruscos podemos suavizar los cambios del yaw a lo largo del tiempo.
Orientar una entidad en 3D (1/3)
En 3D el proceso es similar pero algo más complejo, calculamos to_target:�
Vector3 to_target = normalize(target_pos - entity_pos);
Para calcular un ángulo tomamos el vector front de la entidad y el vector to_target y hacemos el producto escalar. El producto escalar equivale a:
A*B = |A| · |B| · cos(a)
Si A y B están normalizados, podemos hacer acos( A.dot(B) ) y tenemos el ángulo. En nuestro caso sería acos( front.dot(to_target) ).
Cuidado, acos retorna un NaN si el valor está fuera del rango -1..+1, aseguraos siempre de que cumple esa regla si queréis ahorraros problemas, por ejemplo garantizando que los dos vectores no tengan módulo mayor que uno y clampeando el AdotB entre -1 y 1.
Orientar una entidad en 3D (2/3)
Una vez tenemos el ángulo necesitamos el eje de rotación, este eje tiene que ser perpendicular a los vectores front y to_target, y para ello usamos el producto vectorial.
Tened presente que si los dos vectores son iguales el vector perpendicular será cero, y al tratar de normalizarlo dará un divided by zero. Por lo tanto, si el ángulo es cercano a 0 es mejor salir de la función (además, si ya miramos hacia el objetivo no necesitamos rotar nada) o de lo contrario nos dará un eje erróneo.
Una vez tenemos el eje aplicamos la rotación en espacio local de la entidad, el problema es que el eje está en coordenadas de mundo y para aplicar rotaciones locales necesitamos la coordenada en espacio local.
Para pasar de coordenadas de mundo a local usamos la inversa de la matriz model.
inv = entity->getGlobalMatrix();
inv.inverse();
axis = inv.rotateVector( axis );
�Ahora ya solo falta rotar nuestra entidad teniendo en cuenta el ángulo y el eje. Si queremos podemos escalar el ángulo por el delta_time para que no rote de golpe.
Orientar una entidad en 3D (3/3)
Otra opción es rotar usando como eje vectores locales como el up (0,1,0) o el right (1,0,0) si queremos que el movimiento sea más como el de un avión (que no puede girar en cualquier eje).
En tal caso debemos determinar si el punto está por encima o por debajo del plano que forma el vector FRONT RIGHT del avión (el plano que pasa por el centro del avión y tiene su normal como el UP).
Similar a como lo hicimos antes, calculamos el vector desde el centro del plano hasta el punto y computamos el producto escalar, si el producto es mayor que cero el punto está por encima, si es menor es que está por debajo.
Podemos tambien aplicarlo al plano FRONT UP para ver si el punto queda a la derecha o a la izquierda y rotar de manera acorde.
Apuntar
Si tu juego tiene IAs que pueden disparar al jugador y las balas siguen trayectorias parabólicas o tardan un tiempo en recorrer el escenario, entonces te encontrarás con el problema de que aunque una IA apunte a donde esta el player, nunca le acertaran.
Para evitar eso necesitas que las IAs estimen el movimiento de la bala.
Aqui hay un tutorial que trata el tema, explicado de manera muy visual.
Coordinación
Comportamiento grupal
Es bastante común en los videojuegos que el player se enfrente contra grupos de enemigos.
En estos casos es interesante que los enemigos no actúen a nivel individual sino que se coordinen para aumentar el reto para el jugador.
Blackboard
Un método habitual es que cada entidad no solo contenga información local suya sino que pueda acceder a una información compartida por las demás entidades.
Para eso podemos tener una estructura de datos compartida entre entidades conocida como pizarra (blackboard) donde las entidades pueden ir actualizando información o leyendo para determinar qué acciones realizar.
class Blackboard {
public:
static Blackboard* instance;
Blackboard();�
Vector3 last_seen_player_pos;
int agents_seeing_player;
std::vector<Vector3> items_seen;
}
Videos relevantes
El canal de youtube AI in Videogames está dedicado únicamente a AI, tiene videos relevantes sobre muchos temas:
Videos de la GDC interesantes:
Conclusiones
Referencias