So is there an alternative to using state machines in gaming AI? Not entirely – state machines are still required to define simple behaviours in gaming characters, and they’re perfect for the job, so there’s no need to change them. Creative Assembly, for example, still uses a state machine for ‘man shooting’, among many other states.
The problem is when you want to make your characters act more intelligently without cluttering up your CPU resources and creating huge, complicated workloads for programmers. The answer to this is a relatively recent development in gaming AI called the goal-orientated planning system.
Monolith’s F.E.A.R. was one of the first games to bring planning systems to the fore when it launched at the end of 2005, and it was instantly noticeable when you saw multiple characters on-screen acting uniquely and in some cases, very humanly. Gone was the straightforward shooting and wandering around, and in came an advanced force of enemies that would vault over obstacles, duck to avoid fire and kick you during close combat.
In simple terms, a planning system makes a gaming character work out what it has to do in order to fulfil an objective. Instead of having a series of rule-based behaviours in a state machine jostling for attention, it will have a set of goals or objectives, and the character has several choices of ways to achieve them, which depend on the current circumstances. This diagram (see right) was drawn by Jeff Orkin from the MIT Media Lab, who also worked as a senior software engineer on F.E.A.R., and it shows how an AI character forms a plan using a goal-orientated planning system.
In Empire: Total War, typical goals would be ‘make sure my flanks are secure’ or ‘look after this fort efficiently’, which are always prioritised according to the situation. In order to achieve a goal, the computer needs to look at the situation in which it wants to be, and then work backwards from it to calculate the best way of achieving the desired result.
Creative Assembly introduced its own planning system in Empire: Total War, which could make the AI much more unpredictable compared with previous Total War games. Richard Bull worked on the battle AI in the game, and describes a planning system as "like a state machine that re-writes itself", but adds that "it isn’t a magic system in that it isn’t capable of creating its own objectives or tasks; we have a repository of things that the AI can do, and a repository of things that the AI might want to do".
When using a planning system, the AI works on a per-goal basis, working out which goal to prioritise after analysing the situation. In Empire: Total War, Bull gives the example of the AI "rolling its line infantry with cavalry on its flanks and with artillery on its wide flanks waiting to get within range". Bull explains, "It would then be dangerous for the planning system to say 'well actually, I want to use these guys to do this job over here' at the risk of damaging the whole army plan, so the AI takes the resources into account, as well as their current activity and state of action, plus the enemy threat and the terrain."
Bethesda also moved over to a planning system for the combat AI in Fallout 3. Jean-Sylvere Simonet, a programmer at Bethesda who worked on the AI in the game, explains that it "combines simple actions (small state-machines) into entire plans. We implemented a planner for this after trying out other alternatives. In the end, an NPC in combat was able to prioritise goals and actions to maximise their chance of success".
If you kill one of these Super Mutants in Fallout 3, the other won't think twice about picking up his dead brother's weapon if that's the most efficient way of achieving his current goal
The end result in Fallout 3 is that an NPC works out the most efficient way of achieving its goals, which makes it appear as though it’s thinking for itself. It’s impressive stuff to watch. For example, suppose there are two Super Mutants in front of you, you kill one of them, and the other one then runs out of ammo. The remaining Super Mutant will then have the goal of finding a new weapon, so the planning system will work out the most efficient route to obtain one; if the nearest weapon is on his dead brother’s body, he’ll pick it up. This level of unpredictable behaviour is very complicated in a state machine, but a planning system means that the NPC does it automatically. Planning systems aren’t the answer for everyone though.
Relic, for example, still uses state machines for the AI in Dawn of War 2, since the developer wanted the AI to be predictable to a certain degree. Chris Jurney points out that when a player issues an order to a squad, "he then expects that unit to carry it out to the best of his abilities. Because of this, it’s very important that units perform consistently so that users can build an expectation of what will happen when they click".
"As a result," says Jurney, "for the purposes of AI, this means that predictability trumps smarts, so things like learning or re-writing decision trees are out. The expectation of getting the exact most optimal behaviour is a lot higher in RTS games as well, because the player can see every action of every entity he’s controlling and fighting against."