Finite State Machine vs Behaviour Tree, A True Story

I needed behaviour trees because I wanted to manage the complexity of the units AI in Warrior Defense which originally used finite state machines (FSM). FSMs are great because they are so simple and intuitive. When they get big, however, they become so complicated. It got to a point where I’m afraid to change the configuration of the FSM because the working AI easily breaks. In other words, it’s brittle. I don’t like that. I still have lots of features to add later on that deal with unit interactions.

A part of Defender unit FSM. Looks like spaghetti, yum!
Just a part of Defender unit FSM. It looks like spaghetti, yum!

I decided to make my own behaviour tree tool because I can’t find a decent one in the Asset Store. I’m one of those lazy guys that buy a lot of tools. I’ve tried RAIN, which is free. I hated it. The changes to the tree did not reflect in the game right away. It just frustrated me. I’ve bought React while it was on sale but I didn’t like how it worked. Adding actions to it was clunky. It uses functions and runs it in a coroutine. It doesn’t support parameters, as well.

Thus, the journey to developing my own behaviour tree tool began. I called it Banana Tree. I completed the core behaviour tree framework (nodes, sequence, decorators) some months ago. But this is pure code. There’s no visual editor. I’ve made AI behaviours that are hardcoded in classes. Production wise, this is not very efficient. AI behaviours changes a lot. Something that changes a lot should not be code, they should be data. I thought that I should probably make a data driven behaviour tree tool. Looking at the FSM above, I think I’ll be making a lot of code anyway using the current framework.

So I did make a data driven behaviour tree with its own visual editor. I just finished the bare essentials that could create a working behaviour out of data. I’ve successfully ported the complex behaviour above to its Banana Tree equivalent. The high level behaviour looks like this:

High level behaviour nodes
High level behaviour nodes. It looks very neat.

Don’t be fooled, though, because it looks like this underneath those parent nodes:

Worms under the stone
Worms under the stone

What I’d like to point out is that it’s still complicated, but it’s now more manageable. I can complete one branch of the behaviour and forget about it once it works and begin working on another one. My brain is not strained so much to the amount of visual objects because I can just fold the node and stop thinking about the things beneath it. It’s so unlike FSMs where you can’t help but see the states and their wiring.

Using behaviour trees feels more like programming. Each node feels like a function. Working with an FSM feels like wiring. It is static as “wire one event to one transition state”. I now understand what articles about behaviour trees mean when they say FSMs are constricting (I didn’t get it before). Behaviour trees don’t have wires. They execute on how the tree is structured. What to do next is not explicitly stated in the behaviour tree. It can select a lot of possible action branches to execute. In FSMs, you have to explicitly specify what state it should go next. This could be limiting because there may be a lot of possible states to go to. It’s possible to make it work like a behaviour tree but you’ll need more work and maintenance to the FSM. You’ll most probably end up with an FSM like the one I showed.

I can’t say that behaviour trees are better, either. They also have a major disadvantage: steep learning curve. You have to think like a compiler when working with BTs. You have to know what its elements mean like Sequence, Selector, Parallel, Decorator, etc. Like every skilled programmers say, “Know your tools. Know where it’s best used.” Behaviour trees has been proven to work on complex behaviours, but I probably can’t give this to a non programmer and let him/her figure it out on his/her own. FSMs are much more easier to understand. They are far more intuitive, too. FSMs are probably the way to go if you only need to model simple behaviours.

Banana Tree Success!

I think Banana Tree is complete, for now. Software projects can never be completed. Little UI elements and responses are still missing. No copy-paste yet, no undo-redo. But for its purpose and intended use, it does it very well. I was able to replicate the behaviour of ground and flying crawlers using the tool. By doing this, I also uncovered and fixed some major implementation holes.

Ground enemy behaviour using Banana Tree
Ground enemy behaviour using Banana Tree

The biggest stumbling block for me is when I found out that Unity can’t serialize a nested field that has depth of seven or more. It’s so disappointing. My node tree data was serialized like this:

[Serializable]
public class NodeData {

    [SerializeField]
    private string label;

    ... // more data

    // this is a nested serialized field
    // Unity can't handle this if it's too deep
    [SerializeField]
    private List<NodeData> children;

}

public class BananaTreeBehaviour : MonoBehaviour {

    // I thought I'll never have problems with this
    [SerializeField]
    private NodeData rootNodeData;

    ...

}

