Introduction

You've probably heard people buzzing about neural nets and genetic algorithms and all sorts of other fancy terms and methods when it comes to game AI, but the simplest and most practical approach -- and the one that still provides the most natural and interesting possibilities despite its simplicity -- is the Finite State Machine, or FSM. The goal of this tutorial is help you understand what a FSM is, what its advantages and disadvantages are, how to design one, and how to implement one in Blitz.

The title gives it away, really -- it's a computing model that consists of a limited number of states, paths from each state to other states, and a function that can change the model's current state, following those paths.

So what does that mean?

To start off, a state tells an AI what behaviors it should be doing right now. There can be as few or as many states available as you like, but each one will tell your AIs to do something different. For instance, you might have a SEARCH state where an AI is looking for a player, as well as an ATTACK state where it's trying to destroy a visible opponent. You can have as many states as you like in an FSM, but even just a very few states can produce surprisingly convincing AI behavior.

A path is basically a set of rules where an AI switches states. For instance, if your enemy, currently in SEARCH state, detects the player, they would switch to ATTACK state and begin trying to take the player down. In general the more states you have, the more paths between them you'll have as well.

So technically, an AI is a single entity that can possess one state, as defined by the FSM, at any given moment -- a single enemy, not the entire process by which states are changed. And that leaves the FSM itself to be the processes and rules that dictate when AIs change state.

As a side note, a FSM is also known as a 'closed system' -- as the coder, you determine all the possible reactions to all possible game situations and create a state for each reaction. The advantage to a closed system is that you have fine control over how an AI responds to a state -- you code it explicitly so there's no guessing what will happen! The downside, however, is that if something in the game were to happen that you hadn't predicted, the AI will react oddly, selecting a state that might not have anything to do with what is actually happening in the game. That said, though, a well-designed FSM will suffice for almost any game.

It's really easy, actually -- you only need to decide on three things to fully design a FSM:

• STATES. What states are available to your AI?
• BEHAVIORS. How do your AIs behave when they're in each state?
• TRANSITIONS. What has to happen for an AI to change state?

Let's say I'm making a game about bugwars -- hundreds of tiny little mites (erm, pixels) on each side of a massive (erm, 640x480) warzone, all out to kill the bugs of the opposite teams. We'll give each one a random amount of health, speed, strength (to do damage with) and a random attack zone and sensing range -- if they can see an opponent, they can attack it. They're fast healers, but they have to stop moving to heal without food. They're also very social critters, helping each other when they're in trouble. When they're successful they can spawn new AIs, and those new AIs will stick by their parents. Lastly, eating the remains of their fallen enemies can replenish their health.

What states can these bugs be in?

SEARCH, FIGHT, PANIC, REST, SUPPORT, SNACK and SPAWN

What are the behaviors for those states?

• SEARCH: pick a random vector and move that direction for a random amount of time. when time is up, pick a new movement vector and repeat.
• FIGHT: stop where they are and cause damage to their target.
• PANIC: move away from their attacker until they hit the screen edge.
• REST: stop where they are and restore health.
• SUPPORT: pick a random radius and patrol around a panicked or resting ally.
• SNACK: have a munch on a nearby corpse and consume it to gain health.
• SPAWN: create a child AI.

How do they enter those states?

• SEARCH: default state; also when FIGHT is over, or when a creature is done RESTING or SUPPORTING.
• FIGHT: when they spot an enemy, and they're healthy.
• PANIC: when they're getting pounded by a strong enemy.
• REST: when they're done panicking.
• SUPPORT: when they spot a FIGHTING, PANICKED or RESTING ally.
• SNACK: when they spot an enemy corpse and they're under 100% health.
• SPAWN: when they have killed 3 enemies.

That's it! So long as you've defined the states, the behaviors and the transition criteria, your design work is done. Of course, that's the easy part; it's a bit tougher to implement it in code -- but it's not too hard, either.

You'll need to support your states, behaviors and transitions in code, and give actual AI instances the ability to know what state they're currently in. The easiest way to implement this into code involves the following approach:

CONSTANTS. These will define your states and make your code easier to read. Easiest part of the whole thing:

AI TYPE DEFINITION. Easiest way to create multiple AI instances; this also allows us to store other information, like the 'last seen' ally position I mentioned earlier. Almost as simple as the constant declarations -- just be sure the data fields will support all the functionality you want in your game.

BEHAVIOR FUNCTION. A function that tells your AIs what to do when they're in a specific state. I'm not going to paste the entire thing here (especially since you'll get the whole program to play with at the end), but the basic idea is this:

TRANSITION FUNCTION. A function to change an AI's state when it's appropriate to do so. Again, this function will look like one big select/case, and in fact when you optimize your code you may wish to bundle it in with the Behavior function -- especially if you have a lot of AIs to sort through. The shell of that function would look almost identical to FSM_Behavior(), so there's little point in repeating it here, but it's presented in full in the example code, separate so it's easy to see how the two serve separate purposes.

And here, for your amusement and edification, are the BUGZ: Click Here

It's a full implementation of the AI as discussed above, with what I hope are enough comments to make the specifics make sense. Neither the Transition nor the Behavior functions are particularly small, but they should be manageable enough to make sense of.

This newer version of the bugs makes a lot of things more visually interesting, as well as tweaks the FSM a bit. Bugs now get longer ranges after they spawn a child, and those ranges can continue to grow indefinitely if they keep fighting successfully and spawning. Also, consuming enemy corpses can strengthen a bug, replenishing their health. Ranges are now displayed as colored circles, and the color of the circle will show the bug's overall health -- darker means weaker. Lines will shoot out when a bug is attacking, and their li'l tongues will lap up enemy corpses til they're done noshing. Ewwwwwwwwww >:)

FSMs can produce quite a lot of complex behavior with even very few states -- which is a good thing, because as you add more states, it gets progressively harder to keep your AIs behaving the way you want them to. Interaction between states is difficult enough to track, but in a complex game you're likely to have either multiple FSMs or far more complicated Transition processing (for instance, you wouldn't use the same decisionmaking process for an infantry unit as you would a tank!). Keeping a handle on all the possibilities can get tough, so it's important that you take the time to design the state machine ahead of time.

That's it! Hope it's been useful; if you'd like to discuss this or point out all the nasty flaws in my thinking, leave a message on this thread or drop me a line via email (morduun@hotmail.com). Thanks for reading!