Behavior Trees Pt. 01

When I started adding enemies to the game, it quickly became obvious that they needed some sort of AI. Classics like Galaga and Xevious have enemies that make excellent use of predefined patterns, but I didn’t feel like that was going to cut it for… whatever it is I’m trying to go for here. So I needed to learn how to make things do things without me telling them things directly. First quick research turned up an awful lot of state machine driven AI implementations, but after having seen how quickly a game state machine can spiral out of control (maybe another post on my controller state machine sometime) these seemed like a really bad idea. A smarter or more experienced game developer would look at the scope of what I was trying to do and say that an FSM would actually be totally fine and serviceable, but I am neither of those things. Shortly afterward I discovered that behavior trees are a pretty common solution to this problem. They are also incredibly simple, and so seemed like a fun warmup post.

The Setup

The concept is, like I said, very simple. You want your AI characters to do things, right? So somewhere you have the thing that they do. An action of some sort like, like “point your gun at the thing you want to shoot”:

protected static BehaviorStatus PointGunAtTarget(Context c) {
    if(c.currentTarget == null) {
        c.weapon.AimStraight();
        return BehaviorStatus.FAILURE;
    }

    c.weapon.LockTarget(c.currentTarget.transform);
    if(!c.weapon.IsAimedAtTarget()) return BehaviorStatus.RUNNING;
    return BehaviorStatus.SUCCESS;
}

Let’s break this down a little bit.

Context

First, this isn’t a ‘node’ like you’d expect in a tree, this is a function. Don’t worry too much about that, just envision that further down the line this function gets wrapped up into an executable ‘node,’ either literally (i.e. as an instance of an object with a callable method), or at least just conceptually, so for my purposes this function represents a ‘node.’ This function is also static; this is for no real reason other than that my design lets it be, and helps you know that there’s not a whole lot of other shenanigans going on outside of it. But of course you need your AI characters to maintain some sort of state since they don’t all have the same target at the same time and don’t all have the same positioning, etc. To this end, all of the data that my AI characters need to perform these actions and make decisions is encapsulated into a “context” object and passed into these functions when I execute the tree. No need to worry about what’s in it for now, just know that it contains things like access to the character’s weapon controls so that the ‘brain’ (this behavior tree) can tell the character to actually do weapon-related stuff. It also has access to locomotion so that the character can decide to walk somewhere, and so on.

Status

Behavior tree nodes are very simple, which is my favorite part about them. They’re really just functions (or functors) that return one of three values: SUCCESS, FAILURE, and RUNNING; all of which are shown here. Step by step, the procedure my AI needs to follow in order to attempt to “PointGunAtTarget” is:

if(c.currentTarget == null) {
    c.weapon.AimStraight();
    return BehaviorStatus.FAILURE;
}

Make sure you HAVE a target. If you don’t, then you can’t really aim at anything. So go ahead and just aim straight (in case you were previously aiming at something else before you lost your target). This is a FAILURE. It doesn’t HAVE to be a failure, mind you. Maybe you consider aiming straight ahead to be a success condition, but in my case, I use this function to ensure that the AI is working toward attacking something, so not having anything to attack is bad. You could also check this somewhere else before ever calling this function, but I found it helpful to have the check here. Beyond this, we know we have a target, so our next step:

c.weapon.LockTarget(c.currentTarget.transform);
if(!c.weapon.IsAimedAtTarget()) return BehaviorStatus.RUNNING;
return BehaviorStatus.SUCCESS;