I went to the forums and found out that others are complaining about it, too. I found this out last Monday night. I was so excited that I could finally see Banana Tree in action in an actual game, then this happened. Tuesday morning was spent on fixing it. It’s not an easy fix, either. Fortunately, my habits worked for me. Layers of indirection made refactoring easier.

My fix is to have a master list of all node data. I added an extra property named masterId which works as a primary key for the node. Child nodes are then kept as a list of integers where each entry represents the masterId to the actual node instance. I made a custom container class to manage the list of all nodes.

[Serializable]
public class NodeData {

    [SerializeField]
    private int masterId;

    [SerializeField]
    private string label;

    ... // more data

    // no longer nested to circumvent the limitation
    [SerializeField]
    private List<int> children;

}

[Serializable]
public class NodeDataMaster {

    // all nodes of the behaviour tree are collected here
    [SerializeField]
    private List<NodeData> nodeList;

    /**
     * Searches for the node with the specified master id
     */
    public NodeData FindByMasterId(int masterId) {
        for(int i = 0; i < nodeList.Count; ++i) {
            if(nodeList[i].MasterId == masterId) {
                return nodeList[i];
            }
        }

        Assertion.Assert(false, "Can't find node with master id = " + masterId);
        return null;
    }

    public NodeData AddNode() {
        ...
    }

    public void RemoveNode() {
        ...
    }

    ...
}

public class BananaTreeBehaviour : MonoBehaviour {

    // all node manipulation now goes through here
    [SerializeField]
    private NodeDataMaster dataMaster;

    ...

}

I designed the tool to be flexible and extensible without editing any of its source code. This is done through reflection. Custom actions should be implemented as classes that inherits a certain class. By doing so, the editor identifies these classes and adds UI controls for it. Thus, replicating the existing behaviour means porting a lot of function calls to their action class equivalents. My action browser looks like this:

Custom actions
Custom actions

Custom action classes look like this:

    [ActionGroup("Game.Crawler")]
    public class CrawlerHasBlocker : CrawlerAction {

        #region implemented abstract members of BntNodeAdapter
        public override BntResult Start() {
            return Evaluate();
        }

        public override BntResult Update() {
            return Evaluate();
        }

        public override BntResult FixedUpdate() {
            return Evaluate();
        }
        #endregion

        private BntResult Evaluate() {
            if(GetCrawler().HasBlocker()) {
                return BntResult.SUCCESS;
            }

            return BntResult.FAILED;
        }

    }

    [ActionGroup("Game.Path")]
    public class GetTargetPathPosition : BntCachedComponentAction<PathCrawler> {

        [UseVariable]
        public BntVector3 Result {get; set;}

        #region implemented abstract members of BntNodeAdapter
        public override BntResult Start() {
            Result.Value = GetCachedComponent().GetTargetPathPosition();
            return BntResult.SUCCESS;
        }

        public override BntResult Update() {
            return BntResult.SUCCESS;
        }

        public override BntResult FixedUpdate() {
            return BntResult.SUCCESS;
        }
        #endregion

    }

It sounds silly that a single function call need to be promoted to a class to be used in an editor. But I like this better. I like the idea that you can extend the functionality of an editor by just adding classes. This adheres to the Open-Close principle of software engineering.

Working Behaviour Tree From Editor

A lot has happened to Banana Tree and I’m quite happy with its current state. More variable types are now supported in the node inspector. I prioritized the variables that are used in existing actions so I could test them as soon as possible.

While thinking about how action nodes should pass variable values to other nodes, I realized that it’s not effective for nodes to have references of other nodes. Playmaker has this concept of “FSM level” variables. These variables can be referenced by any states in the FSM. Though initially not planned, I think I needed this type of feature in Banana Tree as well for cross node variable communication. I need to have some kind of behaviour-level variables that can be referenced by any action nodes in the behaviour. I’m surprised that the implementation is really not that hard.

Node level and behaviour level variables
I have this action class “TestVariableAction” which is used to test all supported variables. On the right are the behaviour level variables which can be referenced by action level variables.

