How to implement a Behavior Tree (preferably in Unity 3D)

Question

I have a state machine I want to implement as a behavior tree. I now have an understanding of how they work but I can't seem to find a full implementation of one. I have implemented a simple one using a plug-in called Behavior Machine but the problem I have with it is I feel like it limits me just as it did when I used it for making my FSM until I implemented my own FSM that is when I had the privilege of using my own functions to trigger my own state transitions and optimize it so that it doesn't use a lot of resources.

The other problem I have is it is difficult to implement my own nodes and control which part executes (optimization). Any idea where I can find a good tutorial on how I can do this, preferably with Unity and in C# or Java. Or where I can find a good library with proper documentation because the one I found on Git-hub or other sites are buggy or just some classes with no documentation. Your help will be greatly appreciated.

So basically, what I want to do is implement my own Behavior Tree. This way I think I can have better control on how it executes so that it can run on mobile devices smoothly.

Answer 1

There actually aren't a lot of full-blown behavior tree implementations available. There are a good amount of theoretical "behavior tree by example" or just "this is a behavior tree" documents out there. I'll put a few here, but won't really expand on them much because I'm assuming that you've read them and don't know where to start:

• Wikipedia article
• In-depth Gamasutra article
• Fluent API implementation with theory and example code
• libGDX behavior tree implementation
• Basic Android learn-by-example

The last two will probably be more like what you are looking for. I kind of like the last one for basic design, but it doesn't address some of the inherent flaws in behavior trees, like real-time reaction and state management. The next to last one is a full-fledged implementation with a very good wiki on how to design them. If you have what you were looking for, you can stop reading here.

If I still have your attention, then you're probably going to set down the path of rolling your own behavior tree, and those references from before are excellent resources to learn everything you need to know to do just that. On an implementation level, it's pretty important to realize that behavior trees are just a specific realization of a component system, where the behaviors are the components that can be swapped around and ordered to represent the conditional logic that you want you AI to perform. As such, when you design a behavior tree from the ground up, you start by designing a treed component manager with a specific interface to a generic behavior.

What is a treed component manager? It's a term I just made up, but it fits. When you design a component-based system, you generally loop through component slots and execute each component sequentially. In this case, you want the execution of the components to be determined based on the outcome of previous components, which can be (and usually is) represented by a tree of logic that you traverse. The design of the tree itself is relegated to some configuration outside of the code.

Well, then what do I mean by a "specific interface to a generic behavior?" This, once again, goes back to the component idea. When you have components, you don't know exactly what they do (by design!). You need to expose an interface to the most generic behavior (usually done through pure abstraction) and then have your component manager call that completely generic function that basically just says, "Do your thing."

If you read the documents I linked before, you'll see that most often these behaviors have one of three functions. First, they could be a composite behavior that has one to many children and dictate the flow of the tree. They could be a decorator with one child that modifies the outcome of its child in some way before passing that result up the tree. And finally, it could be an action that actually does something -- either setting a state (by writing to a blackboard of some sort), or causing the entity to do something in the game. From these building blocks, you create arbitrarily complex conditional logic chains. In the end, that's all a behavior tree is -- a really complex (and modular) if-then-else series.

Answer 2

For those coming across this thread, I recommend a look at this implementation:

https://github.com/eelstork/BehaviorTrees/blob/master/cs/src/Status.cs

This is a short (<100loc) implementation of stateless behavior trees. Sequences and selectors are implemented via overloading && and ||.

Then a BT would look something like this:

Status Patrol()
=> (playerInSight && Shoot(player)) 
|| (underFire && TakeCover())
|| Guard(doorWay);

This approach is more useful if you're going to code the BTs. For visual scripting how your BT transpiles to C# doesn't really matter (well, it does, and a stateless implementation is still attractive for performance; but the fastest C# conversion might eschew operator overloading and just use if-elses).