Is to go ahead and aim at it! In this case, my weapon system handles the aiming on its own and just needs to be assigned the target. The implementation of how it does the aiming isn’t totally irrelevant, though. Let’s consider a couple situations here. In one, the aiming system just immediately rotates the character to aim at the target. Something like aiCharacter.transform.LookAt(targetCharacter.transform); is pretty straightforward and immediately results in accomplishing our task; the AI is now aiming at its target! In this case, our BT function could return SUCCESS at this point; we know that the aiming is correct and 100% complete. Of course, it’s not always this simple. A more realistic situation is that the AI character doesn’t define ‘aiming’ as ‘just look at it.’ For one, this wouldn’t smoothly transition your character; it would just jump from looking off into the distance to immediately facing its target with no animation or interpolation in between. Also, if your character is, for example, a human holding a gun (and let’s face it, it probably is) then ‘aiming’ really entails pointing the gun at the target. This is at the very least slightly more complicated that just turning, and might even mean engaging your inverse kinematic solver to figure out exactly how one would go about moving hands and wrists and elbows and shoulders and all sorts of other weird anatomy in order to get some arbitrary point (the barrel) on the end of a long stick (the rifle) to aim at something. Point being, aiming at the target won’t usually be an immediate action that you can accomplish, so:

if(!c.weapon.IsAimedAtTarget()) return BehaviorStatus.RUNNING;

We need a second ability to be able to tell when we are finally aiming at the target. Again, the details here aren’t super important, but in my case this more or less just involves checking if the direction of the gun barrel is within some degrees of the target. At this point, if this check fails, then I know that I’ve told my AI to aim its weapon and that it is doing so, but has not yet fully done it, meaning that this isn’t a SUCCESS not a FAILURE, but rather a RUNNING result. This is an important distinction, because if the next step after this “fire your gun” (which is very obviously will be) then you want to make sure you/your gun is completely aimed in the direction it needs to be, lest you start putting holes in the scenery or other AI allies (which might also warrant other checks to make sure you have clear line of sight and so on, but more on that later.) Lastly, of course:

return BehaviorStatus.SUCCESS;

We now know that we A) have a target and 2) are fully aimed at the target. The action “PointGunAtTarget” is SUCCESSful!

Now, I know that was a really long way to explain “write your actions as functions that can return one of three states,” but I’m new to this, so deal with it.

Compounds

OK, now we have the ‘behavior’ parts, but there’s still no ‘tree’ in sight. So it’s time to put them together. How? With more of the same exact things, that’s how. In addition to leaf nodes containing behaviors like the one above, behavior trees also need to connect these with various parent ‘compound’ nodes. The best part about these is that they’re pretty much identical to the leaf behavior nodes; at least in concept. Let’s say we have our PointGunAtTarget action from above and, along with a few others, want to have a more complex action, AttackTarget, which handles more of the entire process:

///pesuedocode
AttackTarget(
  GetTarget;
  FaceTarget;
  PointGunAtTarget;
  CheckAim;
  Fire;
);

This means that to my AI characters, ‘attacking’ means: Face your target, because we can’t (or don’t want to) aim our gun directly behind us since that just looks weird; point your gun, which is just as described above; check your aim to make sure we actually have a good line of sight and not likely to hit walls or other AI allies; and finally, shoot the damn thing. This process is inherently sequential. As the AI, if I can’t face my target or, like in PointGunAtTarget, if I am still in the process of turning to face my target, I don’t want to proceed on to pointing my gun. If I haven’t finished pointing my gun, I don’t want to check my aim. If my aim doesn’t look good, I don’t want to fire. So back to my original rhetorical question: how do we chain these together into a sequence? Well, with a “SequenceNode,” obviously.

Sequences

Compound nodes are just like leaf nodes! These nodes also return SUCCESS, FAILURE, or RUNNING; they just do so dependent on the execution of other nodes. Let’s take a look at a compound node that executes actions in a sequence, since that’s what we’re looking for right now:

public class SequenceNode : Node {
  private Node[] children;
  protected BehaviorStatus Execute(Context c) {
      for(var i = 0; i < children.Length; i++) {
        var status = children[i].Execute(c);
        if(status != SUCCESS) return status;
      }
      return SUCCESS;
  }
}

