/ Unity

Unity Behavior Trees pt. 1

For our game currently in development, working title "Godlands", we need a system for doing AI that's easy to use and will be easy to extend as we want to increase the complexity of our characters. There are various ways to manage character behaviors, some simple and some more complex. I've worked with state machines in previous games, notably Boss Rush where the boss's AI logic was done as a state machine. For a while now I've wanting to try out behavior trees, so that's what I've been working on for Godlands.

The article that I've found does the best job introducing and explaining how behavior trees work is this Gamasutra blog post. It's written by Chris Simpson who does the AI programming for Project Zomboid, which uses behavior trees for their AI characters. Since behavior trees are a big topic and I don't think I could do a good job explaining them, I'll instead focus on the methods I've employed in implementing them in Unity and the challenges I am facing in learning to use behavior trees.

There already exists a plugin for doing behavior trees in Unity, and if we were an existing studio trying to make a game for production purposes $65 would a reasonable price to pay for such a useful tool. However, we're students and have no guarantee of making any money off this project, so keeping our expenses to a minimum would be ideal. Personally I have an interest in making game development middleware, so writing our own library for doing behavior trees is a good middle ground, and it could result in a useful tool that can drive revenue.

Basic C# Behavior Tree

The most naive implementation of any tree is an object for each node with a reference to its children. For the behavior tree, nodes only need two methods: Init() and Tick(). The TreeNode base class that I use is below:

public abstract class TreeNode
{
	public abstract void Init( Hashtable data );
	public abstract NodeStatus Tick();
}

public enum NodeStatus
{
	SUCCESS,
	FAILURE,
	RUNNING
}

One thing you might notice about this base class is that there are no reference to the parent node. This is because the tree is always ticked from top-to-bottom, so a node never has to traverse up to its parent. When you tick a node, it does what it needs to and then returns up to its parent, meaning the execution stack saves us the trouble of having to manually iterate. If our trees were sufficiently massive we would run the risk of a stack overflow, but I don't see that being the case in a project of this size (or any size, really).

For dealing with children we define two abstract node types:

public abstract class Decorator : TreeNode
{
	public TreeNode child;

	public override void Init( Hashtable data )
	{
		child.Init( data );
	}
}

public abstract class Compositor : TreeNode
{
	public TreeNode[] children;
	
	public override void Init( Hashtable data )
	{
		foreach ( TreeNode child in children )
		{
			child.Init( data );
		}
	}
}

From here, any nodes we want to define will inherit from Decorator, Compositor, or TreeNode directly, in the case of leaf nodes.

To drive the tree we create a MonoBehaviour that holds a reference to the root node and ticks it once each frame:

public class AIController : MonoBehaviour
{
	public TreeNode root;

	void Update()
	{
		root.Tick();
	}
}

To build a tree, we simply construct it node-by-node and then hand the root to the AIController:

TreeNode root = new RepeatUntilFail();
TreeNode sequence = root.child = new Sequence();
sequence.children = new TreeNode[] {
	new FindNearestResource(),
	new MoveToDestination(),
	new CollectAdjacentResources() };

GetComponent<AIController>().root = root;

This is a simplified version of a test behavior for some of the characters in our game. The result is a behavior tree that has the character walk to each resource on the map and pick it up until there are none left.

Problems and Concerns

At this point there are two major problems: Performance and usability.

If you're familiar with the performance profile of traversing a linked list, you'll know that it is a very slow action to perform because it requires jumping around memory with no regard for cache coherency. This holds true for a tree structure such as this since functionally it behaves like a linked list. We could improve on this by holding the nodes in a list to guarantee contiguity, but it still won't have the performance profile of iterating over a flat list. Fortunately, save for the most egregious cases, script performance doesn't seem to be the major bottleneck in Unity projects (we tend to run into more issues with graphics and physics performance).

That leaves usability as the bigger problem to be addressed. As you can see from the above example, constructing a behavior tree means building it node-by-node in code. This is easy enough when the tree is trivially small, but anything complex enough to be useful becomes incredibly tedious and error-prone to construct by hand.

Having to construct the tree in code is also inflexible compared to being able to serialize it out as an asset. Ideally you'd construct the tree and turn it into an asset, and then you'd be able to use the inspector to select which behavior is used for which actor in the level. This would make it easy for designers to be able create new actors or swap swap the behaviors for existing actors without having to touch code. In theory you could setup MonoBehaviours that construct the tree and that would be a rough substitute, but it doesn't fit with the usual Unity idioms and still has the problem of error-prone tree construction.

The ideal solution is to use ScriptableObject to make the behavior trees serialize as assets, and then create a custom editor to simplify the creation of behavior assets. This is ultimately the direction I've begun to work in, but that has proven to be a very complicated topic that I'll have to save for another post.

In Conclusion

A naive behavior tree implementation is deceptively easy to put together, but leaves a lot to be desired. We have the potential for minor, incremental improvement (like creating components for constructing the trees), but to address the fundamental issue we'll need to build an editor and serialize the behaviors as assets.

David LeGare

David is a game developer and systems programmer. He likes cats, he tolerates dogs, and he often remembers to dress himself before leaving the house.

Read More