Implementing A Behavior Tree – Part 1

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.

11 Comments, RSS

  1. Austin October 22, 2014 @ 21:47

    Great article. Hopefully part 2 will be coming soon!

    • Renato Pereira October 23, 2014 @ 19:45

      Hi, there! I’m writing it right now. Probably it comes out tomorrow!

  2. Francisco November 28, 2014 @ 10:46

    Olá, muito obrigado Renato pelo seu contributo, tanto para a comunidade de investigação como para o enriquecimento do conhecimento dos aficionados neste tipo de tema. (estou a escrever em português pois deduzi que pelo Nome fosse de nacionalidade Portuguesa ou Brasileira.
    O artigo está muito bom e estou a tentar fazer um sistema semelhante para usar numa plataforma de desenvolvimento de jogos (GameMaker), neste momento a portabilidade precisa de algumas alterações porque a programação nesta plataforma não é OO e usa um linguagem diferente de javascript (GML).
    A minha duvida reside no conceito de open/closed node…. e no porquê da necessidade da sua existência. outra pergunta associa-se á duvida na necessidade de criar uma instancia nova da:

    var currOpenNodes = tick.openNodes.slice(0);

    Não seria possivel usar a “tick.openNodes” directamente?!

    Agora em inglês:

    Thank you very much for your contribution, great article targeting the community and the fans of artificial inteligence in general.
    I’m trying to create a similar system for a game making platform GameMaker and as similiar as the language may be to JS it is still not OO so a lot of changes need to be done. My two questions are about the necessity of using a replica of the close_nodes array:

    var currOpenNodes = tick.openNodes.slice(0);

    and also the concept behind close/open nodes if first place… why do you need then? why are they important? will it enhance the system in performance?

    Thank for your attention!

    • Renato Pereira December 3, 2014 @ 10:35

      Hi, Francisco, I’m Brazilian =). I’m writing in English in order to more people understand us.

      About the copy of “tick.openNodes”, it really seems unnecessary, probably a remnant of an old implementation. I’m going to edit the post.

      The open/close is necessary because some nodes may need to know when they are opened or closed. For example, the wait node must set a ‘startTime’ variable when it is opened (to do that, the node must be closed), the same is true for the MaxTime decorator and other nodes. So, we need to know if a node is opened or not, and to close properly the nodes during the execution.

      I made myself clear?

  3. Marco Ippolito January 28, 2015 @ 05:28

    Hi Renato,
    thank you very much for sharing your excellent Behaviour3JS

    A question: what are the reasons that lead you to choose JS as the implementation language, instead of, for example, python?

    Marco

    • Renato Pereira February 15, 2015 @ 10:26

      Hi, Marco, that is because I’m using JS to make games. I already have an implementation of B3 in Python for my Ph.D. experiments. I hope to release the python version soon.

  4. Jim March 8, 2015 @ 05:46

    Nice work! I can’t wait to see how this continues to progress…and take a stab at playing with some of the work you’ve done.

  5. Benzi Ahamed June 6, 2015 @ 12:54

    Very nice set of articles you’ve got here – been reading them and it is really appreciated!

    I’ve been trying to understand the following statement:
    “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.”

    I’m not able to understand why we need to maintain the list of opened nodes in the previous and current tick, compare them and close out some of them?

    What I can see from the call structure, every time the tree ticks, it always initiates the node’s tick call at the root. So each tree tick call traverses from the root node to the current running node of interest. Along the way, the Tick’s openNodes stack will get populated as well – which means for every tree tick call, the Tick.openNodes will be like a call stack of all the nodes visited (immaterial of them having been marked isOpen from a previous tick); and since the only way the tree Tick function exists is returning recursively back, the moment the call exits the Tick.openNodes will be a list of all visited nodes. This happens every call.

    So my question is, why do we need to maintain Tick.openNodes at all? If every consecutive call to tree tick maintains individual node’s isOpen state in the blackboard, why do we need to have Tick.openNodes stack? I’m not able to figure that out.

    • Benzi Ahamed June 6, 2015 @ 14:46

      I think I found it out. I didn’t quite understand what the Priority/Selection node actually does. (I got insight reading about Spore’s BT implementation here: http://chrishecker.com/My_liner_notes_for_spore/Spore_Behavior_Tree_Docs )

      So since the Priority node allows behaviour subtrees with higher priority to execute, a subsequent tick call will see changes in the Ticks.openNodes list.

      To explain via some pseudocode: I made a tree for a simple animal that has the following behaviour:
      If in danger, flee. Fleeing takes one tick to perform
      If hungry eat food. Eating food takes 3 ticks.
      If neither, stay idle

      Since you can be alerted to danger when you are eating food, the eat food leaf behaviour node will not get run in the next tree tick (and will cause changes in the openNode list between two tick calls).

      Pseudocode implementation and sample debug output:

      let flee =
      FleeBehaviour(
      PrintAction(action: “FLEE”)
      )

      let eat =
      EatBehaviour(
      PrintAction(action: “EAT”, duration: 3)
      )

      let idle = PrintAction(action: “IDLE”)

      tree.root =
      Priority(
      flee,
      eat,
      idle
      )

      eat.hungry = false
      flee.inDanger = false

      // idle – not hungry, not in danger
      tree.tick(agent, blackboard)
      tree.tick(agent, blackboard)

      // become hungry, eat food
      eat.hungry = true
      tree.tick(agent, blackboard)
      tree.tick(agent, blackboard)

      // iterrupted by being in danger
      flee.inDanger = true
      tree.tick(agent, blackboard)
      tree.tick(agent, blackboard)

      // no longer in danger
      // start eating food all over again
      flee.inDanger = false
      tree.tick(agent, blackboard)

      ========= OUTPUTS ==========
      EatBehaviour hungry = false
      —————————
      FleeBehaviour inDanger = false
      —————————
      .Priority.execute()
      ..FleeBehaviour.execute()
      ..EatBehaviour.execute()
      ..PrintAction.execute()
      IDLE-1
      —————————
      .Priority.execute()
      ..FleeBehaviour.execute()
      ..EatBehaviour.execute()
      ..PrintAction.execute()
      IDLE-1
      —————————
      EatBehaviour hungry = true
      —————————
      .Priority.execute()
      ..FleeBehaviour.execute()
      ..EatBehaviour.execute()
      …PrintAction.execute()
      EAT-3
      —————————
      .Priority.execute()
      ..FleeBehaviour.execute()
      ..EatBehaviour.execute()
      …PrintAction.execute()
      EAT-2
      —————————
      FleeBehaviour inDanger = true
      —————————
      .Priority.execute()
      ..FleeBehaviour.execute()
      …PrintAction.execute()
      FLEE-1
      —————————
      .Priority.execute()
      ..FleeBehaviour.execute()
      …PrintAction.execute()
      FLEE-1
      —————————
      FleeBehaviour inDanger = false
      —————————
      .Priority.execute()
      ..FleeBehaviour.execute()
      ..EatBehaviour.execute()
      …PrintAction.execute()
      EAT-3
      —————————

      • Renato Pereira June 8, 2015 @ 11:56

        Hi, Benzi,

        It is necessary to maintain a list of opened nodes because:

        – nodes must know when they are open because some of them have initialization code that is only executed in the “open” callback;
        – if high-priority nodes interrupt the execution of low-priority nodes (as you found out), the low-priority ones must be closed (so it can be reopen next time);
        – the open states are stored in blackboard for each node, as you said, but is a lot more expensive to run through the whole blackboard to find which nodes are open.

  6. […] are Behavior Trees? An Introduction to Behavior Trees Implementing a Behavior Tree Behavior Trees for AI – How They Work Second Generation Behavior Trees Behavior Trees Overview […]

Your email address will not be published. Required fields are marked *

*