I use custom classes to add variables to an action node. The editor identifies these properties and renders the appropriate UI controls. Here’s the implementation of TestVariableAction:

    [ActionGroup("Tests")]
    public class TestVariableAction : BntAction {

        /**
         * Constructor
         */
        public TestVariableAction(string name) : base(name) {
        }

        public BntString StringVariable {get; set;}

        public BntString StringTest2 {get; set;}

        public BntGameObject GameObjectTest2 {get; set;}

        public BntFloat FloatVar {get; set;}

        public BntFloat FloatVar2 {get; set;}

        public BntVector3 PositionVar {get; set;}

        public BntVector3 PositionVar2 {get; set;}

        public BntTransform TargetVar {get; set;}

        public BntTransform TargetVar2 {get; set;}

        public BntBool BoolVar {get; set;}

        public BntBool BoolVar2 {get; set;}

        #region implemented abstract members of BntNodeAdapter
        public override BntResult Start() {
            return BntResult.SUCCESS;
        }

        public override BntResult Update() {
            return BntResult.SUCCESS;
        }

        public override BntResult FixedUpdate() {
            return BntResult.SUCCESS;
        }
        #endregion

    }

If you want to do something like this, I suggest you use custom classes instead of directly using string, float, bool, GameObject, etc. Custom class variables adds indirection so you can add some intermediary features to your variables like referencing another variable when its value is requested or add some more information to the variable. It’s also much easier to assign values to it on game runtime since the class variables can be implemented as serialized and you’ll just have to assign it directly to the action node instance properties through reflection.

With this in place, I was able to instantiate a minimal behaviour tree at runtime from serialized data. What it does is it moves an actor back and forth in two positions, Home and Destination.

Minimal working behaviour... Yey!
Minimal working behaviour… Yey!

The editor is almost complete. When I say complete, it means it must be verified which further means that it should be used in a working game. Tomorrow, I’ll replicate the existing enemy behaviour in Warrior Defense using this editor. It’s not that easy because I’ll have to implement lots of action classes. I’m sure there will be some hiccups but I’ll find a way.

Experimental Node Inspector

Today, I’ve been working on the node inspector of a BananaTree node. The inspector displays information about the selected node. It’s most important use, though, is to set variables of a node. Every property in an action that has a public getter and setter would be considered as a variable. This information could be retrieved through reflection. For now, I’m playing with string properties and I’m quite happy with the result. Variables are automatically added to the node data based from the action node class (properties) if they are not yet found. Its value can also be set through the inspector.

Node inspector, woot!
Node inspector, woot!

I stumbled upon a very useful discovery. Serialized generic classes can be used in Unity with a little help. We know that Unity can’t serialize Dictionary. I need something that works like a Dictionary for the named variables but stores the serializable items in a List. Let’s say we have the following class that stores a single string variable:

    [Serializable]
    public class StringVariable {

        [SerializeField]
        private string name;

        [SerializeField]
        private string stringValue;

        /**
         * Default constructor
         */
        public StringVariable() {
        }

        /**
         * Constructor with specified name and value
         */
        public StringVariable(string name, string value) {
            this.name = name;
            this.stringValue = value;
        }

        public string Name {
            get {
                return name;
            }
            set {
                name = value;
            }
        }

        public string Value {
            get {
                return this.stringValue;
            }
            set {
                this.stringValue = value;
            }
        }

    }

A list of StringVariable instances can be specified as:

public class SomeComponent : MonoBehaviour {
    [Serializable]
    private List<StringVariable> stringVariables;
}

I don’t like this because I’ll have to bake functions like GetStringVar(string name) into the component. I don’t just have string variables. I’ll have int, float, GameObject, Vector3 later on. GetIntVar(), GetFloatVar(), GetVector3Var(), …? No way. This is where I tried to make a generic container class that stores items in a list but provides Dictionary like methods. The first step is to provide an interface to mark classes that it has something that returns a name.

    public interface Named {

        /**
         * Returns a name
         */
        string Name {get;}

    }

StringVariable now implements this interface:

    public class StringVariable : Named {
        ...
    }

This is my generic container that maintains items in a list:

    [Serializable]
    public class VariableMap<T> where T : Named {

        [SerializeField]
        private List<T> itemList;

        /**
         * Constructor
         */
        public VariableMap() {
        }

        /**
         * Adds an item
         */
        public void Add(T item) {
            this.itemList.Add(item);
        }

        /**
         * Removes an item
         */
        public void Remove(T item) {
            this.itemList.Remove(item);
        }

        /**
         * Returns the item with the specified name
         */
        public T Get(string name) {
            int count = itemList.Count;
            for(int i = 0; i < count; ++i) {
                if(itemList[i].Name.Equals(name)) {
                    return itemList[i];
                }
            }

            // not found
            return default(T);
        }

        /**
         * Returns whether or not the map contains an item with the specified name
         */
        public bool Contains(string name) {
            int count = itemList.Count;
            for(int i = 0; i < count; ++i) {
                if(itemList[i].Name.Equals(name)) {
                    return true;
                }
            }

            return false;
        }

    }

