/ Unity

Unity Behavior Trees pt. 2

In the last article I introduced the basic implementation of behavior trees, and I brought up the problems it poses when developing for Unity. This time I'm going to focus on Unity asset serialization and how it makes behavior trees really difficult.

Asset Serialization in Unity

As I brought up last time, one of the problems with the initial implementation of the Behavior trees is that they need to be constructed dynamically at runtime. This not only makes behavior tree construction error prone, it also makes it more difficult to assign behaviors to our characters in the scene. The idiomatic way of doing this in Unity would be to drag a behavior onto the AIController component, just like you would drag an animator onto an AnimationController. We can solve both of these problems by treating behavior trees as assets and creating a visual editor to construct and manipulate them.

To create an asset file out of the data in a script object, Unity needs some way of saving the data in that object to a file. This goes for both prefabs and custom assets, since Unity treats them in just about the same way. When writing a component, you extend MonoBehaviour and when you place that component on the object in the scene Unity can automatically start saving the values you set on the object. For example:

public class MoveController : MonoBehaviour
{
	public float moveSpeed;
}

When you add MoveController to an object and change the value of moveSpeed, Unity saves that value with the scene (or prefab) and loads that same value when you load the scene next time. This is accomplished by saving the value to the scene's .unity file (or the prefab's .prefab file). This process is called "serialization".

With MonoBehaviour we can create prefabs, but for the behavior tree what we want is more akin to an asset like an animation controller. For this Unity provides the ScriptableObject base class which can be used to create generic asset files. Actually creating the asset file requires a bit of editor scripting which we'll go over when we discuss writing an editor for our behavior trees, so for now we'll focus on the behavior tree asset itself.

Creating the Behavior Tree Asset

Previously we had an AIController component that looked like this:

public class AIController : MonoBehaviour
{
	TreeNode root;

	// some methods
}

To allow allow the user to simply drag the behavior tree asset over in the inspector, we change this to:

public class AIController : MonoBehaviour
{
	public BehaviorTree tree;

	// some methods
}

Then we need to create the BehaviorTree class, which will hold the root node of our tree:

public class BehaviorTree : ScriptableObject
{
	TreeNode root;

	// some methods
} 

With this we're ready to start tackling the problem of asset serialization.

Serialization Limits

For day-to-day things, Unity makes it easy to serialize script data into asset files. When extending MonoBehaviour or ScriptableObject public members are serialized automatically, and private members with the [SerializeField] attribute are treated the same way. For custom classes like TreeNode you can get this behavior by adding the [System.Serializable] attribute to the whole class.

When writing members like float moveSpeed and bool canUseAbility Unity's default serialization works perfectly and you can completely ignore the implementation details, but it's when you start to run up against the serializer's limitations that things become difficult. This blog post describes the strengths and limitations of Unity's serialization system. There are two details that are pertinent to dealing with our behavior trees: Custom classes behave like structs (so multiple references to the same object turn into multiple copies of that object), and no support for polymorphism in custom classes.

The first limitation isn't so hard to overcome. It means that we can't serialize the tree structure directly since Unity won'f follow the references between nodes, but we can put the nodes in a list and construct the tree structure through other means. The second is a far bigger issue. If you recall from the first post, we define TreeNode as an abstract class with a public interface, with different behaviors overriding the base class's methods. This poses a problem for us, because when we deserialize the behavior tree's data (meaning load the asset back into the game from a file) we need to construct the nodes with correct derived type, rather than the base type (which is how the serializer sees them).

Serializing a Tree Structure

Because our tree is constructed of a custom TreeNode class, Unity doesn't follow the references between nodes. This is problematic because our tree is constructed entirely of references between nodes, this becomes a problem. This means that with the initial version of BehaviorTree:

public class BehaviorTree : ScriptableObject
{
	TreeNode root;

	// ...
} 

the resulting asset won't have anything in it, because Unity doesn't see any members that it can serialize. To get around this, we have to change the way we represent the behavior tree in memory (at least while unity is trying to serialize our asset):

public class BehaviorTree : ScriptableObject
{
	TreeNode root;

	[System.Serializable]
	class SerializedNode
	{
		public List<int> children;
	}

	public List<SerializedNode> serializableTree;

	// ...
} 

We added two new things here: A serializable class SerializedNode that has a list of ints that will represent the indices of the node's children, and and List<> of SerializedNodes that will represent the serialized version of our tree.

The next step is to convert the tree in memory into the serializable form. This consists of traversing the the tree, putting all the nodes in the list, and patching up the indices of the children for each of the nodes. There are two broad options for implementing this: Having BehaviorTree manually traverse the tree and add the nodes to the list, or having the nodes define a method to serialize themselves and passing them a reference to the serialized list. In this case I went with the latter as it has the advantage of allowing decorators, compositors, and leaves to handle serialization differently since the number of children they can have all differ.

