Article
files/tree-topdown

A Technical Overview of Game::AI++

Alex J. Champandard on July 15, 2007

Game::AI++ is an extensible decision making and control system, specifically designed for actor behaviors in virtual simulations. The library uses a unique combination of existing techniques to overcome three specific challenges:

  1. Integration of Designer Input with Automated Algorithms

  2. Unification of Planning and Execution

  3. Ubiquitous Support for Concurrent Behaviors

The source code will be released to subscribers of the Game AI Newsletter for a closed beta on August 1st. Alternatively, you can get an early copy now by reviewing this site at Stumble Upon.

Challenge: Integration of Designer Input with Automated Algorithms

Generally, AI is a balance between pure reasoning and domain experience. In the games industry, this corresponds to two opposite approaches for building decision making and control systems.

A Behavior Tree

A simple behavior tree.

  • Human experts create the behaviors by hand, micro-managing every detail. Typically in games, this is done with a combination of state machines and behavior trees, where the designers specify almost everything by hand. Then, the hierarchical structure is traversed top down, all the way down to the leaf to find valid actions, which execute greedily.

  • A planner works out the correct order of behaviors, typically using the STRIPS algorithms. This is like path-finding to combine low-level actions with A* to find a way to reach the goal. There’s no need to assemble the behaviors directly, but it requires more programming to model the world, annotate each action with preconditions and side effects, gather data then execute the plan, etc.

A STRIPS Search Tree

A simple STRIPS search tree.

Ideally you want both; it should be possible for designers to control everything if they wish to (e.g. to add realistic human-like quirks the behaviors), but otherwise let the algorithms take over (using pure logic to find intelligent solutions). This would spread the workload more evenly among the development team; the designer doesn’t have to baby-sit a state machine or behavior tree, and the programmer wouldn’t need to explain everything about “realistic” behavior to a planner.

Solution: Express Each Behavior as a Custom Search

The common technique behind both approaches is the tree search. A planner searches a uniform tree of dependencies and side effects, and a behavior tree has layers of different behaviors that traverse their children. So whether the search tree is structured backwards from the goal, forwards from the current state, or top-down from the root behavior, they still fundamentally all trees.

To unify these two approaches, it should be easy to create behaviors that are custom search interpreters. So for example:

  1. A node in the planner’s search tree would recursively ask its dependencies to search themselves.

  2. A node in the top-down tree requests its child behaviors to run and accomplish their task.

Each of these nodes overrides the search locally, and does not know other nodes are searched. This makes the system modular, and it then becomes possible to mix and match between the different kind of nodes, thereby assembling different kinds of trees together. (This is, in effect, a form of hierarchical planning.)

Custom Search Tree

A custom search tree; each behavior is modular.

It’s simple in theory, but there are two catches to get this right:

Efficiency
Having only one search interpreter, like A*, is very fast. Having different interpreters in each node slows things down — most likely by an order of magnitude. But, these custom nodes are great ways to provide domain experience, like in a hierarchical path-finder. This speeds up the overall search by multiple orders of magnitude, so you end up with a net gain for most trees. (The fastest planners are hierarchical ones, not heuristic ones.)
Intuitiveness
Ultimately, the system must also be easy to use by the designers, at least as much as the behavior trees are. To do this, it’s necessary to edit the tree as a set of chunks that plug together well. Providing common top-down control primitives like sequences, selectors and decorators achieves this for designers. It also becomes easy for programmers to annotate actions with dependencies and side effects.

Challenge: Unification of Planning and Execution

Making high quality behaviors, both intelligent and realistic ones, involves combining decision making (planning) with control and monitoring (execution). They’re equally important, yet there’s a tendency in most games to focus on either one or the other…

  • A behavior tree uses almost no planning. Instead, it cleverly uses greedy search for behaviors that match, so that no looking ahead is necessary (for well designed trees). But it’s not entirely reliable; designers can’t make sure that every behavior tree works in all contexts.

  • A raw planner provides no execution, it assumes that the plan itself can be executed correctly. Obviously, when it fails then the planner starts again from scratch – and that’s not the best approach on large problems.

