Author: Ken George

Steam store page is now live! Which I guess means this is technically announced now.

So that’s good.

Hey, company logo and stuff! This means I’m a professional now and you can’t convince me otherwise.

Credit to VitalZigns.com for the excellent work.

Alright, carrying on from last time.; let’s talk about what I did the first time and why it was bad and what I did the second time and why (I hope) it’s at least a little less bad.

Old and busted

Here’s an example of what my behavior trees used to look like in that first implementation I kept mentioning:

protected BehaviorStatus MainMovement(Context c) {
  return Subtree(c,
      Try()
          .To(If(IsUnderFire, Try()
              .To(InOrder()
                  .Then(PickNearestCover)
                  .Then(MoveTowardDestination)
                  .Then(TakeCover)
                  .Done())
              .Or(InOrder()
                  .Then(GetDown)
                  .Done())
              .Done()))
          .Or(InOrder()
              .First(HasCover)
              .Then(AccrueSafety)
              .Then(Try()
                  .To(If(IsOutOfAmmo, Reload))
                  .To(If(FeelsSafe, MoveUp))
                  .Or(If(IsSafeToLook, PeekOverCover))
                  .OrElse(If(IsSafeToStay, TakeCover)))
              .Done())
          .Or(InOrder()
              .Then(MoveUp)
              .Done()
          )
          .OrElse(InOrder()
              .Then(GetDown)
              .Done()
          )
  );
}

Couple obvious things to note here. First, the goal at this point was to make the tree easy for me to understand and update so I could iterate more quickly. To that end I’m using a bunch of fluent builder classes to facilitate the organization of nodes into a coherent tree. Try().To(...).Or(...) represents a Selector builder, where the AI tries each of the actions until a SUCCESS, and InOrder().First(...).Then(...) is my Sequence node builder, creating a list of steps to be done in order. I’m being inconsistent with how I use these builders in some spots, but it still more or less reads the way I wanted it to. Second, you’ll notice some “If” statements in there. What are these? Well, I found myself frequently wanting to use something like the following in my tree:

Try()
  .To(IsOutOfAmmo)
  .Then(Reload)

This little two-child Selector is just a check to make sure we reload when necessary. The first method is what I like to call “query behavior”; it doesn’t do anything, it just returns SUCCESS or FAILURE based on some predicate. In this case, it returns SUCCESS when the AI’s weapon is out of ammo and essentially ‘gates’ the call to the Reload method. The If node is just a small wrapper around this common Selector node that cleans up my tree syntax.

Now, insted of a Selector/If/Whatever, I could have made the Reload function itself ccheck internally to make sure ammo levels are low before it reloads (and FAIL otherwise), but I wanted to keep the action free from the precondition in case I wanted to use it elsewhere. What if the AI wasn’t out of ammo, but was low on ammo and had a moment where it had nothing else to do? This way I could have two ammo check preconditions instead of two action implementations, which lends itself to much more flexible tree composition.

So what’s broken here? Well, regardless of my numerous builders, it turned out pretty awkward to write. There’s a lot of parens and nesting and different function names to keep track of. It also didn’t follow a good composite pattern and required things like that pesky “Subtree” call at the top in order to make this tree into a node useable in another tree. And while those two things are annoying, the main issue is that the implementations of the control nodes looked like this:

public static Func<Context, BehaviorStatus> Sequence(params Func<Context, BehaviorStatus>[] funcs) {
  return c => {
    foreach(var child in funcs) {
        var status = Process(child, c);
        if(status != BehaviorStatus.SUCCESS) return status;
    }

    return BehaviorStatus.SUCCESS;
  };
}

So when I made a Sequence node, I wasn’t actually making a ‘node’ at all, just a function! This wasn’t an accident, I actually wanted it like this, but that was obviously before I realized that it would cause me some trouble. Specifically, it’s really annoying to debug these. You can still hit breakpoints inside the functions but your debugger winds up giving you a giant stacktrace of anonymous method calls that makes it pretty impossible to tell how you got to that function; paritculaly if you reuse that function in multiple places in the tree.

Now, it’s also kind of hard to add state to these, and I did already mention that we want some state along the lines of “what node left off RUNNING last time I was here?” While this is an annoyance, I don’t think it’s as much of a problem as I first thought when I initally set about my redesign. Speaking of…

New hotness luke-warmness

Alright, we all love a good refactor/redesign. Too much so usually, but in this case I don’t feel too bad about spending the time on it. You alredy saw a “before,” so here’s the “after”:

 public static BehaviorNode<SubsystemContext> MakeTree() {
  return InParallel(
      //Assess
      InOrder(
          Do(EvaluateFire),
          Do(AtDestination),
          Not(IsUnderFire),
          Do(AccrueSafety)
      ),

      //MainMovement
      Try("to move",
          If(IsUnderFire, Try(
              InOrder("to escape fire",
                  PickNearestCover,
                  MoveTowardDestination,
                  Hunker
              ),
              InOrder("to fall back",
                //I don't know, run away somehow, I haven't bothered yet...
              )
          )),
          InOrder("to stay in cover",
              Do(HasCover),
              Do(AccrueSafety),
              Try(
                  If(FeelsSafe, MoveUp),
                  If(IsSafeToLook, Crouch),
                  If(IsSafeToStay, Hunker)
              )
          ),
          InOrder(
              Do(MoveUp)
          )
      ),
      Do(FireOnTarget)
  );
}

