¿Cómo funcionan los NPC’s?

Bienvenido a una de las áreas que más me gustan de la programación de videojuegos! 😀

Los NPC’s (Non-Playable Characters), son todos aquellos personajes de un juego que no son controlados por el jugador (al menos no directamente), pueden ser desde compañeros que te acompañan durante alguna de las misiones, o enemigos hostiles contra los que te enfrentas, incluyendo los jefes de algún nivel, o incluso vehículos que se muevan de manera autónoma.

Así que como seguramente te has de estar imaginando, la respuesta a ésta pregunta es básicamente un problema de Inteligencia Artificial, sin embargo (depende del juego) quizás pueda ser un poco más complejo de lo que se ve, pero déjame explicarme para que tengas una idea de cómo está la cosa:

Primero, tenemos que entender que cuando en la universidad te enseñan Inteligencia Artificial están buscando resolver un problema muy diferente al de la I.A. que se utiliza en un juego (salvo que sea una escuela de videojuegos, claro)….

En la academia normalmente intentan hacer una máquina lo más inteligente posible para poder resolver un problema dado, desde análisis de datos hasta robótica; sin embargo, en un videojuego tú intención realmente es divertir al jugador, no hacer al NPC más inteligente (si lo hicieras, se frustraría, tiraría el control y dejaría de jugarlo)… así pues, realmente en videojuegos estamos tratando de crear “Estupidez Artificial”… es decir, que el jugador perciba que el NPC es inteligente, pero sin que lo sea tanto para permitirle al jugador progresar a través del juego.

Esto nos trae con algo interesante: tienes que trabajar la percepción del jugador junto con la lógica de cómo actúa, muchas veces utilizando “hints” para que el jugador entienda qué es lo que el NPC quiere hacer, tal como animaciones, sonidos o voces de “nos están rodeando”, precediendo a un NPC que se mueve en dirección opuesta… (de lo contrario el jugador va a decir “uy qué IA tan chafa, los enemigos se van!”).

Pero bueno, hay básicamente 3 aspectos que estarás trabajando mientras desarrollas la I.A. de un personaje en un videojuego:

• Comportamiento
• Planeación
• Representación del Conocimiento

En su base toda la lógica de un NPC está basada en una Finite State Machine (FSM), si en la universidad llevaste clase de compiladores sabes de lo que hablamos… tú personaje puede estar Parado, Atento, Atacando, Herido, Huyendo, etc… todos son estados… Es tan básico que el lenguaje de script que se creó para el UnrealEengine3 (UnrealScript) ya manejaba implicitamente dentro del lenguaje el concepto de “estado” (y obviamente se encargaba de la transición entre estados)….

Sin embargo, en algunos casos la FSM por sí sola se vuelve muy determinista (si hace tal cosa SIEMPRE le sigue tal otra), y puede que no sea exactamente lo que quieres, aquí es cuando podemos empezar a meterle  un poco de “Lógica Difusa”, donde en lugar de decir que A=1 y B=0 y para pasar entre estados tiene que estar en 1 ó en 0, realmente puedes estar en un punto intermedio (ejm 0.4532) y el resultado de hacia qué estado se mueve depende de la función y los valores que hayas definido para este estado intermedio (ya se pone más interesante el personaje, vdd?).

Así también, en lugar de usar una FSM, es posible que quieras utilizar un “Árbol de Comportamiento” (OJO: no confundir con un “Arbol de Decisión”), que en esencia cumplirá la misma función que una FSM, pero tiene otras ventajas.

Pero bueno ¿de qué sirve eso si no vemos a nuestro NPC hacer algo?… aquí es cuando entran en acción temas como “Patrones de Comportamiento” (el típico comportamiento de los enemigos de un juego de NES, o alguno actual más casualón), “Steering Behaivors” (que tú NPC persiga a alguien, que lo evada, que huya, que merodee, etc)… también querrás simular que tus NPCs (especialmente si son pájaros, peces, perros, zombies, etc) se mueven en grupo, ahí está el tema de “Flocking”…

Hasta aquí es lo más esencial… sin embargo normalmente la I.A. se trabaja en capas (donde ésta fue la capa más baja).

Ya en las capas superiores empiezas a trabajar otros aspectos, como la planeación y la toma de decisiones, aquí es cuando entran en juego algunas técnicas como (ahora sí) “Arboles de Decisión” , “Rule Based Systems”, “Goal Oriented Action Planning”, “Bayesian Networks”… y si quieres hacer que tus NPC tengan formaciones y movimientos tácticos en grupo tienes “Blackboard Systems” que es una muy buena opción…

Así como también el famoso “A*” para pathfinding (encontrar la ruta de un punto A a un punto B habiendo obstáculos de por medio), e incluso algunas veces querrás manejar un pathfinding jerárquico…

Nota: La diferencia entre “Árboles de Decisión” y “Árboles de Comportamiento” es en esencia que en el árbol de decisión utilizas el árbol como una estructura de datos para analizar el estado del juego y tomar una decición, es decir:

Siempre recorres del nodo raíz del árbol hacia alguna de las hojas, donde cada rama representa una variable del estado del juego que deseas analizar para tomar una decisión, y te moverás entre cada rama dependiendo de si aplica o no aplica, y al final la hoja a la que llegues es la decisión que tomarás..