Pretty straightforward, right? We have a sequence of actions represented by children and in this case would be our GetTarget, FaceTarget, PointGunAtTarget, CheckAim, and Fire behaviors from before. We iterate over these children, executing them all in order, just like we want. However, if any node does not return a SUCCESS, we stop there and return whatever non-SUCCESS state (either RUNNING or FAILURE) that it gave us, meaning that the SequenceNode itself completes with RUNNING|FAILURE, and the rest of the children remain unexecuted in this iteration of the tree. SequenceNode one of the ‘standard’ types of nodes that are in pretty much every behavior tree implementation, along with SelectorNode. Let’s take a look at that one real fast:

public class SelectorNode : Node {
  private Node[] children;
  protected BehaviorStatus Execute(Context c) {
      for(var i = 0; i < children.Length; i++) {
        var status = children[i].Execute(c);
        if(status != FAILURE) return status;
      }
      return FAILURE;
  }
}

This is kind of like the inverse of SequenceNode. Whereas sequences are all about ‘try to do all of these,’ selectors are for when you want to ‘try to do one of these.’ Selectors iterate their children until they find the first one that doesn’t return FAILURE. If a child fails, it just goes on to the next until it runs out. This is useful for when you have a prioritized list of actions that you want to attempt. Like I said, Sequence and Selector nodes are two of the common, basic building block nodes in behavior trees and you’ll likely use them a lot. However, it’s important to remember that since these are such simple constructs, and since they all share a common pattern, you can write your own compound nodes to implement whatever sort of behavioral flow control that make sense for a given AI.

Getting back to the problem at hand, let’s imagine a very simple constructor for this type of node:

public SequenceNode(params Node[] childNodes) {
  this.children = childNodes;
}

If we also imagine that there is the ability to create base ‘behavior’ nodes objects out of functions like PointGunAtTarget, like so:

var PointGunAtTargetNode = new BehaviorNode(PointGunAtTarget);

then we could do something like this:

var tree = new SequenceNode(GetTargetNode, FaceTargetNode, PointGunAtTargetNode, CheckAimNode, FireNode);

And have something that looks a little more like a tree! Just one of the behavior nodes on its own is technically a tree too, of course, but this finally feels more tree-like. Now since this tree is stateless with regard to the individual AI characters (which all keep their state inside of personal Context objects), I only need one copy of it. I can then take this copy and execute over it, probably from within whatever ‘main’ class represents my AI character:

public class MyAI {
  private static Node tree = new SequenceNode(FaceTargetNode, PointGunAtTargetNode, CheckAimNode, FireNode);
  private Context context;

  private void Start() {
    //Populate context with references to weapons, locomotion, character data, or whatever else will be needed in the behaviors.
    context = new Context(...);
  }

  //NOTE: So long as the behavior implementations allow, there's actually no need to iterate the tree *every* frame like I am here.
  private void Update() {
    tree.Execute(context);
  }
}

The AI now ‘thinks’ about what to do every frame, and the behaviors the tree lands on instruct it what to do. Of course, the only thing this AI does is stand in one place and try to fire at a target, but that’s actually a pretty useful thing, particularly when you consider that since the tree is just a node itself, and nodes all share a similar pattern, you can reuse it in more complex behaviors. For instance:

var attack = new SequenceNode(GetTargetNode, FaceTargetNode, PointGunAtTargetNode, CheckAimNode, FireNode);
var move = new SequenceNode(GetDestinationNode, FindPathToDestinationNode, FollowPathNode);
var tree = new SelectorNode(attack, move);

