Introduction

Demands for immersive gameplay and intelligent interactions with non-player characters put new focus on the shortcomings of current techniques used by game developers to make AI in games. Behavior Trees, the dominating technique used by the game development industry currently, is showing its age. It is starting to fail as game developers wants more complex AI that features emergent behavior and realistic decision-making under incomplete information. Consequently, superior AI technologies such as Utility AI, already used for some of the best AIs in games, are increasingly replacing Behavior Trees, and introducing a new era of better and more advanced game AI.

How Behavior Trees came to rule the world of game AI (and why they are in decline)

Most AI developers know that Finite State Machines (FSM) are fantastic for simple AI. By simply defining states, and defining conditions for translating between states, AIs can be invoked in infinite loops of decision-making. I.e the FSM will continue executing its current state, until conditions tell it to transition to another state.

Being able to translate from any state to any other state by specifying conditions, makes it very easy to design FSMs for AI behavior. However, it turns out this is also the drawback of the FSM approach. In professional games, FSMs can easily have hundreds of states, and at such sizes they become increasingly difficult to debug. Damian Isla outlined this in detail regarding the AI of Halo 2 at his GDC talk from 2005.

Typical Finite State Machine configuration with several behaviors. Each transition (arrows) comes with its own list of conditions.

To mitigate some of these challenges, FSMs have evolved into hierarchical structures to make them easier to design and debug. The idea of hierarchies extended the ability to manage many states, but did not remove the problem that sooner or later FSMs become unmanageable as they grow in size and complexity.

Typical Hierarchical Finite State Machine, designed to reduce complexity by separating certain behaviors into substates.

Eventually, this idea of hierarchical organisation of tasks, lead to the idea of instead organising tasks in tree-like structures, a.k.a. Behavior Trees. The idea is that behaviors are either executed one-at-a-time or in sequence. The decision of which behavior to execute is evaluated at a certain tick-rate, such as once per second. At each tick the whole tree is evaluated, and if another behavior is chosen than the last invoked, the execution state can be changed, otherwise the behavior continues to execute. In that way, a number of the shortcomings of FSMs are overcome, such as getting stuck in a state and having buggy state changes. The Unreal Engine has a nice Behavior Tree implementation that serves as a reference for Behavior Trees in game AI.

Typical Behavior Tree - starting with a root node. The root node triggers the Conditional, which selects between behavior A or B. The Conditional is sometimes called a Decorator.

Behavior Trees in many cases provide a framework for designing more comprehensible and easier-to-read AIs than hierarchical FSMs. Also, the nicely organised tree makes for easier visual debugging in practice. 
 

Complex Behavior Tree with conditionals, concurrent (simultaneous) behaviors, and a sequence of behaviors. 

However, the Behavior Tree technique has a number of shortcomings. Attempts have been made at mending some of these by implementing different extensions to the Behavior Tree model.

For very large behavior trees, the costs of evaluating the whole tree can be prohibitive. Consequently, the idea of sub trees has been introduced. The idea is that the sub tree can continue executing without invoking the whole tree, until some condition is met to exit the subtree. However, this reintroduces some of the complexities associated with controlling and debugging transitioning between states in Finite State Machines.

However, the major challenge with Behavior Trees is that even though the technique better organises behaviors, it does not provide a model for improving decision-making. The decision-making is locked to the conditional nodes, without specifying how decisions are made to invoke different subtrees.

What Are the Requirements of a State-of-the-art AI?

This leads us back to the features needed of state-of-the-art AI.

The state-of-the-art in AI for games calls for AI technologies that can support more complex, deep and immersive game worlds. In titles such as Hitman, Witcher and Assassin’s Creed, the number of non-player characters is growing, and the demands for bespoke and life-like behaviors are increasing. In titles such as Call of Duty and The Division, the number of adversaries and the requirements for deep, varying and complex tactical behaviors are exploding. Static, scripted game design no longer cuts it, to support the dynamic and ever evolving scenarios demanded by game designers and modern gamers alike.