Let’s look at what’s not different here first. InOrder and Try are still here and still mean the same thing, I’m still using If as a shorthand for a two-child Selector, and I’m still using some fluent names/patterns to make the tree ‘read’ like a plan. “In order to escape fire, pick nearest cover, move toward dstination, hunker down” tells me the goal the AI wants to accomplish at this point as well as how it should go about accomplishing it.

Now for what’s different. First, I removed a lot of cruft by relying less on actual builder methods and more on some plain ol’ helper functions with a bunch of convenient overloads. An optional string argument lets me label subsections both for clarity when reading/writing the code and for debugging purposes that I’ll go over later. There’s also a couple new nodes. I’m not going to go over them indetail since I feel like the last post was the place for covering basics, but I’ll summarize just so we’re on the same page:

• InParallel(...): This node is the solution I hinted at last time in regards to doing multiple things at once. It’s a very simple control flow node that just runs all of its children. It doesn’t stop early for a SUCCESS or a FAILURE or even a RUNNING; it always runs all of them. What it returns as its own return value is really up to you. I use it here as the top level node to ensure the AI is always doing all of its “primary” actions.
• Not(...): I’ll be you can guess what this one does! That’s right, SUCCESS becomes FAILURE and vice versa. Just a little tool to improve node reuse.

Now there’s also a Do(...) call that keeps cropping up, This isn’t actually a behavior tree thing, it’s an artifact of my implementation and a necessary bit of glue to get the builder functions to work correctly. Builder functions like InOrder can either accept a list of nodes, or a list of functions, which are then just converted to nodes behind the scenes (again, just to keep things clean). For obvious reasons you can’t mix and match these arguments, so if one of the arguments is a node, the rest need to be, and Do does this just that: wrap a function into a node. So, this:

InOrder(
    Do(EvaluateFire),
    Do(AtDestination),
    Not(IsUnderFire),
    Do(AccrueSafety)
)

and this:

InOrder(
    EvaluateFire,
    AtDestination,
    IsNotUnderFire,
    AccrueSafety
)

are completely equivalent. I prefer the latter format, but it just happens that I had an IsUnderFire query behavior and didn’t want to write an inverted version, so I just created a Not node from it. This meant that EvaluateFire, AtDestination, and AccrueSafety all needed to be wrapped as well. I’ve gotten a little far afield here, so let’s get back to the actual implementation.

Real nodes

Instead of my nodes being pure functions, they are now actual first class objects and follow a composite pattern by all having a common interface:

public interface BehaviorNode<in Ctx>
{
    string name { get; }
    bool resumes { get; }
    BehaviorStatus Execute(Ctx c);
    BehaviorNode<Ctx>[] children { get; }
    bool Done(BehaviorStatus lastStatus);
}

The interface is for a generic context since every project I use this tree in will likely have very different AI and therefore very different requirements for what kind of context I want to pass around. Later on I also enforce an interface on the context itself, but not just yet.

A very simple implementation of this interface is the leaf behavior nodes that are constructed from my AI’s behavior functions.

public class FuncNode<Ctx> : BehaviorNode<Ctx>
{
    public string name { get; set; }
    public bool resumes { get { return false; } }
    public BehaviorNode<Ctx>[] children { get { return null; } }

    public bool Done(BehaviorStatus lastStatus) {
        return false;
    }

    private readonly Func<Ctx, BehaviorStatus> func;

    public FuncNode(Func<Ctx, BehaviorStatus> operation) : this(operation.Method.Name, operation) { }

    private FuncNode(string name, Func<Ctx, BehaviorStatus> operation) {
        if(operation == null) throw new InvalidOperationException();
        func = operation;
        this.name = name;
    }

    public BehaviorStatus Execute(Ctx c) {
        return func(c);
    }
}

Pretty straightforward. To make a node you just call a constructor with a function that represents what the node does when it executes. As you might expect, flow nodes like selectors and sequences are also implementations of this interface but with a predefined execution function and a constructor that accepts their children. On top of these constructors sit a bunch of my builder functions, like:

public static BehaviorNode<Ctx> InOrder(string name, params BehaviorNode<Ctx>[] nodes) {
    return new SequenceNode<Ctx>(name, true, nodes);
}

//Note: the extra 'true' arg here is for the node's "resume" property and allows
//  me to create sequence nodes that do NOT resume their last RUNNING child, which
//  I found occasionally useful.

And that’s pretty much it! There’s a bunch of overloads to the builders just to clean things up, but I’ll spare those boring details. End result is that

Alright, so now I’ve covered how I build the nodes and trees, but I still haven’t talked about how to fix that pesky last-RUNNING-node problem, or how to make trees easier to debug. There’s even some as-yet-unmentioned topics like reading a tree from a file and updating at runtime. Oh, and how to execute the damn thing. It may look an awful lot like execution is as simple as rootNode.Execute(myContext); (and it very well can be), but I went a slightly different direction with mine. My morning coffee is gone now, though, which means I’m done rambling for today.

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.

A website seems like something a company should have. I am pretending to have a company. So now there is a website. I’m sorry.