This gives us a new tree; one that first tries to attack the enemy by performing the sequence defined in the attack SequenceNode just like before. However, now if attacking fails (such as when “CheckAim” returns failure because the target is out of range or behind a wall), the SelectorNode continues on to its next option: move toward the enemy. Our AI now tracks down and murders whatever it thinks needs murdering. Good, right? Well, turns out there’s still some problems. Pretty big ones, even. Remember that some of our actions may take a while to fully complete to either SUCCESS or FAILURE, and return RUNNING in the meantime. So let’s think about what that means with a series of iterations over this tree:

  • main ‘tree’ SelectorNode:
    • tries ‘attack’ sequence first
      • GetTarget: SUCCESS
      • FaceTarget: SUCCESS
      • PointGunAtTarget: SUCCESS
      • CheckAim: FAILURE (Uh oh, we are out of range and can’t attack!)
    • ‘attack’ failed, so try ‘move’ next
      • GetDestination: SUCCESS
      • FindPathToDestination: SUCCESS
      • FollowPath: RUNNING

Done! This iteration is now complete, and the AI is on the move. As it is now, in the next iteration, we would try ‘attack’ again first. If the move brought us into a good line of sight with the target, we might succeed and all is well – our AI tried to fire, couldn’t, moved so it could, and fired. Smart little thing. However, it could also go like this: * main ‘tree’ SelectorNode * tries ‘attack’ sequence first * GetTarget: SUCCESS * FaceTarget: SUCCESS * PointGunAtTarget: RUNNING

Done! Earlier this time, too. Looks like our last ‘move’ made the AI’s gun drift off target and it will need to adjust. Since the ‘attack’ sequence didn’t fail this time, so the selector won’t bother moving on to the ‘move’ sequence. This might have some unintentional effects, depending on how the AI behaviors are implemented. With no new move commands issued, what happens? Does the AI need to be reminded to move and stops on its own when there’s no instruction from the tree? In this case, our last two iterations mean that the AI started moving and immediately stopped to check its aim again, which takes time. If this aim also failed because we’re still out of range, it needs to move again. The end result here is a stuttering “step, aim, step, aim, step, aim” loop. Maybe logic outside of the tree keeps the AI moving under its own direction without instructions from the tree? In that case, how does it know when to stop? We don’t have that command in here at all. Even if we did, would we wind up in the same stuttering movement? Well, a new control flow node might help in some cases. One that lets us simultaneously move and aim/attack would be nice here. That won’t always cut it, though. Ultimately, there’s still a key missing piece to behavior trees. In order to prevent the AI from interrupting itself by start from the top of the tree and retrying earlier actions evey time, it needs to be able to resume something it was doing the last time. Specifically, it should have the ability to remember which child in a Selector or Sequence node it ‘left off’ (received a RUNNING response) on and be able to start from that node again on the following iteration.

How to do this (and specifically why I had to rewrite my BT implementation) will have to come another time. Not trying to be dramatic or anything; it’s just that I’ve written enough non-code for one day.

Confession Time

I’ve lied to you. A lot, really. My two implementations of behavior trees are really quite a bit different than the examples I’ve given above. In my first attempt, the statement “compound nodes look just like leaf nodes!” was pretty true, but statements like “don’t worry about this function, it will just get wrapped up into a node” and examples like the SequenceNode class that does just that with its nice interface inheritance and everything were absolutely false. In my more recent implementation, there are discrete node classes and a similar composite pattern shared across leaf and compound nodes, but “compound nodes look just like leaf nodes!” was only technically true and showing the chain of relations between the two would have been arduous and more confusing than helpful. To that end, lots of the examples above are either cherry picked from one or the other implementation or just plain made up on the spot to illustrate the concept more clearly. I may also write some specifics on my first try, what was good, what was bad, and what I changed in my second implementation, but that’s not what this post turned out to be. So instead, lies.

2 Replies to “Behavior Trees Pt. 01”

  1. Hi there just wanted to give you a quick heads up and let you know a few of the pictures aren’t loading correctly. I’m not sure why but I think its a linking issue. I’ve tried it in two different internet browsers and both show the same results.

    1. Thanks for the heads up!
      There aren’t any images in this particular post, though there are some code blocks if those are what’s failing to load for you.

Comments are closed.