how to

Fast links for other parts and tutorials:

If you’re looking for actual code to use, check it out:


In the previous post (Part 1), I presented the base architecture for our Behavior Tree. In this one, there is not much to talk, but a lot to show. I will present some implementations of basic nodes here, and with this, you will have (hopefully) a pretty good idea of how this all works and how to continue on your own.

We will implement here:

  • Composites: Sequence, Priority, MemSequence, MemPriority;
  • Decorators: Inverter;
  • Actions: Wait, ChangeColor, ChangePosition;
  • Conditions: IsMouseOver.

By the end of this post, we will also put a simple behavior tree into action.

It is important to note that, I’m oversimplifying our implementations due to legibility and better understanding of the core features. For example, I would replace the “children” variable in decorators to a “child” variable in a real scenario, because they can only have a single child. More than that, I would create a class for each node category in order to treat the these differences between them. If you are going to implement a BT from scratch with basis in these tutorials, I trust you are going to make the necessary changes. =)

** Remember: all nodes must inherit from BaseNode.

Composites

A composite node can have one or more children. The node is responsible to propagate the tick signal to its children, respecting some order. A composite node also must decide which and when to return the state values of its children, when the value is SUCCESS or FAILURE. Notice that, when a child returns RUNNING or ERROR, the composite node must return the state immediately.

Sequence

The sequence node ticks its children sequentially until one of them returns FAILURE, RUNNING or ERROR. If all children return the success state, the sequence also returns SUCCESS.

var Sequence = function() {
    this.initialize(arguments);
}
Sequence.prototype = new BaseNode();
Sequence.prototype.tick = function(tick) {
    for (var i=0; i<this.children.length; i++) {
        var status = this.children[i]._execute(tick);

        if (status !== SUCCESS) {
            return status;
        }
    }

    return SUCCESS;
}

Priority

The priority node (sometimes called selector) ticks its children sequentially until one of them returns SUCCESS, RUNNING or ERROR. If all children return the failure state, the priority also returns FAILURE.

var Priority = function() {
    this.initialize(arguments);
}
Priority.prototype = new BaseNode();
Priority.prototype.tick = function(tick) {
    for (var i=0; i<this.children.length; i++) {
        var status = this.children[i]._execute(tick);

        if (status !== FAILURE) {
            return status;
        }
    }

    return FAILURE;
}

MemSequence

MemSequence is similar to Sequence node, but when a child returns a RUNNING state, its index is recorded and in the next tick the MemPriority call the child recorded directly, without calling previous children again.

Notice that, this is the first time we use the blackboard inside a node. The MemSequence must save the index of the last running child in the blackboard in order to start from it in the tick function. Also notice that, every time the MemSequence is opened (which means that it was closed), the node resets the “runningChild” to zero.

var MemSequence = function() {
    this.initialize(arguments);
}
MemSequence.prototype = new BaseNode();
MemSequence.prototype.open = function(tick) {
    tick.blackboard.set('runningChild', 0, tick.tree.id, this.id);
}

MemSequence.prototype.tick = function(tick) {
    var child = tick.blackboard.get('runningChild', tick.tree.id, this.id);
    for (var i=child; i<this.children.length; i++) {
        var status = this.children[i]._execute(tick);

        if (status !== SUCCESS) {
            if (status === RUNNING) {
                tick.blackboard.set('runningChild', i, tick.tree.id, this.id);
            }
            return status;
        }
    }

    return SUCCESS;
}

 

MemPriority

MemPriority is similar to Priority node, but when a child returns a  RUNNING state, its index is recorded and in the next tick the, MemPriority  calls the child recorded directly, without calling previous children again.

var MemPriority = function() {
    this.initialize(arguments);
}
MemPriority.prototype = new BaseNode();
MemPriority.prototype.open = function(tick) {
    tick.blackboard.set('runningChild', 0, tick.tree.id, this.id);
}

MemPriority.prototype.tick = function(tick) {
    var child = tick.blackboard.get('runningChild', tick.tree.id, this.id);
    for (var i=child; i<this.children.length; i++) {
        var status = this.children[i]._execute(tick);

        if (status !== FAILURE) {
            if (status === RUNNING) {
                tick.blackboard.set('runningChild', i, tick.tree.id, this.id);
            }
            return status;
        }
    }

    return FAILURE;
}

Decorators

