Developers of game AI are always interested in cramming more complexity into the virtual brains they build. However complexity often has a price, or rather has many prices: poor run-time, poor scalability, a lack of directability and worst of all, a murky experience for the player in which the AIs seem to act "randomly" rather than "intentionally". We will discuss the sources of complexity, the various ways in which complexity can manifest itself and also some of the architectural approaches we took in Halo 2 to mitigate these negative effects. This discussion will center on the problem of scalable decision-making, but will also touch on questions of memory, knowledge model, and control representations for the scripting and influencing of the AI by level designers.

The Brute Force Approach to Common Sense

When it comes to game AI, more is often better, in the sense that the more well-rounded an AI's behavioral repertoire is, the more unique triggers an AI can recognize, and the more unique ways an AI can respond, the more likely we are to see the AI as a common-sensical kind of creature. A "common sense" AI is a long-standing goal for much of the research AI community. For many (for example, [Lenat95] and [Stork99]), the question of common sense is intimately connected to the problems of knowledge acquisition and representation. After all, common sense can simply be considered the massive database of mundane, everyday knowledge that is so obvious to the walking, seeing, thinking human being that it never really needs to be taught or even expressed. This makes common sense a very elusive thing indeed.

For games, or at least for Halo 2, we are far less interested in encoding factual knowledge (birds have wings, water gets things wet) than we are in encoding behavior, which is perhaps a different sort of knowledge. This is the knowledge that says that when you are sitting in a vehicle seat, you have to get out of the seat before you can walk through the door, or that in order to stop someone from shooting you, you need to move in order to place a large sturdy barrier between you and your attacker. In both styles of common sense however, the solution is the same: quantity. The more the AI knows, the better.

Quantity, of course, is complexity, especially when considered along with some of the other constraints that The Game forces upon us. It is not enough that the AI be able to do it a lot of things, it is equally important that they do all those things right, at the right times, and in a way that does not break the illusion of life, or threaten the player's understanding of the AI's intentions or motivations. In Halo 2, the AI works best when the player believes he is fighting a living breathing (evil) creature, and can respond to and predict that creature's actions accordingly. As authors of behavior, one of our primary goals is to facilitate the on-going narrative that is taking place in our player's head: "oh, the grunt just ran away screaming because I pulled out my energy sword and it was scared, but when I had it cornered, it turned around and started fighting again".

Attaining both these goals - quantity on the one hand and what we might term behavioral integrity on the other - is a huge architectural challenge. Because whatever the content of the knowledge we encode, we need an appropriate container to put it all in, hopefully a container that addresses the perennial large-system-design concerns of scalability, modularity, transparency and so on.

We pay for complexity in a number of ways:

• Coherence: If behavior is action over time, we need to make sure that our AIs start, stop and change actions at appropriate times. And we must avoid at all costs the problem of dithering (the rapid flipping back and forth between two or more actions).
• Transparency: given the AI's outward stance, it must be possible for the untrained observer to make reasonable guesses as to the AI's internal state as well as explain and predict the AI's actions.
• Run-time: The most obvious of all constraints. The AI has to run at 30Hz or more.
• Mental bandwidth: When we lose the ability to reason about what's going on in the system, we lose control over it.

Quantity in service of common sense is not the only sources of complexity. Consider these others:

• Usability: The AI must be directable enough to support the larger fictional setting of the game. The "user" in this case is not the player but the level designer, who must craft a drama over the course of the level through character placement, scripting and high-level direction.
• Variety: Different AIs behave in different ways according to their character. How do we design a system that provides a base of robust common sense behavior but that also allows for character-to-character variety?
• Variability: AIs should behave different in different situations, especially when those situations are directed by the designers in service of the story (for example, one scene might demand that the player-ally AI be holed up, defending themselves from an onslaught that the player will ultimately rescue them from, while the next might send the same AI out on an assault with the player).
• Run-time: the one concern that can both suffer from and contribute to complexity. Much of the complexity of an architecture like Halo 2's stems from our desire to avoid work we don't need to do.

This paper will discuss some of the techniques that Bungie used in the implementation of the Halo 2 AI to handle the burgeoning complexity problem. The first half of the paper will deal mostly with questions of internal architecture, particularly as it relates to memory and decision-making. The second half of the paper will present some of the useful level-design tools we used to control AI and script levels.

Core Combat Cycle

In the beginning, it's all very simple. It probably starts out looking something like Figure 1. This is the kind of diagram a game designer might come up with to describe the ways in which a player may interact with AI. Clearly each of the states shown describes very different modes of behavior for our characters, preferably with their own animation styles (sneaking for searching, flailing panic for flight, etc.) How might we go about implementing this scheme?

	Figure 1: The combat cycle

The first thing to recognize is that the figure contains all kinds of hidden complexities. For example, for each of the arrows we have a question of "when is it appropriate to follow this transition?" Some of the transitions are voluntary (for example, the decision to give up searching and return to idle). Others are forced by perception: clearly from combat we are forced along a transition, either to idle or to search, when our target steps behind an obstacle. In other words, the diagram is a useful conceptual tool (particularly for designers), but falls far short of being implementable.

