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.