Everything’s good so far but I had a problem. This does not work (it does not display in Unity inspector):

public class SomeComponent : MonoBehaviour {
    [Serializable]
    private VariableMap<StringVariable> stringVariables;
}

I tried a little magic:

    [Serializable]
    public class StringVariableMap : VariableMap<StringVariable> {
    }

Now this works in Unity:

public class SomeComponent : MonoBehaviour {
    [Serializable]
    private StringVariableMap stringVariables;
}
Serialized generic class!
Serialized generic class!

This is so cool! This has countless possibilities. Its weakness, though, is it implies that I’ll have classes like IntVariableMap, FloatVariableMap, GameObjectVariableMap, etc. But this is a small price to pay. My main goal is to put the code of the custom container in one class and I have done that.

If you have a better idea, please do tell me.

Action Browser Window

Look, the editor now has an action browser and can add actions into the tree!

1-21-2014
Action Browser Window!

This thing took a long time to create. I wanted actions to be added into the editor automatically after compilation. It uses reflection to look for those classes. I also studied attributes and how to access them so I could add grouping attributes to the action class like the one in the image. Attributes are so cool! This is my ActionGroup attribute:

using System;

namespace BananaTree {
    /**
     * An attribute used for grouping actions
     */
    [AttributeUsage(AttributeTargets.Class)]
    public class ActionGroup : Attribute {

        private string name;

        /**
         * Constructor
         */
        public ActionGroup(string name) {
            this.name = name;
        }

        public string Name {
            get {
                return name;
            }
        }

    }
}

This class can be used like this:

    [ActionGroup("Bnt.Movement")]
    public class BntMoveToByDuration : BntAction {
        ...
    }

Unity does not have a built in “selection list” GUI where an item is highlighted when it is selected. That took a while as well. My implementation used GUI event handling and GUIStyle.

Completing the action browser made me excited. I thought it would take me more days to complete this. Now it’s done, I’m moving closer to having a data driven AI. My next task is to serialize the tree data into a Unity object. I’ve decided to use Unity objects instead of text files like XML or JSON so I could easily implement features like assigning Unity objects (GameObject, component, prefab) as parameters.

Colorful Nodes, Bugs, and Complexities

I just finished coloring the different nodes. This has proven to be useful. At first glance, I could see right away what type of node it is. The color could also provide meaningful description to the node when a different label would be provided (which I plan to implement later).

It looks like DNA!
It looks like DNA!

I’ve ran into some complexities that should be implemented into the editor. First, a decorator can only have one child. There was no problem when adding a child using the right-click menu. But I forgot that dragging a node to a decorator is also adding a child. I’ve fixed it using an observer pattern.

Second, when a node is moved up/down along its sequence, the data counterpart should be updated as well. I use a different tree for the rendering part and data part. I just can’t have one object that contains both the rendering data and behaviour tree data. I made a promise to myself that the tree control should be decoupled as much as possible so I could easily extract it for my future editors. The consequence is that I have to make a system to sync the two tree-like data and keep them consistent. I also added an assertion that the two data should be consistent whenever there are updates to the tree.

Child Nodes and Reflection

My Behaviour Tree editor is getting interesting. I can now add child Composite or Decorator nodes. The nodes are identified through reflection. Here’s a simple utility code to populate a list with all the subclasses of the specified type:

        public static void PopulateSubclassList(List<Type> typeList, Type parentType) {
            Type[] types = Assembly.GetAssembly(parentType).GetTypes();
            foreach(Type type in types) {
                if(type.IsSubclassOf(parentType)) {
                    typeList.Add(type);
                }
            }
        }

This is what I used to collect all Composite nodes and Decorator nodes. Now I can do something like this:

Right click, then poof!
Right click, then poof!

I could clearly see my next tasks from here.

  • Color coding of different types of nodes
  • A separate Action nodes window where all available action classes would be collected
  • XML Serialization
  • Delete node
  • An inspector panel where a node can be renamed and variables can be added

I don’t have some kind of design document for this project so I just go along and see what works. Now that I think about it, I don’t create such documents with my other projects, either. Someone would probably scold me for this.