Behavior

What does the actual control structure look like? Like many systems, the Halo 2 AI implements a hierarchical finite state machine (HFSM) or a behavior tree, or even more specifically, a behavior DAG (directed acyclic graph), since a single behavior (or behavior subtree) can occupy several locations in the graph. An example is shown in Figure 2. This is a highly abbreviated version of the actual core behavior DAG of Halo 2, which contains on the order of 50 different behaviors.

HFSMs are a well-known and time-honored technique for decision-making. We will therefore confine our current discussion to some of the "special features" we found useful in Halo 2.

Decision routines

In a typical HFSM scheme, the role of non-leaf behaviors is to make decisions (specifically, decisions about which of its children to run), while the role of the leaf behavior is to get something done. When it comes to the decision-making process that takes place in the former, there are two general approaches: (a) the parent behavior can make the decision using custom code, or (b) the children can compete, with the parent making the final choice based on child behavior desire-to-run, or relevancy. Both options will in fact be useful to us at different times, so we leave the ability to write customized decision routines on the table.

Design Principle #1: Everything is customizable

Where we can, we will use the more general mechanism (option b), particularly for some of the core components of the combat cycle, each of which will be parent to many children (on the order of ten to twenty). Using this approach for these parents is a good idea, since writing hard-coded logic to choose between one of twenty options can be tedious, as well as unscalable.

	Figure 2: example behavior dag

