The problem of Game AI

This is the second part of the thread I started in The Coderack and Codelets, which was a brief and probably incomprehensible introduction to the Copycat architecture. Now I want to look at the actual problems that I want to solve, i.e. the problems and limitations of Game AI as it exists today.

Consider are fairly typical but complex situation that a good Game AI should be able to handle: a group of warriors that does an ambush on a bandit’s lair. As the battle evolves each character AI has to perform a number of tasks (in no specific order):

• Path finding: don’t run into trees or get trapped in a dead end.
• Group movement: the group should stay in formation, warriors should not get singled out and become easy prey for the enemy, and gaps in the formation should quickly be closed so the enemy cannot break through and split the group.
• Battle: well, fight for you life or you’ll be dead.
• Communicate: listen to orders and adjust behavior, or react to a comrade’s call for help.
• Situation assessment: where are the enemies, who should I attack?

The biggest challenge is to make these tasks interact properly. For realistic behavior the fact must be acknowledged that each character has just a limited “cognitive capacity.” Let’s look at an example:

A character that is busily defending himself against two enemy fighters will not turn around to help a comrade, he might not even hear (or better: have the mental capacity to process) his call. His movement is mostly determined by the battle and his enemies, so his path finding is reduced to hold position or retreat – and he has no time to look around to realize that the direction is he moving to is a deadly dead end. Once his enemies are defeated the character is able to spend more cycles on other actions, like looking where the battle has taken him, reassessing the situation, regrouping, looking for new enemies to attack or noticing the archer hiding on a roof.

These are just the most obvious tasks which are directly related to a combat situation. Characters have much more behaviors which – on first sight – are not related to combat. For example taking shelter when it is raining, because getting wet is somewhat unpleasant. This is of course a behavior that should be suppressed while fighting. But what if it is a pitch black night and the torch in his hand is the only source of light? Letting the torch get extinguished would be suicide, so in some circumstances seeking shelter from rain can make sense even in the middle of a fight.

And a combat situation is one of the easiest things to handle, because of its nature only short term and tactical decisions have to be made. Dialogs or strategic decisions are much harder because they can be influenced by all previous player actions. Traditional system quickly reach their limits here, for example I encountered several situations in games like Oblivion or Fallout 3 where I completed quests in an order that was not anticipated by the designers and the dialogs conflicted with my previous interactions with certain characters.

Many, many rules will not apply or get activated in any situation, but there’s no a priori way to sort out unneeded rules. At any given point the whole repertory of behaviors as well as the full range of sensory input the character gets from his environment has to be considered by the AI engine. Selecting a subset in an “intelligent” way just moves the problem to another layer without reducing the complexity. And just applying some simple heuristics to cut down the complexity leads to strange and nonsensical actions and discontinuities in behavior (which can often be seen is current titles).

The point is that the complexity of the problem growth exponentially with the wealth of rules and behaviors that the characters have. And for more realistically behavior of characters you want a lot of rules. The current state-of-the-art AI architectures, which build on rather rigid algorithms (finite state machines, decision trees, etc.), become very hard to maintain and their runtime characteristics go down the drain when faced with this combinatorial explosion.

After this short exploration of what is problem is, let me try to explain why I think the Copycat architecture could solve these issues.