So why unify them? A complex behavior can’t be fully planned upfront, so it should be easy to change a plan dynamically as changes occur in the world. Dealing with failure is a very human quality and getting it right is important. By integrating the planning tree with the execution tree, the designer gets as much control over both of them, and can specify how they integrate together to make the most realistic behaviors.

For example, it would be possible to:

  1. Support lazy replanning, where problems are dealt with on the fly when they occur.

  2. Support incremental planning, as only the start of the plan would be executable.

  3. Fake human planning by executing certain behaviors while planning, e.g. talk about options or make gestures, or taking time to remember information.

Also, unifying the two algorithms results in much simpler code! So, how does Game::AI++ achieve this?

Solution: Everything is a Behavior Transformation

Assume the following; the outcome of planning is a set of possible behaviors to be executed, and the outcome of execution is a side effect in the world. Both also, indicate whether they succeed or fail. Ultimately it’s possible to treat them all in the same way by looking at them as behaviors that return other valid behaviors in that context.

  • A planning behavior returns a list of possible behaviors to be executed in the world.

  • An execution behavior, once run, returns an empty behavior that does nothing.

  • A planning and execution behavior will keep returning different trees that combine planning and execution.

Tree Transformation

A tree with two valid transformations in this context.

This process is like transforming a behavior tree into other trees that are valid in that context. The client behavior can then select which resulting tree it wants to run.

Challenge: Ubiquitous Support for Concurrency

The most realistic and intelligent behaviors involve doing multiple things at the same time. In particular, it’s important for game actors to:

  1. Support multiple long-term behaviors.

  2. Handle events and short-term responses at the same time.

  3. Plan on multiple independent problems simultaneously.

Here’s how Game::AI++ handles it.

Solution: Implement Behavior Search with Cooperative Scheduling

Behaviors for both planning and execution are written as coroutines. These are functions with their own memory (closures) that can pause and resume where they left off. For convenience, there’s a scheduler responsible for managing these coroutines.

The process of searching another node is done by creating a transformation, which behaves like a lazy iterator/generator. The owner of a behavior can request transformations by providing callback, then waiting for the scheduler to process that search.

In effect, all the behaviors are collaborating together at all times to produce the overall result.

Feedback!

If you don’t understand something, or if part of the design does not make sense to you, then feel free to ask by posting a comment. The best questions stand a chance to win an AiGameDev.com T-shirt at the end of the month!

Discussion 9 Comments

Andrew on July 16th, 2007

Just a quick question; the code you'll provide (in beta, or at an eventual release) will the source code for the AI, but what are you currently using to actually test it in some kind of environment? :) Just would be interesting to know how this style might apply (or where it might best apply or not) to the multitude of different game types (real time/turn based, 3d worlds/2d worlds, AI groups and communication, non-combat/combat) and so on. Especially since if it needs testing (thus the "beta" tag), what will be the best method to test it? I guess if it is source-code based (GLP'ed or whatever you do) you're using some kind of source-code-is-available engine to produce the working environment? I think also, your examples are good generally (I understand what they mean), but definitely I know I like a "different" way of explaining it by using an example (some ways better/worse, so need definitions and examples of course!) - for instance, "Generic FPS 101", and the enemy bot AI, but that of course is a different post entirely, since you can't really easily mix the examples and the definitions/explanations too much :) I will be on the lookout for the email even if I'm not the perfect audience :) and thanks in advance for any answers!

alexjc on July 16th, 2007