Por el contrario, un “Árbol de comportamiento” al principio empiezas en el nodo raíz, pero una vez que analizaste a los nodos hijos y tomaste la decisión de qué hacer, te mueves al nodo seleccionado, y ahí “te quedas”.. cada nodo del árbol representa un comportamiento en el que se encuentra el NPC en ese momento,.. y en la siguiente iteración empiezas del nodo en el que te quedaste, analizas sus hijos y te vuelves a mover al nodo que mejor califique, hasta que llegas a alguna hoja y se resetea el estado.

Digamos que un “Árbol de Decisión” lo utilizas para razonar el estado del juego en un momento dado y tomar una decisión, mientras que el “Árbol de comportamiento” es una guía del comportamiento que seguirá tu NPC en el mediano/largo plazo…

Y bueno, finalmente necesitas representar el conocimiento que utilizarás para que tus NPCs puedan razonar y tomar decisiones, ¿no?…

En el caso de Pathfinding seguramente podrás utilizar un mapa de tiles para representar el terreno (especialmente en juegos 2D isométricos), o bien un “Navigation Mesh” en un escenario 3D, que pueda utilizar el algoritmo de A* para recorrer y analizar las diferentes opciones… aquí no solo es la representación del terreno que se puede caminar, sino proveer a los NPCs de información relevante para decidir el mejor camino para los diferentes tipos de NPCs (por ejemplo, una persona normal quizás no podría cruzar una zona pantanosa, pero un tanque de guerra si, así que la heurística que utilizará el A* de la persona evaluará la viabilidad de trazar su camino por un lado, mientras que la heurística que resolverá el A* del tanque será diferente basado en la información del terreno y las capacidades del mismo NPC).

En general muchas cosas dependerán del juego que estés haciendo al momento de definir cómo representas ese conocimiento que utilizará la I.A., pero por ejemplo, en juegos de deportes, o de estrategia donde la posición de tus enemigos y aliados es importante, es muy útil el uso de “Mapas de Influencia” (un grid que representa que tanta influencia enemiga o aliada hay sobre ciertas zonas del mapa).

Y bueno, finalmente, así como en el aspecto visual del juego puedes tener modelos con diferentes Level-of-Detail (de modo que cuando un personaje esté lejos utilices un modelo con menos polígonos que cuando está cerca), en la I.A. también puedes manejar diferentes LOD (¿para qué haces cálculos innecesarios de cosas que el usuario no percibirá?).

¿cómo ves?… ¿te late?….

Si te late conocer más respecto a todo lo que mencioné, te recomiendo le eches un ojo a los siguientes libros:

• Programming Game AI by Example (Alex J. Champandard)
• Artificial Intelligcnce for Games (Ian Millington)
• AI for Game Developers (David M. Bourg, Glenn Seeman)

Aquí unas referencias concretas:

– Finite State Machines
Programming Game AI by Example, Capitulo 2
AI for Game Developers, Capitulo 9
Artificial Intelligence for Games, Capitulo 5.3

– Patterin Movement
AI for Game Developers, Capitulo 3

– Steering Behaviors
Programming Game AI by Example, Capitulo 3
Artificial Intelligence for Games, Cpaitulo 3.3, 3.4

– Flocking
AI for Game Developers, Capitulo 4

– Formaciones y Movimiento Táctico
Artificial Intelligence for Games, Capitulo 3.7

– Pathfinding (A*)
AI for Game Developers, Capitulo 7
Artificial Intelligence for Games, Capitulo 4.3

– Hierarchical Pathfinding
Artificial Intelligence for Games, Capitulo 4.6

– Representación del Mundo (Tiles, Waypoints, Navegation Meshes)
Programming Game AI by Example, Capitulo 8
Artificial Intelligence for Games, Capitulo 4.4

– Decision Trees
Artificial Intelligece for Games, Capitulo 5.2

– Behaivor Trees
Nota: No conozco algún libro que hable al respecto, pero estas ligas servirán:
http://aigamedev.com/open/article/behavior-trees-part1/
http://aigamedev.com/open/article/behavior-trees-part2/
http://aigamedev.com/open/article/behavior-trees-part3/
http://www.gdcvault.com/play/1012744/Behavior-Trees-Three-Ways-of
http://www.smu.edu/~/media/Site/guildhall/Documents/Theses/Delmer_Stephan_Thesis_Final.ashx?la=en

– Rule Based Systems
Artificial Intelligence for Games, Capitulo 5,7
AI for Game Developers, Capitulo 11

– Goal Oriented Action Planning
Programming Game AI by Example, Capitulo 9
Artificial Intelligence for Games, Capitulo 5,6

– Blackboard Systems
Artificial Intelligence for Games, Capitulo 5,8

– Influence Maps
Programming Game AI by Example, Capitulo 4
(no aparece bajo ese nombre, pero ejemplifican muy bien su uso)

– Bayesian Networks (decisiones bajo incertidumbre)
AI for Game Developers, Capitulo 13

– A.I. Level of Detail
Artificial Intelligence for Games, Capitulo 9.3

– Lógica Difusa
Programming Game AI by Example, Capitulo 10
AI for Gamer Developers, Capitulo 10
Artificial Intelligence for Games, Capitulo 5.4

 

Y finalmente otro excelente libro que no habla concretamente de ninguno de éstos temas, pero se enfoca en una parte fundamental de la IA para videojuegos, que es la de tratar de imitar el comportamiento humano, ya sea en lo individual, o en grupo, enseñándonos paso a paso y de una manera muy digerible a analizar la psicología humana y las dinámicas grupales, para después crear modelos matemáticos que ayuden a representar al comportamiento real:

• Behaivoral Mathematics for Game AI (Dave Mark)

En fin!…

Espero a alguien le sirva!!