TL;DR

Finite State Machines are the most boring way to do game AI.

What Is A Finite State Machine?

Finite State Machines (FSM) are a very simple concept to understand. You simply work out all the states that your system can be in, and then for every single state work out every single action you can take from that state (and in what circumstance you would take it). This is, I feel, best explained by XKCD. Here’s an example of an extremely basic game AI for a game:

Finite State Machine

Pretty basic stuff I hope. The AI will patrol around until it finds an enemy. Once it has located the enemy it will shoot it until they are dead, and then it will… have a panic attack because there is no way to get back to the patrol state! The problem is that this AI is really boring – playing against this would get very predictable very fast. You really need a few more states to account for various interesting events. For example:

Finite State Machine

Oh God, what happened here? This is a slightly more interesting AI, but even this one is missing some pretty vital parts. E.g. If you throw a grenade at an AI making coffee he will totally ignore it – you need to add more connections from basically every node to dive for cover if a grenade is sighted. If the enemy is no longer in sight after dropping snacks the AI will be confused, so you need to add a connection there to “search cautiously”. Once again, there’s no way back from combat to patrolling so we need another connection there. If we wanted to add in little things like AIs meeting each other mid patrol and exchanging some small talk we’d need a whole load of states to handle seeing each other, stopping, talking and all the extra connections for what happens if they see a grenade/enemy while doing all this. Now imagine what would need to be done to add another weapon type into the game (e.g. a flash bang grenade), or a special enemy type (e.g. one who can only be taken down by specialised weaponry).

What I’m trying to get at here is that FSMs might seem like a good way to create AIs (because the game designer retains complete control), but actually they’re terrible because the designer retains complete control of every action the AI will ever make which is loads more control than is really practical.

Why Would You Tell Me About Such A Dreadful Way To Design AI?

Heist doesn’t use any FSMs for AI (it does have a rather complex FSM for network session negotiation, but that’s something we want to be boring and predictable), so why would I bother telling you about this approach? Finite State Machines were the way game AIs were written almost exclusively up until 2000 (as far as I can tell, I’m not exactly a history student). Even today, they are still an important part of game AI. I’ve mostly talked about FSMs because some of the systems I will be discussing were invented almost entirely to solve the problems with them, and discussing these systems without first discussing the basics of FSMs would be very difficult.

Coming Soon

I’m going to discuss Goal Oriented Action Planning and Behaviour Trees in the next couple of entries. These are techniques which improve upon the limitations of Finite State Machines.



blog comments powered by Disqus