Decorators are special nodes that can have only a single child. The goal of the decorator is to change the behavior of the child by manipulating the returning value or changing its ticking frequency.

Inverter

Like the NOT operator, the inverter decorator negates the result of its child node, i.e., SUCCESS state becomes FAILURE, and FAILURE becomes SUCCESS. Notice that, inverter does not change RUNNING or ERROR states, as described in algorithm below.

var Inverter = function() {
    this.initialize(arguments);
}
Inverter.prototype = new BaseNode();
Inverter.prototype.tick = function(tick) {
    var child = this.children[0];

    if (!child) {
        return ERROR;
    }

    var status = child._execute(tick);

    if (status == SUCCESS)
        status = FAILURE;
    else if (status == FAILURE)
        status = SUCCESS;

    return status;
}

Actions

Action nodes perform computations to change the agent state. The actions implementation depends on the agent type, e.g., the actions of a robot may involve sending motor signals, sending sounds through speakers or turning on lights, while the actions of a NPC may involve executing animations, performing spacial transformations, playing a sound, etc.

Wait

Wait a few seconds. Notice that, in this node, we need to define a parameter in the initialization!

var Wait = function(milliseconds) {
    this.endTime = milliseconds;
    this.initialize();
}
Wait.prototype = new BaseNode();
Wait.prototype.open = function(tick) {
    var startTime = (new Date()).getTime();
    tick.blackboard.set('startTime', startTime, tick.tree.id, this.id);
}

Wait.prototype.tick = function(tick) {
    var currTime = (new Date()).getTime();
    var startTime = tick.blackboard.get('startTime', tick.tree.id, this.id);
    
    if (currTime - startTime > this.endTime) {
        return SUCCESS;
    }
    
    return RUNNING;
}

ChangeColor

Change the color of the target object.

Note here: this is the first time we use the target object. Thus, this node, different of the previous ones, is very coupled to our application. Here, this node will be used in our example below and the target object is a shape of CreateJS.

var ChangeColor = function(color) {
    this.color = color;
    this.initialize()
}
ChangeColor.prototype = new BaseNode();
ChangeColor.prototype.tick = function(tick) {
    tick.target.graphics.clear();
    tick.target.graphics.beginFill(this.color);
    tick.target.graphics.drawRect(-100, -30, 200, 60);

    return SUCCESS;
}

ChangePosition

Choose a random position for our target object.

var ChangePosition = function() {
    this.initialize()
}
ChangePosition.prototype = new BaseNode();
ChangePosition.prototype.tick = function(tick) {
    tick.target.x = Math.floor(Math.random()*800);
    tick.target.y = Math.floor(Math.random()*600);

    return SUCCESS;
}

Conditions

A condition node checks whether a certain condition has been met or not. In order to accomplish this, the node must have a target variable (e.g.: a perception information such as “obstacle distance’” or “other agent visibility”; or an internal variable such as “battery level” or “hungry level”; etc.) and a criteria to base the decision (e.g.: “obstacle distance > 100m?” or “battery power < 10%?”). These nodes return SUCCESS if the condition has been met and FAILURE otherwise. Notice that, conditions do not return RUNNING nor change values of system. Graphically, condition nodes are presented by gray ellipsis, as shown in the image below.

IsMouseOver

Verifies if the mouse is over our target object.

var IsMouseOver = function() {
    this.initialize();
}
IsMouseOver.prototype = new BaseNode();
IsMouseOver.prototype.tick = function(tick) {
    var point = tick.target.globalToLocal(stage.mouseX, stage.mouseY);
    if (tick.target.hitTest(point.x, point.y)) {
        return SUCCESS;
    } else {
        return FAILURE;
    }
}

Example: Jumping Box

So, we have all our nodes. Now put it all together in a file called behaviors.js and copy the code below into a html file:

