Tutorial
icon-dog1_02

The Backbone of AI Behaviors: Movement and Animation

Alex J. Champandard on October 31, 2007

This article continues a series building the AI for a simulation game from the ground up. Last week, you found out what assets and libraries this project uses, and you helped figure out a first design to show off some simple but useful behaviors.

The best place to start implementing game AI is with movement and animation control. So this tutorial first explains what the desired behaviors are for the dogs in our simulation, then goes through the requirements and parameters of the low-level actions. After that, you’ll learn how behavior trees work quickly, and how they can be applied to this design in practice.

The Design

Last week’s article suggested that the first steps in building the actor AI should be movement and animation. Based on the comments, the following was decided:

  1. Use randomness as a basics of decision making to create emergent behaviors.

  2. Let the behavior tree apply coherence to the animations.

The resulting behaviors will essentially be as Sergio described [1] in the comments:

“Have dogs move around to random positions, stay there for a random amount of time before moving again, and have them play a random idle animation (lying down, barking, peeing, whatever). Emergent behavior at its best!”

Now as Diego mentioned [2], using predefined sequences is also important as it applies some structure to the behaviors. This is what the behavior tree is for.

Low Level Actions

The implementation will focus on three actions to serve as the interface with the rest of the game. Not only is it important to specify how they work, but you should also think about their parameters — as Dom mentioned [3].

The three actions required for this week’s design are:

  • Move — This controls translation relative to the current position of the dog. This is specified as a 3D vector (customisable) onto the transformation matrix. Most movement is constrained to the flat X, Z plane, as the animations specify the Y height if necessary.

  • Turn — Likewise, it controls rotation relative to the dog’s orientation. This should be specified as a yaw angle only (around the Y axis), as rotation around the other two X and Z axes is specified by animations if necessary.

  • Animate — This plays a single animation on the dog’s skeleton. The speed and looping are options specified to the action. For this first iteration, no blending or animation transitions will be implemented.

All actions should perform independently of frame rate, and perform the necessary interaction with the engine to achieve their purpose.

Dog Skeleton

Screenshot 1: A dog’s polygons and its underlying skeleton.

Logical Control

As far as the behavior tree goes, there are a few high-level tasks required to control the execution of the actions. These are called composite tasks (since they contain child tasks), and can be assembled hierarchically to create more complex logic. We’ll need:

  • Sequence — This task plays its child actions one after the other. For example, move to a location, then sit down. (Learn more about sequences.)

  • Parallel — This kind of tasks executes its child tasks concurrently. This week, they are used exclusively for playing animations while moving, e.g. for walking or turning. (Read all about parallels here.)

  • Probability Selector — This task picks a random child task to run. For example, if the dog wants to rest, it could randomly pick sitting or lying down. (More details about selectors.)

  • Priority Selector — This task tries to execute its children in order. If the current child fails, then the logic falls back to the next option. For example, peeing is more important than wandering around.

Now, the biggest problem is that the actions described above (e.g. move, animate) always succeed as they are not context-specific. So the selectors will never have to fallback to a different behavior. Using a primitive Fail action fixes this problem, and forces the decision-making system to deal with failure. These actions are mostly intended for being used within probability selectors, so you can specify that nothing happens a percentage of the time.

Behavior Tree Design

Here’s how everything is plugged together into one large logical structure that controls the whole behavior of a dog. The root of the tree is implemented as a priority selector that picks in order: bodily functions, active behaviors, and passive behaviors (each of these are implemented are probabilistic selectors). Specifically speaking:

  1. Bodily behaviors are high-priority things like resting, sleeping, eating, pooping, etc. These are chosen randomly as a probabilistic selector, which also selects a Fail action a large proportion of the time.

  2. When the bodily behaviors fail, the root selector falls back to the active behaviors. These are walking around, running, chasing tail, scratching, etc. This is also a probability selector that fails part of the time.

  3. When the active behaviors fail, the next fallback are passive behaviors. For example, this involves sitting, lying, standling idle, etc. This is another probability selector, but this one never fails since there are no more fallbacks.

At a much lower level in the tree, the actions are assembled together into parallels and selectors to make realistic behaviors.

  • On a lower-level below the selectors, sequences are optionally used to combine multiple animations into meaningful sequences. For example, before walking the dog could look around, and after eating it could sit down.

  • Even lower in the tree are parallels, used to combine animations and movement actions together. When turning or walking for example, the transformation matrix of the dog needs to be moved in space at the same time.

As a diagram, it looks like this:

Behavior Tree

Figure 2: Behavior trees for the dog’s AI logic.

The orange leaf nodes are actions for movement and turning. The beige leaf nodes are actions for animating the dog. The red diamonds are actions that just fail. The dark grey P stands for a parallel of actions to make a composite behavior. The light grey S represents a sequence of lower level behaviors. The question marks in dashed circles are selectors, priority selectors at the top level and probability selectors below.

Next Week: Implementation Details

The following article will show how this is actually implemented in C++, along with some code listings. You’ll also get to see the full detail behavior tree that controls the dogs. And, hopefully, you can watch a video of what it looks like in practice!

In the mean-time, if you have any comments or questions, feel free to post them below.

Discussion 1 Comments

pachanga on November 8th, 2007

You've got a typo in "Last week" link. P.S. Your blog is awesome! Keep it going ;)

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!