Implementing A Behavior Tree – Part 2

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!

14 Comments, RSS

  1. Oliver Zhou April 22, 2015 @ 10:11

    Hi, Author

    It’s a great series to read.

    The question is what’s the biggest advantage to use Behavior3js rather than code by hand.

    Since Javascript is very easy yet powerful script language, it should not be too difficult to write such logic by hand.

    • Renato Pereira April 22, 2015 @ 10:28

      Hi, Oliver, thanks for commenting.

      The question is, why would you want to rewrite a BT library that does the same as Behavior3?

      It is not quite easy to implement a behavior tree. Take a look around the internet, there is a lot of very different implementations around there and in general, most of them have inconsistencies. For example, some represent a behavior by a single function – this representation can’t model Wait nodes, for example, because the node must have an internal state to know is it must reset the counter or not. Others start ticking the tree in the node the last returned the RUNNING state, which is very wrong, because you lose the capacity to interrupt low-priority behaviors in order to execute high-priority ones.

      Behavior3JS is consistent, tested, open source, data driven, reviewed by community and based on a formal description that proves the relation of this architecture to general controllers. Moreover, you can also use the open and online visual editor =]

      • Oliver Zhou April 27, 2015 @ 06:55

        Hi Renato,

        Thanks for your reply. I would say Behavior3JS is great library. I would like to use in my next project if I can.

      • Oliver Zhou April 27, 2015 @ 06:58

        I like the visual editor as well. The debugger is definitely a great plus.
        And I like to the use of AngularJS

    • Renato Pereira April 22, 2015 @ 10:30

      Oh, and you may want to take a look at this post [1], where I explain the development process of my Ludum Dare game that I used b3js. I can say that is pretty easy to use, I only miss a debugger (that is in list to be implemented).

      [1] http://guineashots.com/2015/04/20/democracy-my-game-for-ld32/

  2. Deahun May 6, 2015 @ 05:06

    Thank you for your great article.

    I’m sorry that I’m not good at speaking English.

    I have a question.

    Should behavior tree check to start from root node per tick ?

    I think It is not a very efficient way. But If I record the last active node and in the next tick I start to check from the recorded node not root, definitely it should skip to check the previous nodes of the recorded node.
    I’m very confuse.

    If there is a node which you want to check before all in specific situation, how would you do that?
    Or best way is designing to prevent this from happening.

    • Renato Pereira May 6, 2015 @ 11:06

      Hi, Deahun,

      The tree MUST start the tick always from the root, either with a running node or not. This is necessary because must have priority over others, being able to interrupt the execution of low priority nodes. For example, if a robot is following some wall, the FOLLOW_WALL node is returning RUNNING, but if the robot finds a hole in front of you, it must interrupt the following behavior and do something to avoid the hole.

      If you want to always start from the last running node, you can simply use MemSequence and MemPriority instead of Sequence and Priority nodes.

      For further reference, you can check my BT library (http://behavior3js.guineashots.com/)

      • Deahun May 6, 2015 @ 23:42

        Thank you for quick response.

        I have one more question.

        I’ve made monster AI with HFSM in MMORPG.
        So I handle each event in proper state. But BT doesn’t have state.
        How does BT handle a event properly?

        Receive event and record at agent and if some node which using the information processes it, doesn’t it?

        Is it obvious question? If so, I am ashamed. ^^;;;

        • Deahun May 7, 2015 @ 00:15

          For example, If a monster has been attacked where process it.
          BT node or something event processor?

        • Renato Pereira May 14, 2015 @ 00:53

          Hey Deahun,

          This isn’t a trivial question and people solve that in different ways.

          My approach is: 1) define a “perception” structure in the agent (e.g., the perception could have flags like “visible hostile enemies”, “damage taken”, etc.); 2) you call the behavior tree tick function, and the nodes will use the perception data; 3) at the end of the tick, you clean up the perception data. So during the execution of your game, the events populate the agent perception structure (and not the nodes).

  3. Mitch December 27, 2015 @ 07:54

    Renato , you pretty much are my hero today.
    Thanks for all of your tutorials , the time and effort you’ve put into them. They’re thorough and clear , just what I needed.

    • Renato Pereira December 28, 2015 @ 14:02

      Glad I could help! Cheers 🙂

  4. GuangzeFu March 21, 2016 @ 05:36

    HI! Wisdom stranger!
    Sorry about my poor English.
    I’m totally agree with your B3 among so many implements about it I have seen. And I’m trying to write a game AI base on your advice.
    But I really don’t understand one Decorator node ,Limiter, it’s codes.
    I don’t know wheather this node is wrote by you. It’s so odd to understand:

    open()
    {
    blackborad:set(“loop”, 0)
    }

    tick()
    {
    loop = self.loop
    if loop < self.max_loop:
    status = self.child._excute(tick)

    — please notice here!!!
    if status == OK or status == FAIL:
    blackbord:set("loop", loop + 1)

    return status
    }

    why it add loop count only when its child returns OK or FAIL however the BASENODE will close it ?

    if you close it, it will open when next time enter it, means the loop count will be 0 again!

    please reply me here or email me.

    thx a lot.

  5. GuangzeFu March 21, 2016 @ 10:58

    Hello, me again.

    And I found another problem in your B3JS and B3PY and I think that would be your BUG.

    The problem is about the node’s close stage call_back. You can recreate the bug in follwing situation:

    There’re three nodes marked as (1), (2), (3)

    (1)sequence node;
    (2)RUNNING action node;
    (3)RUNNING action node, too;

    first tick, (1), (2), and (2) is running, open_nodes : {(1), (2)}.
    second tick, (1), (2), and (2) is finished and return SUCCESS. means, (2) close itself after excutation. And then (3) will execute because of (1)is sequence node. open_nodes : {(1), (3)}.

    Back to the function “tick” of BTree:
    ———————————————————————–
    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=start; i–) {
    lastOpenNodes[i]._close(tick); ///////////////////////CLOSE (2) AGAIN HERE!////////
    }
    ———————————————————————–
    (2) will be closed twice which should be closed once(once in its tick that finish RUNNING).

    waiting for your answer. Please inform me here or email me.

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

*