English Version

Primeros pasos en Inteligencia Artificial:

Modelos de comportamiento usando máquinas de estados

En el mundo de los videojuegos, está muy bien que los enemigos parezca que piensen y actúen en consecuencia a nuestros actos.
Básicamente si no lo hicieran, luchar contra un enemigo o contra una palmera no tendría diferencia alguna (los cocos, quizás).

En este artículo pretendo explicar qué hace decidir a un enemigo actuar de una manera o de otra, y poner un ejemplo práctico.
Mi intención es, que alguien que no sepa nada del tema, después de leer el artículo pueda jugar a un juego y entender porqué ese enemigo viene corriendo hacia mí cuando claramente tengo un bazooka en la mano.

CONTENIDO
  • Máquinas de Estados
  • Montando el tinglado
    • Patrullar
    • Buscar
    • Seguir
  • Conclusiones
  • Ejemplo

Máquinas de Estados

Me referiré a ellas como autómatas. Hay de muchos tipos, de estados finitos, infinitos, con transiciones lambda/epsilon etc. etc.

La mejor manera de explicar su funcionamiento es con el siguiente diagrama:

fsm1.jpg
Los autómatas cuentan con términos propios (lenguaje, palabra, estado, ...), pero como eso es más complicado, vamos a lo básico.
Simplificando: empezamos en un estado, y cuando se cumple una condición, saltamos a otro estado.
Tanto las condiciones como los estados pueden ser abstracciones de cosas más complejas. De hecho, hasta pueden ser tratados como otros autómatas aparte.


fsm2.jpg
Esto nos puede ayudar a ser organizados y no acabar con tiras y tiras y tiras de papel/hojas de <mi procesador de texto>. Ya sabéis, divide y vencerás.


Sabiendo eso, se puede hacer un esquema parecido al siguiente...
fsm3.jpg
... en el que dejamos externa la parte de inicio/fin. Si además lo llamamos, por ejemplo, 'soldado'... pues supongo que ya se empieza a ver por dónde van los tiros.


Y hasta aquí la parte teórica, que no quiere decir ni por asomo que no exista nada más que explicar (je). Simplemente he contado lo básico que creo que es necesario para entenderlo.
De todos modos, si alguien siente curiosidad, wikipedia es tu amiga ->
http://en.wikipedia.org/wiki/Automata_theory
http://en.wikipedia.org/wiki/Finite_state_machine

Pasemos al ejemplo práctico

Montando el tinglado

Para nuestro ejemplo contamos con un par de modelos, a los que asignaremos diferentes comportamientos.

Ya que el comportamiento puede variar, creamos una clase base, de la que heredarán el resto.
public class CBehaviourModel
{
	public CBehaviourModel() { }
	public virtual void Update(GameTime gameTime, ref Vector3 position, ref Vector3 direction, ref Vector3 rotation) { }
}


El método importante es el Update (bueno, estando sólo el constructor y un método tampoco queda mucho más).
Como alguno de los comportamientos modificará la posición, etc. de su modelo, lo pasamos por referencia en el Update.

Teniendo ya la clase base, podemos crear el resto.
El planning es que uno de los modelos estará en modo patrulla, y el otro estará buscándolo. Cuando lo vea, lo seguirá.

Hacemos 3 clases entonces: CPatroller, CStraightSearcher y CFollower.
Además, hacemos una cuarta CStandStiller, que no hace nada. Realmente es como la clase base, pero con el nombre adecuado a lo que hace, quedarse quieto.

Para las explicaciones me centraré en los métodos "importantes", básicamente los Update. Ya que en los métodos Draw, Load, etc. no hay nada excesivamente raro, no los comentaré.

Patrullar

Se trata de una clase muy simple.
Contiene un array de N posiciones, que le indican la ruta a seguir. El punto N conecta con el primero, de manera que hace un recorrido cerrado.

En el Update, va guardando el tiempo pasado entre frame y frame (cumul_time) para determinar la distancia que avanza.
Hace un Lerp entre 2 vectores: pilla vector1, pilla vector2, y con un factor alpha [0..1] devuelve un nuevo vector. Si alpha = 0.5f, devuelve el vector medio entre v1 y v2. Como va de 0 a 1, usamos el tiempo para determinar alpha.
Una vez llegado al destino (cumul_time = 1), se avanzan los corners (si es el final se vuelve al principio).
public override void Update(GameTime gameTime, ref Vector3 position, ref Vector3 direction, ref Vector3 rotation)
{
	// update time: takes X seconds to go from corner to corner
	cumul_time += (float)gameTime.ElapsedGameTime.TotalSeconds / corner_to_corner_time;

	if (cumul_time > 1f)    // reached max?
	{
		cumul_time = 0f;

		// Change corners
		++actual_corner;
		rotation.Y -= 90f;
		if (actual_corner >= corner_points.Length)
		{
			actual_corner = 0;
			rotation.Y = 0f;
		}
	}

	// patrolling
	int next_corner = actual_corner + 1;
	if (next_corner >= corner_points.Length)
		next_corner = 0;

	Vector3 from = corner_points[actual_corner];
	Vector3 to = corner_points[next_corner];
	position = Vector3.Lerp(from, to, cumul_time);
}


Apunte: siempre suelo decir que a la hora de calcular cualquier cosa en videojuegos hay que tener en cuenta tanto los números como los gráficos.
Es decir, que hay que cuadrar los valores de los elementos con los de las meshes que se van a pintar.
Por eso cuando se cambia de esquina se actualiza la rotación del modelo. Si no, iría pululando por el escenario sin más (ver el caso de CFollower).

Buscar

Esta clase está hecha a modo de alarma típica de láser infrarrojo. Tenemos el modelo quieto, que "emite" un rayo; si alguien cruza ese rayo se cambia de comportamiento a CFollower.
Para simular el rayo usaremos dos planos. El segundo se usa para limitar la "altura" del primero, ya que un plano es infinito y por tanto cualquier cosa que estuviera por detrás del modelo se detectaría también.

Aunque no se vea, en la escena tenemos
scene.jpg
las rayas de colores son los dos planos.

En el Update se hace la comprobación que el objeto esté por delante del plano rojo, y que intersecte con el plano amarillo.
public bool Intersects(BoundingSphere sphere)
{
	intersection_front = false;
	intersection_straight = false;

	// check0: front of plane
	if (Front.Intersects(sphere) != PlaneIntersectionType.Front)
	{
		return false;
	}

	intersection_front = true;

	// check1: straight plane
	if (Straight.Intersects(sphere) == PlaneIntersectionType.Intersecting)
	{
		intersection_straight = true;
	}

	return (intersection_front && intersection_straight);
}

Seguir

Finalmente, esta clase se encarga de seguir una posición con una distancia de seguridad (para no montar un modelo con otro).
Cada Update se ha de actualizar la posición a seguir, por lo que se hace desde el Update del juego principal.
if (dino.Behaviour is CFollower)
{
	((CFollower)dino.Behaviour).TargetPosition = sword.Position;
}

dino.Update(gameTime);
sword.Update(gameTime);


y en el update correspondiente, se calcula la nueva posición
public override void Update(GameTime gameTime, ref Vector3 position, ref Vector3 direction, ref Vector3 rotation)
{
	Vector3 dir = target_position - position;
	dir = dir - dir / 10; // security distance = 1/10;

	position += dir * (float)gameTime.ElapsedGameTime.TotalSeconds;
	dir.Normalize();
	direction = dir;
}


En este modelo no se actualiza la rotación del modelo, por lo que se ve "mal" cuando se mueve. Este es el ejemplo que comentaba en la clase CPatroller.

Conclusiones

Con todo lo anterior se puede conseguir lo que se ve en el ejemplo, que es muy básico.
Con algo más de complejidad, se podría hacer, por ejemplo, que si un elemento se escapa a más de una distancia X, el otro elemento cambia a CSearcher.
También CStraightSearcher se podría convertir en CSearcher, haciendo no sólo una línea recta, si no que vaya rotando en un arco para ampliar la búsqueda, añadir un cono de visión, etc.

Los controles básicos son WASDZX + mouse para la cámara, espacio para iniciar el comportamiento de patrulla, R para resetear y ESC para salir.

Finalmente, espero que este artículo haya ayudado a alguien a entender, o entender mejor, como funcionan algunas de las Inteligencias Artificiales en los videojuegos.
Hay que tener en cuenta que las máquinas de estados se usaban hace mil millones de años, y que los juegos next-gen usan algoritmos muchos más complejos.
Pero bueno, que de algún lado ha venido todo.

Lo dicho, que espero que haya sido útil.

Ejemplo

Ejemplo simple de IA (XNA 2.0)

¡Saludos a todos!

Marc "Glx" García
http://www.codeplex.com/XNACommunity

Last edited Oct 14, 2008 at 12:48 PM by glx, version 4

Comments

No comments yet.