This calls for AI that is simple to design, and yet can express complex behavior. I.e. AI that can give rise to  emergent behavior, can make reasonable decisions in situations that the game designer did not necessarily foresee, and can express a large range of behaviors similar to what would be expected by a human player.

With requirements for handling a large number of input factors and using these to select from a large number of behaviors, existing AI technologies simply break down. It becomes impossible for AI designers to map out all scenarios in the state machine or tree, and it becomes impossible to design an adequate amount of test cases to ensure that the AI behaves as intended when put in front of human players. Hence, a better, more robust, AI technique is needed.

Handling Complex Behavior is probably the dominating challenges of state-of-the-art AI. Most other problems in the game development process comes from the ability to handle the AIs when they grow in size and complexity.

A New Paradigm for AI

Killzone 2 has been lauded as a game with some of the best designed AI. Guerilla Games used a utility system for making dynamic tactical decisions for the AI, and described in detail how a simple scoring system enabled the AI to make sound tactical decisions without knowing the game world in advance. Similar systems have been used for other AIs such as the AI in F.E.A.R, Civilization and the famous Quake bots.

The utility system works by identifying options available to the AI and selecting the best option by scoring each option based on the circumstances. This has proven a remarkable well-working method for several reasons.

However, the Utility AI also has some built-in magic that makes it an overall better decision-making method. Dave Mark of Intrinsic Algorithm outlines how curves can be used to score different options available to the AI.

Example of how curves can be used to prioritize desires. All desires have an input function that is normalized to the interval between 0 and 100. The action related to the curve with the highest utility - normalized to values between 0 and 1 - is executed. The utility of sleep rises exponentially as the urge becomes stronger, the utility of using you energy declines linearly, and the utility of hunger is present at most times, except right after a meal. However, it rises when the urge ‘hunger’ becomes large enough. The urge can be different for each desire. The urge to sleep can be based on the time since the last nap. The urge to spend energy can be based on time of day, and the urge of hunger can be based on the time since the last meal. 

The curves enable the Utility AI to make decisions across a large spectrum of inputs, and gives it a fuzzy-logic quality. In practice, the Utility AI can thus make rather good decisions even in scenarios that the AI programmer didn’t foresee. This is something that the Killzone 2 AI uses in abundance, and is part of the magic behind the AI.

The ease-of-use of the Utility AI is also extended into domains that are normally difficult to handle for Behavior Trees. Comparing and prioritizing hundreds of tactical positions, such as the Killzone 2 AI does, is rather difficult in a Behavior Tree, as you cannot add branches dynamically to the tree. Some Behavior Trees, such as the one in Unreal Engine’s Blueprint, solves this by making a special module available called the Environmental Query System available. This system can query the surroundings for positions and prioritize them according to specific rules - resembling linear programming. However, the Utility AI principles can take any group of objects and score these, whether they are tactical positions, planets, goals or weapons. This makes the methodology very versatile for decision-making.

Showing the Difference between Behaviors Trees and Utility AIs

To understand the difference between Behavior Trees and Utility AI we can look at a concrete example of a simple AI often used in certain game genres, e.g. first-person shooters.

The AI has four actions: Move to Enemy, Fire at Enemy, Move to Cover, and Load Weapon. The AI has four inputs to base its decisions on.

The outline of how the AI works is quite simple. If the gun is loaded, you should consider firing or moving closer to the enemy if the enemy is too far away. If your gun is not loaded, you should reload, or seek cover before you reload if you are too exposed. Whether you should fire or move closer, depends on the distance to the enemy, whether you are in cover, and the distance to the nearest cover. However, as is always the case with AI, there are a few exceptions to the general rules. If we are very close to the enemy, the AI might have to reload on the spot, as the AI might not make it to cover. If we are close to cover, we might go to cover first, as the advantages of firing from cover are significant. If we are far enough from the enemy, we might also reload even if we are not in cover. Either because the enemy is unlikely to hit us, or because the cover is even further away.

The following table shows the actions that should be executed for different input parameters.

We will first implement this AI in a Behavior Tree and subsequently using a Utility AI.

Behavior Tree

