Tutorial
icon-dog2

On the Effectiveness of Random Decisions in Structured Behaviors

Alex J. Champandard on November 7, 2007

This tutorial on AiGameDev.com continues the series which builds simple AI logic for a simulation game. The previous article established a first design. This time, you’ll see how it can be implemented at the low-level.

It’s surprising how effective random decisions can be when they are structured together into a tree of sequential behaviors. After a few hours of work, the dogs turn and walk forward for a bit, and randomly play specific animations like sitting or scratching their backs. With a little more tweaking, there’s little doubt that this approach can provide the best bang for buck as far as “fake AI” is concerned.

Here’s what the video looks like. The playback speed is slightly accelerated and the randomness of the decisions is increased artificially to help show off the different animations in a short amount of time.

Obviously, there’s still a long way to go — particularly in terms of animation quality and temporal coherence of the decisions (e.g. not peeing too often, or sleeping/sitting shortly after pooping).

Animate Action

The first step in the implementation is to plug in the behavior tree to the animation system via an action. A different instance of this class is created each time an animation is played.

class ActionPlayAnimation : public Action
{	
public:
  // This function is called every update.
  Status execute();
  // Initialization before the first update.
  void setup(Ogre::Entity& entity);

private:
  Ogre::AnimationState* m_pAnimState;
  SettingsPlayAnimation m_Settings;
  /* ... */
};

The action initializes itself from an Ogre3D entity, which is used to access the correct animation state object. An internal settings object is used to customize the action via the behavior tree. (Two lines of plumbing macros from Game::AI++ are omitted.)

The initialization function must enable the animation state and set the time to zero, but the bulk of the work is done in the execution function:

Status ActionPlayAnimation::execute()
{
  m_pAnimState->addTime(m_Settings.getSpeed());
  if (m_pAnimState->hasEnded())
  {
    m_pAnimState->setEnabled(false);
    return COMPLETED;
  }
  return RUNNING;
}

This action is very low-level; it’s directly responsible for activating and stepping the animation forward in time. Over the weeks as the animation system improves, these responsibilities are likely to be handled in a separate system such as the blend tree.

Now this action has been defined, it can be instantiated as a node in the behavior tree using a type-safe tree builder, as described previously.

Node* sleep = TreeBuilder()
  .execute()
    .Speed(0.2f)
    .Loop(false)
    .Name("sleeping")
  .end();

This exact syntax can be plugged in to bigger trees to form more complex behaviors.

Translation & Rotation

The actions for movement and rotation are defined in a similar fashion as the animate action. The only difference is that they initialize themselves from a Ogre3D scene graph node, which is used to affect the transformation matrix of the dog. The only interesting code is in the main execution function:

Status ActionMove::execute()
{
  Ogre::Vector3 vTranslate(0.f, 0.f, m_Settings.getZ());
  m_pNode->translate(vTranslate, Ogre::Node::TS_LOCAL);
  return RUNNING;
}

Essentially, this function relies on Ogre3D to translate the scene graph node relatively to its current position. The rotation action does the same thing conceptually:

Status ActionTurn::execute()
{
  Ogre::Quaternion qRotate;
  qRotate.FromAngleAxis(
            Ogre::Radian(m_Settings.getSpeed()),
            Ogre::Vector3::UNIT_Y);
  m_pNode->rotate(qRotate, Ogre::Node::TS_LOCAL);
  return RUNNING;
}

Both of these actions rely on their settings to determine how far to translate or rotate. This is customized via the behavior tree builder like for the animation action:

Node* turn_left = TreeBuilder()
  .execute()
    .Speed(+1.0f)
  .end();

Building Up Complexity

Given these low-level behaviors, they can be plugged together to make more complex behaviors using sequences and collections. For instance, the process of walking forward or turning around is defined as running a movement action while playing an animation:

Node* walk = TreeBuilder()
  .composite()
    .execute()
      .Speed(10.0f)
    .end()
    .execute()
      .Speed(1.0f)
      .Loop(false)
      .Name("walk")
    .end()
  .end();

These composite behaviors can also be sequenced together in the same fashion:

Node* wander = TreeBuilder()
  .composite()
    // Turn behavior
    // Walk behavior
  .end();

The child behaviors within the sequences can be plain animation actions or alternatively, the collections defined previously.

Top-Level Behavior

This is how the root of the behavior tree is defined. The top-level node essentially repeats the process of selecting a type of behavior based on its priority.

Node* root = TreeBuilder()
  .decorator()
    .composite()
      // Bodily
      // Active
      // Passive
    .end()
  .end();

This behavior can be applied by adding it to the brain of a dog using the following syntax:

alive::Brain brain;
brain.add(*root);
// ...
brain.tick();

These brain objects are in fact stored within a lightweight Dog class, responsible for helping initialize the actions as they are added to the behavior tree.

Room for Improvement

While the implementation of all the actions and behaviors is in place, there are still lots of opportunities for improvement on the design side.

  1. Certain random choices do not make sense from a temporal perspective. For example, the dog may just fall asleep directly after pooping, without moving.

  2. Most behaviors just play a single animation, with optional transformations in 3D space. More interesting behaviors could be achieved by using sequences to lead into and follow these animations.

  3. The only control over execution times of the behaviors is by making the animations not loop, and sequencing them over again. For example, the walk animation in the video repeats exactly four gaits every time.

  4. Many actions that are selected randomly should not be re-selected too often. It makes the behaviors seems a bit odd, and prevents the dog from exhibiting a varied behavior.

Such problems can be remedied with little extra technology, so next week’s article will explore different strategies for achieving this, and provide a higher-level overview of the resulting behavior trees (using mostly graphs now the low-level code is in place).

Discussion 3 Comments

FuriCuri on November 9th, 2007

Hi there. First I want to thank you for your great articles. It's really great to be able describe such complex thing like game AI with ease like you do. So keep up a good work. I want to propose my solution to problems you mention in "Room for Improvement" section. Let there be the "markers" (the name for this popped from the top of my head). Some global (for our AI system) list of strings (or IDs - whatever). Starting and/or completing an action can result in one of this: 1. Create marker. 2. Delete marker. Let each marker have an expire timer - when marker expires it will be automatically deleted. Of course we can set marker with infinite expire timer (let this will be by default). And let there will be a condition restriction that can be applied to any node or leaf in our behavior tree. The condition will contain some very simple logic that operate with markers existence. A little example. Let action "Sleep" creates a marker "Had a nap" uppon completion with expiration in 1 minute. And lets actions "Sleep", "Sit", "Lie down" have execution condition [!IsMarkerExists ("Had a nap")]. That way we can guarantee that dog will not fall asleep, sit or lie down in at least 1 min after it has a nap. Well, that the first improvement that comes to my mind while I was reading your great articles. I'm not so experienced game programmer as you, but maybe this will get you to more good AI solution. Keep it going.

FuriCuri on November 9th, 2007

Just spotted that my idea probably just a particular implementation of decorators :) Well, I hope in next article we'll see those too. Looking forward to it.

alexjc on November 10th, 2007

[B]LM[/B], Thanks for your comment. You're absolutely right. I do plan on implementing this with a decorator that stores a floating point number, keeping track of the last time since the behavior was allowed to run. Then, an adjustable threshold specifies if the behavior can run again based on the current time. I don't think I'll implement that this week, as there are still some good ways to improve the behaviors without it (plus I have enough material for a whole tutorial already). But next week definitely! :-) 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!