Hi Andrew, Thanks for the question. About the test environment, it's a good point. Right now I'm making lots of little tutorials that show how to implement common patterns in game AI. For example, making an action, a condition, building a sequence, doing lookahead planning before execution, etc. There will be a graphical demo at some stage, but not immediately. However, even at the end of the month there will be easily enough information for professional AI coders to learn from and work with. I have no doubt that this engine will be easy to apply to FPS and TPS. In the simplest case, it's a robust behavior tree AI (quite commonly used these days). It worked for me at Rockstar, and they use it in Halo and many other places... Some of the more advanced features with concurrency (less proven) aren't required. It's all designed in a layered fashion so if you don't include them they won't be linked into your game. But I have no doubt these features will get used; I saw first hand how my designers started using them everywhere when I implemented them into my last engine :-) Alex

alexjc on July 16th, 2007

Hi Andrew, Thanks for the question. About the test environment, it's a good point. Right now I'm making lots of little tutorials that show how to implement common patterns in game AI. For example, making an action, a condition, building a sequence, doing lookahead planning before execution, etc. There will be a graphical demo at some stage, but not immediately. However, even at the end of the month there will be easily enough information for professional AI coders to learn from and work with. I have no doubt that this engine will be easy to apply to FPS and TPS. In the simplest case, it's a robust behavior tree AI (quite commonly used these days). It worked for me at Rockstar, and they use it in Halo and many other places... Some of the more advanced features with concurrency (less proven) aren't required. It's all designed in a layered fashion so if you don't include them they won't be linked into your game. But I have no doubt these features will get used; I saw first hand how my designers started using them everywhere when I implemented them into my last engine :-) Alex

Andrew on July 16th, 2007

Great, thanks for the reply, and if it is up to contributors to provide a test engine that's okay, I'll take a crack at it myself, perhaps with one of the quake source-released engines. The advanced features do sound good, and it sounds like a expandable / modifiable solution. I'd be interested to see how this applies to non-combat games, there are plenty of real-time ones and turn based types, although FPS and TPS are obviously a central area for this research, and a working demo / tutorial of all the work is a must before getting to specific implementations.

Andrew on July 16th, 2007

Great, thanks for the reply, and if it is up to contributors to provide a test engine that's okay, I'll take a crack at it myself, perhaps with one of the quake source-released engines. The advanced features do sound good, and it sounds like a expandable / modifiable solution. I'd be interested to see how this applies to non-combat games, there are plenty of real-time ones and turn based types, although FPS and TPS are obviously a central area for this research, and a working demo / tutorial of all the work is a must before getting to specific implementations.

alexjc on March 30th, 2008

[quote]Game::AI++ is an extensible decision making and control system, specifically designed for actor behaviors in virtual simulations. The library uses a unique combination of existing techniques to overcome three specific challenges: Integration of[/quote] Read the [url=http://aigamedev.com/alive/game-ai-technical]full article[/url] on the blog.

popolon on September 25th, 2008

Hi, I'm having troubles understanding the solution proposed by AI++ to the integration of planning and execution. Is there any further documentation I could check on that? There is plenty of work in this area in the academic world. For example, Firby's RAPs, McDermott's NASL, or Ambros's IPEM system. Those are classics, but there is also some recent work (like Muñoz Ávila's RepairSHOP or our current work on Darmok). At first sight, the solution provided by AI++ strikes me as pretty elegant. But I can't understand the figure or the explanation properly (what are the yellow/red nodes in the figure?). I was thinking that there might be some interesting lesson that can be learnt from AI++ and be taken to the academic community. thanks! santi

alexjc on September 25th, 2008

Hi Santi, There's not really any more documentation on the topic except the whole source code itself. But you can look at that like you would look at a LISP interpreter -- which isn't much use without the patterns on top of it that help you build useful programs. That part I've also got answers to but haven't written down yet. I won't be working on this much in the near future, but I definitely think there are some valuable ideas in there -- particularly in terms of its potential to make the typical hacks that game developers use more elegant. Alex

popolon on September 27th, 2008

Thanks Alex, I'll definitively look into the source code in the near future. I'll let you know if I have any questions

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!