Assuming we do use a child-competitive decision model, how do we actually go about picking a winner? Numerous systems feature an analog activation desire: each child provides a floating point number indicating its relevancy, and the child with the highest relevancy wins (with the previous tick's winner given an added bonus to avoid dithering). This does, however, again face a scalability problem once the number of competing behaviors gets above a certain number, especially when a very specific set of priorities is desired (for example, "fight the target, unless the player drives up in a vehicle, in which case get in his vehicle"). Tweaking floats in order to get a specific set of rules or priorities is feasible when there are two or three choices, but when there are twenty or more it is almost impossible.

We will simplify this scheme considerably by making relevancy a binary test. Using this approach, we were able to define a small number of standard decision schemes:

• prioritized-list: march down a prioritized list of the children. The first one that can run, does, but higher-priority siblings can always interrupt the winner on subsequent ticks.
• sequential: run each of the children in order, skipping those that are not currently relevant (and never revisiting it). When we reach the end of the list, the parent behavior is finished.
• sequential-looping: same as above, but when we reach the end of the list, we start again.
• probabilistic: a random choice is made from among the relevant children.
• one-off: pick in a random or prioritized way but never repeat the same choice.

Of these, by far the most commonly used is the prioritized-list scheme. It has a number of great advantages, not the least of which is that it is closely in line with the way that we generally think of solving problems: we think first of the best thing to do, but failing that we will consider the second best, the third best and so on. Whichever we choose, when a better option opens up, we immediately switch to it.

Behavior Impulses

However, this presents a new problem: what about when the priority is not fixed? In other words, under certain circumstances behavior A has priority over behavior B ("fight rather than getting into a nearby vehicle") but under other circumstances, B has priority over A? ("Unless the player is in the vehicle, in that case do get in.") To solve this problem, we use a behavior impulse. An impulse is a free-floating trigger which, like a full behavior provides a binary relevancy, but is itself merely a reference to a full behavior. When the impulse wins the child competition either the current stack of running behaviors is redirected to the position of the referenced behavior, or the referenced behavior is simply run in the position of the impulse. In the example given above, we are interested in the latter. Our priority list becomes

player_in_vehicle_impulse
fight_behavior
enter_vehicle_behavior

The important point here is that we have explicitly separated out the condition that would have made the enter_vehicle_behavior more desirable, into a separate impulse that nonetheless references the same behavior.

Design Principle #2: Value explicitness above all other things

As mentioned, impulses can also serve to redirect the current behavior stack to another portion of the tree. For example, there might be self-preservation impulses (self-preserve due to damage, self-preserve when facing a scary enemy, etc.) that are children of the engage behavior - thus the impulses are only considered when the AI is engaging. When one of these impulses is chosen, rather than running self-preservation under engage, we simply pop up a level in the tree and run self-preservation in its native position. The semantics for how this redirection is performed (in particular what level of the tree to search for the referenced behavior, and what limitations to place on the reference itself) are somewhat involved. Suffice it to say that impulses can at times act as "pointers" to other branches of the tree and cause execution to jump to that branch.

Impulses serve us well in another way. Consider an impulse that never returns a positive relevancy: this impulse will never provide us with a referenced behavior to run. On the other hand, this is an arbitrary, lightweight piece of code that can itself be run at very specific point in the behavior DAG. What might we use this code for? Anything. Perhaps we could make a data-logging call, to record the fact that we reach that point in the priority list. Or perhaps we wish to spew some debugging information to the console. Or perhaps we wish the character to make a certain sound whenever a certain condition is met. The fact is, that the code does not need to be explicitly part of a behavior to do something useful. Might this be considered a hack? In some cases, yes, since we are specifically bypassing the behavior performance step (which says that a behavior can only do real work when it is officially chosen), but in fact this is one of the design purposes of the impulse construct: to give us a convenient way to place arbitrary pieces of code at specific points in the behavior DAG.

Design Principle #3: Hackability is key

Hacks are going to happen. When they do, we must make sure we have a way of containing them. This system also imposes a healthy discipline on our hacks, since one is required to label and, in the case of the Halo 2 codebase, list them in a global list of impulses, thus making it very unlikely that we will lose track of them and forget that they are there.

Behavior Tagging

As trees grow to large sizes, we can easily imagine that determining behavior relevancy would become one of the principle contributors to run-time. After all, we are often checking the relevancy of numerous behaviors and impulses that are not actually running. Often, however, we find that many of the basic relevancy conditions are the same across many candidates. For example, in Halo 2, vehicle status (is the actor a driver, a passenger or on-foot) and alertness status (is the AI in visual contact with a target, simply aware of a target, or unaware of any targets) are practically always checked when determining relevancy.

The idea of behavior tagging is to move these common conditions out of the relevancy function (thereby avoiding having to write the same code over and over again) and encode them in a tag for the behavior, which is checked directly at decision-time. In Halo 2, these conditions are encoded as a bitvector, which is then simply compared with another bitvector representing the AI's current actual state. Behaviors and impulses whose conditions are satisfied undergo the full check for relevancy. The others are ignored entirely.

While this can be considered simply a way to speed up the relevancy check, there is another interesting interpretation. We can see these conditions as locking and unlocking large portions of the behavior tree, thus modifying its fundamental structure. For a passenger of a vehicle, for example, the unlocked portions of the tree are very limited: major branches controlling fleeing, self-preservation and searching, for example, are unavailable to it. A vehicle driver has much more available to it, but still not as much as an infantry AI. If we were to look closely at the engage behavior we would find something else: that the fighting behaviors of a driver and an infantry unit are different, the infantry unit using the fight_behavior and the driver using the more specialized vehicle_fight_behavior (the latter keeps the AI moving around constantly, whereas the former tends to pick points and stay there). Similarly the process of searching is very different for a driver versus an infantry unit, mostly for the presence in the case of the latter of a number of coordination behaviors that make searching a group activity.

	Figure 3: Allowable behaviors for infantry, drivers, and passengers

This is the first of several techniques we will present that affects the decision-making process through direct modification of the structure of the tree itself.

Stimulus behaviors

Here is another redundancy concern: imagine a "flee when leader dies" impulse. This impulse essentially waits until an "actor died" event occurs, then it springs into action, testing whether the actor that died was a leader, whether there are other leader actors in the vicinity, etc. If all its conditions are satisfied, it triggers a flee behavior. The problem is that given the architecture we've described, this impulse would need to be tested every single tick. We would like to avoid the need to evaluate this impulse continually when we KNOW that no "actor died" event has occurred. We would like, in some sense, to make this impulse "event-driven".

One way we might consider doing this is through a stimulus behavior. This is a behavior or impulse that does not appear in the static tree structure, but is instead dynamically added by an event-handler to a specific point in the tree. In the given example, the actor would receive an "actor died" event asynchronously with its main update loop (in Halo 2 these sorts of event notifications happen through a callback). Assuming it is then determined that the actor that died was of a leader class, this causes a flee_because_leader_died stimulus impulse to be added to the behavior tree of the receiving actor. This means that for a given a period of time (one or two seconds in Halo 2), that impulse will be considered for execution along with all the other static behaviors and impulses.

	Figure 4: a dead-ally event is turned into a "leader dead retreat" impulse which is dynamically added to the root child list. This impulse will cause a retreat behavior, interrupting engage, postcombat and idle but not self-preservation or retreat itself (if the AI is already running it).

Why is it important that the impulse be placed into the actual behavior tree? After all, we could simply force the actor to start running a behavior based on some decision local to the event-handling code. We don't do this, because it would not, in a sense, be a well-thought-out decision unless it was made in the context of the full tree. In the above example, we would not want to consider fleeing if we were already running enter_player_vehicle, but could if we were simply running engage. It would be ludicrous, not to mention highly unscalable, to test these conditions in the event-handler. Only by placing the stimulus behavior into the tree itself can we be assured that all the higher-level and higher-priority behaviors have had their say before the stimulus behavior can consider taking action.

This is an important point, because it underlines the fact that tree-placement constitutes as large a part of the decision process for a behavior or impulse as does its relevancy function. Note also that nothing prevents the stimulus behavior from being a non-leaf behavior, thereby allowing the addition of entire behavior subtrees in an event-driven way. Thus we are again finding a way to modify the structure of the behavior tree in order to get the precise set of behaviors considered.