The figure below shows how the AI could be configured in a Behavior Tree. An initial conditional would determine what subtree to traverse, based on whether the gun is loaded or not. Subsequently, another input parameter such as cover state can be evaluated. The subsequent sub-branches all have to evaluate the third parameter, such as distance to enemy, before going to the fourth parameter, distance to cover.

The order of input parameters can be shifted around, and the tree can become more or less complex depending on the order, although the resulting action will be the same. The tree might be reduced even more, but that requires extensive analysis of the tree or using analytical techniques to minimize or regularize the tree structure. However, getting to this stage from the table above is already quite time-consuming and error-prone.

The tree already has a wide number of sub-branches at this point, even though there are only four input parameters and four actions. Needless to say, the Behavior Trees can quickly become rather big. If five or more input parameters are added, the tree will grow even more complex, and if we want to shift the order of input parameters around we would need to redesign the entire tree. Also, if the game designer chooses to change just some of the rules above, we risk having to redesign a significant part of the tree.

Utility AI

The figure below shows how the AI can be implemented using utility based methods. Each action is evaluated separately, and the highest scoring action is chosen. Move to enemy is evaluated based on one point per distance to the enemy in e.g. meters. If the gun is not loaded, 100 points is subtracted, to ensure that the move to enemy action scores very low if this is the case. Fire at enemy receives 75 points if the AI is within 50 meters proximity to the enemy. If the AI cannot make it to cover, i.e. the distance to cover is greater than the distance to the enemy, Fire at Enemy receives another 50 points. If the gun is not loaded, 100 points is subtracted, to ensure this action doesn’t execute in that case. Move to cover receives 50 points if the AI is not in cover. It receives another 50 points if the AI is within 50 meters proximity of a cover. Load receives 75 points if the weapon is not loaded, and 50 points if the AI is in cover. Load has 125 points subtracted is the gun is not loaded.

The Utility AI requires just one table with 10 scorers, of which 1 is reused, to be implemented. Furthermore, the order of evaluation of the input parameters doesn’t matter. Hence, there is no need to minimize or regularize the AI. Additional parameters and scorers can also easily be added to the AI as these just extend the table.

The Utility AI does not require a hierarchy or tree structure to implement the AI above. However, this can be added to the Utility AI as needed. Thus, actions do not need to be concrete actions such as Load or Move, but can be actions that lead to other Utility AI evaluations. In fact, the Utility AI can be used as a Behavior Tree and implement the exact same branch structure as the Behavior Tree above - if desired.

What are the Areas Where the Utility AI is especially good?

As is turns out, the utility methodology is incredibly versatile. Hence, it can be used for any type of decision-making process that can be solved via scorers.

From our experience, the Utility AI is especially good at fulfilling the requirements related to state-of-the-art AI. The list is very long, but some of the areas where we have really seen Utility AI shine are:

What are the Limitations of Utility AI?

The limitations of the Utility AI are primarily linked to it being a design-based AI. As with most AI technologies for games, the idea is that the AI should implement the use cases specified by the game designers. Hence, even though the Utility AI can make decisions under circumstances of incomplete information, and can exhibit some emergent behavior based on its ability to interpolate and make fuzzy decisions, it will still rarely be smarter that the AI developer who designed it. Furthermore, the ability to make smart decisions requires tweaking the scorers to ensure correct behavior, and this requires developer-time and game testing. Alternative technologies to avoid these limitations are in the direction of machine learning. Even though these technologies are having a huge impact on other industries, the games industry has yet to see strides in AI due to machine learning. However, there are some companies, such as Good AI, that are working on these technologies.

Conclusion

Behavior Trees are still popular in game development, but are increasingly showing their age. They have many challenges that are impairing their ability to support the requirements for complex AI in next-generation games. Utility AIs have already proven their worth in many top-titles, and have supported some of the best AI seen in games. The technology does not have many of the problems of Behavior Trees and thus holds great promise for future games, with more complex, more immersive, and ultimately, intelligent AI.

Jakob Rasmussen
CEO Apex Game Tools

Apex Utility AI Personal Edition
Apex Utility AI Pro Edition

Feel free to ask any questions!

References: