Stepping on Artificial Intelligence:

State machine-based behaviour models

In the world of videogames, it's nice for the enemies to simulate thinking and that they act in consequence to our actions.
Basically, if they wouldn't do that, fighting an enemy or a palm would have no difference at all (coconuts, maybe).

In this article I mean to explain what makes an enemy decide acting in a way or another, and put an example.
Mi intention is that someone who knows nothing about this subject, after reading this article he/she can play a game and understand why that enemy is coming to me when I clearly have a bazooka in my hands.

CONTENT
  • State Machines
  • Building the house
    • Patrol
    • Search
    • Follow
  • Conclusions
  • Example

State Machines

I will refer to them as automata. There are many types of: finite states, infinite states, lambda/epsilon transitions, etc. etc.

The best way to explain how it works is with this diagram:


fsm1_eng.jpg
Automata have their own specifications (language, word, state, ...), but that's more complicated, so let's stick to basics.
Put in short: we start in a state, an when a condition is met, we jump to other state.
Both conditions and states can be abstractions of something more complex. In fact, they can even be treated as other automata appart.


fsm2_eng.jpg
This can help us to be organized and not to end with tons and tons of paper/<my text processor> pages. Y'know, divide and conquer.


Being aware of that, we can draw an automata like this...
fsm3_eng.jpg
... in which we externalize the start/end parts. Moreover, we can name it, for example, 'soldier'... and I guess we already know where this is going to.


And the theoric part ends here, which not means that there's nothing left to learn (heh). I've just explained what I think is necessary to understand it.
Anyway, if someone feels curious, wikipedia is your friend ->
http://en.wikipedia.org/wiki/Automata_theory
http://en.wikipedia.org/wiki/Finite_state_machine

Let's move to the example

Building the house

For our example we have a pair of models, to which we'll assign different behaviours.

As is obvious, behaviours can change, so we create a base class, from which the rest will inherit.
public class CBehaviourModel
{
	public CBehaviourModel() { }
	public virtual void Update(GameTime gameTime, ref Vector3 position, ref Vector3 direction, ref Vector3 rotation) { }
}


Update is the important method (well, just having the constructor and a method, there are not many options left).
As some behaviours will modify its own model's position, ..., we pass them by reference.

Once we have the base class, we can create the rest.
The plan is as follows: one of the models will be in 'patrol' mode, and the other will be searching for the first. If the searcher sees the patroller, the searcher will start following the patroller.

So, we'll do 3 classes: CPatroller, CStraightSearcher y CFollower.
As an extra, we also create a fourth one: CStandStiller, that does nothing. It's like the base class, but with the right name according to what it does, stand still.

As for explanations I will focus on the "important" methods, mostly the Update ones. Because the Draw, Load, etc. methods have nothing weird enough, so I won't be commenting them.

Patrol

It's a very simple class.
It has a N position array, which is the route to follow. Point N connects to the first one, so it's a closed route.

At the Update, the class saves the time passed between frames (cumul_time) to determine the distance to advance.
Then does a Lerp between 2 vectors: takes vector1 and vector2, and with an alpha factor [0..1] it returns a new vector. So if alpha = 0.5f, it returns the middle vector between v1 and v2. As it goes from 0 to 1, we use time to determine alpha.
Once reached the destiny (cumul_time = 1), the corners advance (and if it's the final then returns to the beginning).
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);
}


Note: I always say that to calculate something in videogames you have to count with both number and graphics.
That means, you have to match the elem. values with the mesh-to-paint values.
For this reason, on a corner change the model rotation is updated. If it didn't, the model would be just floating on the scene (see CFollowe for details).

Search

This class has been based on the usual infrared laser alarm. We have the model still, emitting a ray; if someone crosses that ray, the model changes its behaviour to CFollower.
To simulate the ray we'll use two planes. The second one is used to limit the "height" of the first one, due to the limitless of a plane, so anything behind would be also detected.

Although it's not seen, the scene looks like this
scene.jpg
color rays are the two planes.

In the Update there's a double-check to assure that the object is in front of the red plane, and that is intersecting with the yellow plane.
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);
}

Follow

And the last class. This class follows a position with a security distance (so one model doesn't trespass the other one).
Each Update has to update the position-to-follow, so this is done at the main game Update.
if (dino.Behaviour is CFollower)
{
	((CFollower)dino.Behaviour).TargetPosition = sword.Position;
}

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


and in the other Update, the new position is calculated
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;
}


This class does not update the model rotation, and due to this the model looks weird when it moves. This is the example I was talking in the CPatroller class.

Conclusions

With all of the above you can achieve what's seen in the example, which is very basic.
Adding a little more complexity, we could have that, for example, if an object escapes to a distance far than X, then the other changes to CSearcher again.
Also CStraightSearcher could be transformed into CSearcher, doing not just a straight line (plane), but an arc-rotation to have the searching field amplified. Also add a vision cone, etc.

Basic controls for the example are WASDZX + mouse for the camera, space for initiating the patrol behaviour, R for reset and ESC for exit.

Finally, I hope this article has helped someone to understand, or understand better, how some of the Artificial Intelligences work in videogames.
Please note that state machines were used thousands of million years ago, and that next-gen games use algorithms a lot more complex.
But then again, everything has come from somewhere.

And that's all, I hope this has been helpful.

Example

Simple AI example (XNA 2.0)

Cheers to everyone!

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

Last edited Oct 14, 2008 at 8:49 PM by glx, version 3

Comments

No comments yet.