To do this we add another method to TreeNode:

public abstract int Serialize( List<SerializedNode> serializeList );

We pass in the list of serialized nodes so each node can add itself, and then we return the index of that node in the list so that parent nodes can add their children to the to its list of children. Here's the Serialize() method for compositor nodes as an example:

public override int Serialize( List<SerializedNode> serializeList )
{
	int index = serializeList.Count;

	serializeList.Add( new SerializedNode()
	{
		children = new List<int>()
	} );

	foreach ( TreeNode child in children )
	{
		serializeList[index].children.Add( child.Serialize( serializeList ) );
	}

	return index;
}

The first thing the node does is add itself to to the serialized list, ensuring that a node always appears before its children. This helps when deserializing the asset because we know the root node is always the first node in the serialized list, and can reconstruct the tree from there. The node then calls Serialize() on each of its children, which add themselves to the list and return their index, which the node uses to construct its list of children. The node finally returns its own index so that its parent can do the same.

Handling Polymorphism

So far we have a method for serializing the tree's structure, but we're still missing the types of the nodes. To see where this problem manifests itself, let's look at how you do custom serialization in Unity.

Unity provides the ISerializationCallbackReceiver interface which defines the methods OnBeforeSerialize() and OnAfterDeserialize(). Before Unity serializes out your class it calls OnBeforeSerialize() which gives you a chance to set your data up so that it's serialized out in the way you want. In this case, that means taking the behavior tree structure and putting it into the SerializedNode list so that it's in a form Unity can handle. After loading the data back from the asset file Unity calls OnAfterDeserialize() so that you have a chance to take that data and put it back in a usable format. In our case, when OnAfterDerserialize() has been called the data for the tree will have been put back in the SerializedNode list, at which point we have to reconstruct the tree from that data.

So far, the only data in SerializableTree is a list of nodes and the indices of the children of each node, but there's nothing to tell us what type each node should be. This proves to be a serious problem because Unity doesn't provide a good way of handling polymorphism in custom classes, to Unity everything looks like the base class.

As a disclaimer, I haven't yet found a good solution to this one. Unity handles polymorphism correctly when deriving from Unity types (MonoBehaviour and ScriptableObject), and it tracks references correctly in this case which means we wouldn't have to put the tree into a list, but each object needs to be saved as its own asset. That means that each node would have to be its own asset file which would quickly become unmanageable, making the custom serialization route the better option for now.

My current solution for tracking node types is to use reflection to get the node's actual type as a string, and then use that string to construct that node with the correct type later. It's an ugly solution and it doesn't work on all platforms (Windows 8 phones, at least, doesn't support reflection), but it works until I can find a more robust solution.

Here's a look at BehaviorTree's OnBeforeSerialize() and OnAfterDeserialize():

public void OnBeforeSerialize()
{
	_serializedNodes = new List<SerializedNode>(); // remove previously serialized version
	if ( root != null )
	{
		root.Serialize( _serializedNodes );
	}
}

public void OnAfterDeserialize()
{
	root = ( _serializedNodes.Count > 0 ? DeserializeNode( 0 ) : null );
}

TreeNode DeserializeNode( int index )
{
	List<TreeNode> children = new List<TreeNode>();
	foreach ( int childIndex in _serializedNodes[index].children )
	{
		children.Add( DeserializeNode( childIndex ) );
	}

	// use reflection to create node of correct type
	TreeNode node = (TreeNode)Activator.CreateInstance( Type.GetType( _serializedNodes[index].typename ) );
	
	node.SetChildren( children );
	return node;
}

I added a typename member to the SerializedNode type, and we can use GetType().AssemblyQualifiedName get the name of the type as a string when serializing out the tree. When deserializing we can use Type.GetType() to create a Type object from that string, and then Activator.CreateInstance() to construct an object of that type.

Problems

On top of the above issues with just getting the tree structure itself serialized out, there are other problems that still haven't been addressed. The biggest issue is that we have to store the same information for all nodes, which means we can't provide any configuration data for specific nodes.

For example, we may have a Delay decorator node that simply returns the Running status until a certain amount of time has passed. It would be great of we could specify different values for different instances of the nodes but that requires us to serialize extra data for that node type, something we don't have a way of supporting. I can imagine a few contortions we could go through to get this to work, but the fact that its so difficult to do something that should be simple tells me that there's a fundamental problem with the implementation that needs to be fixed.

Conclusion

What we have so far is a proof of concept but doesn't work as a final implementation. We haven't gotten to building an editor for the behavior trees and we're already seeing major problems that need to be addressed. In future articles I'll go over the basics of creating a visual editor, but things aren't going to be able to progress much further until we can address the more fundamental issues with the behavior tree system. For Godlands at least our design has changed such that we no longer rely so heavily on AI, so this has become a less pressing issue for us.

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