Article
files/essays/anatomy-icon

The Anatomy of an AI Architecture for Game Characters

Alex J. Champandard on June 20, 2008

Would you be surprised to hear that regardless of the technology you choose to implement your decision making system there are some very common patterns that reoccur in AI architectures? Whether you implement a planning engine based on STRIPS or HTN, or a more reactive system using fuzzy logic or behavior trees… All of these technologies, when plugged together in a game AI architecture, will exhibit similar patterns that don’t even depend on the character-type or even the style of game.

This article will help you understand these principles so you can make more informed decisions about which technology to use where, find bottlenecks and problems in your current system, or simply to improve your overall architecture. You’ll see how technology based on either heuristics or hierarchies each serve their purpose, but more importantly, you’ll learn where they are better suited.

Constraints and Restrictions

When building a decision making system, you typically face many different kinds of requirements, which can be broadly classified into two categories:

  • Specifications from the designers (e.g. emotional states, gameplay choices), or goals from the level scripters (e.g. orders, behavior restrictions).

  • Limitations from the animation data — among others assets. For example, certain motions can only be performed after others (only eat when sitting, only sprint from a walking state, etc.)

You may recognize a familiar issue of top-down vs. bottom-up that’s been discussed here on AiGameDev.com a few times already. The fact is it doesn’t particularly matter which way you approach the problem since you need to take both types of requirements into account to be successful.

What’s important here is that these constraints affect the decisions that are made by your characters. In first- or third-person shooters, the enemies typically don’t have that many possible actions, and even fewer top-level states. However, even with a larger space of possible actions, your system has a very low-dimensionality in terms of possible choices: “If you do anything but *this* action here, then it’s a bug.”

Top-Down Restrictions and Bottom-Up Constraints

Figure 1: There are usually very few decisions at the highest and lowest levels of the architecture. Your requirements dictate this.

Symbolic Decisions

“Only classical AI has managed to solve problems requiring precise logical control.”

To deal with such tight requirements, developers typically use so-called “symbolic” or “classical” AI like finite-state machines, rule-based systems, or even planners. In all these cases, you basically have to either manually create transitions, individual rules, or edit pre-conditions and side-effects to make sure that your characters do the right thing at the right time.

These days, developers in industry are getting pretty good at building these kinds of systems, using a combination of automation and hand-crafting. Techniques like hierarchical logic help provide some structure, while planners help fill in the gap using logical reasoning. Although, it’s interesting to note that only “classical” AI has really managed to solve this problem requiring such tight logical control…

Example: The soldiers in F.E.A.R. at the lowest level, use a finite-state machine with two basic states (i.e. move and animate) although the AI can set many different parameters for these discrete states. The challenge is making sure that the sequence of states and parameters chosen actually creates believable human-like animation.

A Land of Opportunities

Despite the restrictions from high-level goals and the low-level sequencing of actions, there’s a place in the middle where the two meet where many more choices open up. In fact, it’s almost a combinatorial explosion of different choices you can make at this level.

Here are some examples from action games, to illustrate the kinds of problems that have numerous solutions — many of which are perfectly valid solutions:

  1. Selecting a weapon based on the current combat situation.

  2. Picking the best target from a list of threats…

  3. Deciding where to move to cover, of many options.

  4. Finding the best combat action to perform.

These types of decisions don’t particularly require tight control like in the previous cases. In fact, when you’re developing, you can often start off with a random number generator as the first implementation!

Combinatorial Explosion of Mid-Level Decisions

Figure 2: An AI architecture is typically structured in layers; the ones in the middle have the widest variety of choices.

Heuristic Evaluation

Now you can certainly build a whole AI system using classical AI techniques like planners or state machines, but in certain situations these are no longer very appropriate. In practice, developers in industry typically implement their mid-level systems separately, using technologies like fuzzy logic or a voting/filtering system. These techniques could be classified as heuristic approaches since they evaluate the value of many different solutions, and then pick the best one.

The other symbolic layers we discussed earlier are much better developed in commercial AI engines. However, this area is very promising for the near future, since “modern” AI techniques could all help design systems that are better than the random number generator. This includes:

  • Reinforcement learning of choices based on high-level goals.

  • Data-mining behaviors from large quantities of play testing data.

  • Observing expert play and training an AI using imitation learning.

Research is already underway in this field, but now that developers are comfortable with the symbolic part it may take less time to integrate these ideas into a modern game! (Particularly since these techniques work well on parallel hardware, and also benefit from large quantity of data from online games.)

Summary & Discussion

The decision of game characters are subject to many requirements, based on design or resources available. AI Architectures are typically built to deal with these restrictions and constrains by using classical/symbolic/hierarchical AI systems like finite-state machines and planners. However, once this problem is dealt with, it creates an incredible number of opportunities at the mid-level of the architecture. These decisions are typically made using heuristic systems like fuzzy logic, or manually crafted voting systems, etc.

More often than not, an architecture will focus on either approach: hierarchical or heuristic. However, both are required to create great behaviors that are both consistent and believable (respectively).

Does your system support both these approaches? Do you focus more on one than the other? Post a comment below!

Discussion 3 Comments

alexjc on June 20th, 2008

Oh, man that was a fun article. It practically wrote itself :-) The implications, however, are far reaching in my opinion... [LIST] [*]The symbolic AI at the top and bottom can't easily be parallelized, but heuristic AI can. Is parallelism what will finally convince developers to adopt modern AI techniques? [*]Developers in industry tend to spend lots of time on a framework for the symbolic stuff, yet the heuristic stuff is very ad-hoc. What would be the impact of better frameworks for heuristic problems? [*]Academic research in computational intelligence to focus on the heuristic stuff only, and completely throws all requirements out of the window. Are we now better placed to [URL="http://aigamedev.com/forums/aigamedev.com/architecture/learn-realistic"]integrate[/URL] it?[/LIST]Anyway, thoughts welcome!

Jare on June 21st, 2008

I'm not sure that decision-making (making an informed yet interesting choice among a number of possibilities) happens only at the middle, which is what I understood from the way you described it. A bot deciding to fight or flee, an enemy coordinating with its peers for an attack, those seem pretty high level to me. The distinction between what is heuristic and what is directed is very interesting, though, helps clarify the concepts.

alexjc on June 21st, 2008

Jare, Decisions happen everywhere in the architecture. But there are fewer correct decisions at the highest and lowest level because you have the most constraints. For example, at the high-level designers have pretty clear ideas of how they want to make the player seem like a super-hero, and that usually involves triggering attack, retreat & regroup, last assault, flee (e.g. [URL="http://aigamedev.com/reviews/halo-ai"]Halo[/URL]). So fundamentally, if you do anything but those states, then it falls out of the scope of the design... Also for single player games, you'd be surprised how tightly scripted AI characters can be. So there are very few choices in those cases too... I hope that clarifies things! Alex

If you'd like to add a comment or question on this page, simply log-in to the site. You can create an account from the sign-up page if necessary... It takes less than a minute!