<html>
  <head>
    <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
    <title>Behavior Tree Example</title>

    <style type="text/css">
      html {margin: 0px; padding: 0px;}
      body {margin: 0px; padding: 0px; text-align: center; }
      canvas {margin: 50px auto; background: #F2F2F2; }
    </style>

    <!-- CREATEJS -->
    <script type="text/javascript" src="http://code.createjs.com/createjs-2013.12.12.min.js"></script>

    <!-- ALL OUR CLASSES HERE -->
    <script type="text/javascript" src="behaviors.js"></script>

    <!-- GAME CODE -->
    <script type="text/javascript">
      // CREATEJS
      var canvas;
      var stage;

      // BEHAVIORS
      var tree;
      var agent;
      var blackboard;

      function start() {
        // CREATEJS
        canvas     = document.getElementById('canvas');
        stage      = new createjs.Stage(canvas);

        // BEHAVIORS
        blackboard = new Blackboard();
        tree       = new BehaviorTree();
        tree.root  = new Priority(
          new Sequence(
            new IsMouseOver(),
            new MemSequence(
              new ChangeColor('red'),
              new Wait(500),
              new ChangePosition(),
              new ChangeColor('blue')
            )
          ),
          new ChangeColor('blue')
        )

        agent = new createjs.Shape();
        agent.graphics.beginFill('blue');
        agent.graphics.drawRect(-100, -30, 200, 60);
        agent.x = 400;
        agent.y = 300;

        stage.addChild(agent);
        stage.update();

        createjs.Ticker.addEventListener('tick', onTick);
      }

      function onTick() {
        tree.tick(agent, blackboard);
        stage.update();
      }
    </script>
  </head>

  <body onload="start();">
    <canvas id="canvas" width="800" height="600">JS not enabled</canvas>
  </body>
</html>

This example presents a blue rect in the screen. When will move the mouse over this rect, it will change to red; then it will wait a half second to change its position, resetting its color to blue again. Check it out:

.

This ends the series of tutorials about Behavior Trees. I hope to hear some feedback from you guys!

Read more

Fast links for other parts and tutorials:

If you’re looking for actual code to use, check it out:


In these days, I’ve being developing a Behavior Tree (BT) library in JavaScript, including the core structures of BTs, a visual editor and a visual debugger. In this post, the first part of two, I will explain my implementation choices of the core structure, which is almost finished in my library, and by the end of this series you will have an example code of fully functional behavior tree with some basic nodes.

*Notice that, you can translate the code here from JavaScript to any language.

Before any code, I’ve defined some objectives (the must-have) of the implementation:

  • Must be easy to connect the tree to a visual debugger (during the tick signal, the debug must know which node is executing);
  • The tree must know the open nodes from last tick (so it can close previous open nodes that weren’t called in the current tick);
  • Must be easy to load and save the tree in a JSON format (this is important because the visual editor will also save and load the tree as a JSON);
  • Nodes must have, at least, a function for events: open, tick, and close. The open function is only called before the tick function and only if the node is closed (if it returned RUNNING the last tick, the node is still open). In the tick function, a node will perform some computation. The close function will be called after the tick function and only if the node returned SUCCESS, FAILURE or ERROR (or if the tree force it);

After several implementations with different design choices, I came up with a fairly decent architecture for BTs, which can be seem in the figure below. This architecture will be explained in detail during this post, so don’t worry to understand it all right now.

bt_architecture

I’ve decided that, the tree and the nodes will not store a reference to a target object (e.g., an NPC instance or a monster instance) nor variables related to the execution of the tree or of the node (e.g., a list of opened nodes or the last child to return a RUNNING state), they will only store structural information (e.g, reference to the children) – Suppose you have 1000 NPCs in a game that share the same behaviors (e.g., villagers or pack of evil goblins), with this design choice, a single instance of the tree will control all the thousand agents.

Now, the execution information must be stored somewhere else. For this, we will create a Blackboard structure, which will serve to us as individual memory to our agents, thus, each one of the 1000 NPCs in the example above will have a different Blackboard instance.

In this architecture, I don’t see the needed to have multiparenting (explained here). The multiparenting implementation seems too complex and the outcome seems too low (not sure, but I think large trees will not consume that much memory with this architecture; later I will test if this is true and benchmark the multiparenting feature).

Constants and Helpers

Starting the code. First of all, we have to define some constants to represent the state values. I’m using the states SUCCESS, FAILURE, RUNNING, and ERROR, as described here.

// NODE STATES ================================================================
var SUCCESS   = 1;
var FAILURE   = 2;
var RUNNING   = 3;
var ERROR     = 4;

// GLOBAL & UTILITY FUNCTIONS =================================================
var createUUID = function() {
    var s = [];
    var hexDigits = "0123456789abcdef";
    for (var i = 0; i < 36; i++) {
        s[i] = hexDigits.substr(Math.floor(Math.random() * 0x10), 1);
    }
    // bits 12-15 of the time_hi_and_version field to 0010
    s[14] = "4";

    // bits 6-7 of the clock_seq_hi_and_reserved to 01
    s[19] = hexDigits.substr((s[19] & 0x3) | 0x8, 1);

    s[8] = s[13] = s[18] = s[23] = "-";

    var uuid = s.join("");
    return uuid;
}

Notice that I also included the function createUUID . This function will be used to create unique IDs for our objects (consult this if you want to know more about how UUID works).

Blackboard

So, the Blackboard will be the memory structure for our agents, which will be used by the tree to access the execution variables. The Blackboard must differentiate global information, accessed by any node in the tree, by the agent, or even other trees (yeah, with this implementation, you may use different trees to control the same agent using the same memory); per tree information, accessed only by the nodes in the same tree or the tree instance itself (e.g, a list of open nodes from last tick); and per node per tree information, accessed only by the node that wrote the information (e.g., a flag telling if the node is open or not).

var Blackboard = function() {
    this.initialize();
}
Blackboard.prototype.initialize = function() {
    this._baseMemory = {}; // used to store global information
    this._treeMemory = {}; // used to store tree and node information
}

Blackboard.prototype._getTreeMemory = function(treeScope) {
    if (!this._treeMemory[treeScope]) {
        this._treeMemory[treeScope] = {
            'nodeMemory'         : {},
            'openNodes'          : [],
        };
    }
    return this._treeMemory[treeScope];
};

Blackboard.prototype._getNodeMemory = function(treeMemory, nodeScope) {
    var memory = treeMemory['nodeMemory'];
    if (!memory[nodeScope]) {
        memory[nodeScope] = {};
    }

    return memory[nodeScope];
};

Blackboard.prototype._getMemory = function(treeScope, nodeScope) {
    var memory = this._baseMemory;

    if (treeScope) {
        memory = this._getTreeMemory(treeScope);

        if (nodeScope) {
            memory = this._getNodeMemory(memory, nodeScope);
        }
    }

    return memory;
};

Blackboard.prototype.set = function(key, value, treeScope, nodeScope) {
    var memory = this._getMemory(treeScope, nodeScope);
    memory[key] = value;
};

Blackboard.prototype.get = function(key, treeScope, nodeScope) {
    var memory = this._getMemory(treeScope, nodeScope);
    return memory[key];
};

The Blackboard class only defines two public methods: set  and get . Notice that, both receive the parameters treeScope and nodeScope, these parameters will be used to define the memory context (global if both aren’t provided, per tree if only treeScope is provided, or per node per tree is both are provided).

Both,  set  and get , are pretty simple, only get the contextual memory object and store/retrieve values to/from it. The _getMemory  will decide which memory will be used, depending on parameters.

Also notice that, the _getTreeMemory  and _getNodeMemory  methods will create a new object inside the tree memory if it doesn’t exist. The object used as memory is a common Object in JavaScript, but in other languages you can use dictionaries (also called hash tables or hash maps).

Tick

Nodes do not need to have a reference to their parents, only to their immediate children, in the same way, the tree will only know the root node. In order to tell nodes in which tree their are, and make references of the target and the blackboard visible to them, We will use a Tick object. This object will be created by the tree, will store the references, and will be propagated to the nodes during the tick.

var Tick = function() {
    this.initialize();
}

Tick.prototype.initialize = function() {
    this.tree       = null;
    this.openNodes  = [];
    this.nodeCount  = 0;
    this.debug      = null;
    this.target     = null;
    this.blackboard = null;
}

Tick.prototype.enterNode = function(node) {
    this.nodeCount++;
    this.openNodes.push(node);
    // call debug here
}

Tick.prototype.openNode = function(node) {
    // call debug here
}

Tick.prototype.tickNode = function(node) {
    // call debug here
}

Tick.prototype.closeNode = function(node) {
    // call debug here
    this.openNodes.pop();
}

Tick.prototype.exitNode = function(node) {
    // call debug here
}

The Tick is also used to:

  • Store the list of current open nodes and count the number of nodes ticked during the traversal;
  • Send the activation signals to debug (as commented in the code);

The tick have some methods that will be called by the node objects. See below the BaseNode  definition, to know more.

BehaviorTree

The tree must keep a list of open nodes of the last tick, in order to close them if another branch breaks the execution (e.g., when a priority branch returns RUNNING.). After each tick, the tree must close all open nodes that weren’t executed.

var BehaviorTree = function() {
    this.initialize();
}

BehaviorTree.prototype.initialize = function() {
    this.id          = createUUID();
    this.root        = null;
}

BehaviorTree.prototype.tick = function(target, blackboard) {
    /* CREATE A TICK OBJECT */
    var tick = new Tick();
    tick.target     = target;
    tick.blackboard = blackboard;
    tick.tree       = this;

    /* TICK NODE */
    this.root._execute(tick);

    /* CLOSE NODES FROM LAST TICK, IF NEEDED */
    var lastOpenNodes = blackboard.get('openNodes', this.id);
    var currOpenNodes = tick.openNodes.slice(0);

    // does not close if it is still open in this tick
    var start = 0;
    for (var i=0; i<Math.min(lastOpenNodes.length, currOpenNodes.length); i++) {
        start = i+1;
        if (lastOpenNodes[i] !== currOpenNodes[i]) {
            break;
        } 
    }

    // close the nodes
    for (var i=lastOpenNodes.length-1; i>=start; i--) {
        lastOpenNodes[i]._close(tick);
    }

    /* POPULATE BLACKBOARD */
    blackboard.set('openNodes', currOpenNodes, this.id);
    blackboard.set('nodeCount', tick.nodeCount, this.id);
};

The tree definition is also pretty simple, it only have one method, called tick. The tick method receives a reference to the target object and another to the target blackboard as parameter. With these references, it creates a Tick object and propagate it to the root node, and just waits for the root to return the status. After propagating the tick signal, the tree closes all open nodes from the last tick that weren’t called in the current one (the last open nodes list is stored in the blackboard while the current open node list is created by Tick during the propagation). Finally, the tree saves the list of open nodes in the blackboard.

BaseNode

All nodes will inherit from a BaseNode . This class will implement a execution method that will call all “interface” methods:

  • Enter: called every time a node is executed;
  • Open: called only when the node is opened (when a node returns RUNNING, it will keep opened until it returns other value or the tree forces the closing);
  • Tick: the real implementation of the node (e.g., the composite nodes will call their children in this method);
  • Close: called when a node return SUCCESS, FAILURE or ERROR, or when the tree forces the node to close;
  • Exit: called every time at the end of the node execution.

The user can create new nodes by inheriting the BaseNode and overriding the interface methods.

var BaseNode = function() {
    this.initialize();
}

BaseNode.prototype.initialize = function(children) {
    this.id          = createUUID();

    this.children = [];
    if (children) {
        for (var i=0; i<children.length; i++) {
            this.children.push(children[i]);
        }
    }
}

BaseNode.prototype._execute = function(tick) {
    /* ENTER */
    this._enter(tick);

    /* OPEN */
    if (!tick.blackboard.get('isOpen', tick.tree.id, this.id)) {
        this._open(tick);
    }

    /* TICK */
    var status = this._tick(tick);

    /* CLOSE */
    if (status !== RUNNING) {
        this._close(tick);
    }

    /* EXIT */
    this._exit(tick);

    return status;
}

// Wrapper functions
BaseNode.prototype._enter = function(tick) {
    tick.enterNode(this);
    this.enter(tick);
}
BaseNode.prototype._open  = function(tick) {
    tick.openNode(this);
    tick.blackboard.set('isOpen', true, tick.tree.id, this.id);
    this.open(tick);
}
BaseNode.prototype._tick  = function(tick) {
    tick.tickNode(this);
    return this.tick(tick);
}
BaseNode.prototype._close = function(tick) {
    tick.closeNode(this);
    tick.blackboard.set('isOpen', false, tick.tree.id, this.id);
    this.close(tick);
}
BaseNode.prototype._exit  = function(tick) {
    tick.exitNode(this);
    this.exit(tick);
}

// Override these to create nodes
BaseNode.prototype.enter = function(tick) {}
BaseNode.prototype.open  = function(tick) {}
BaseNode.prototype.tick  = function(tick) {}
BaseNode.prototype.close = function(tick) {}
BaseNode.prototype.exit  = function(tick) {}

Notice that, there is a wrapper method for all interface methods, they are used to update the isOpen  flag in the blackboard and call the Tick methods.

To be continued…

In the next post, I will show the implementation of some basic nodes and examples of use of this tree.

Read more