Javascript

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

CreateJS is a collection of 4 libraries: EaselJS, PreloadJS, SoundJS and TweenJS. EaselJS provides tools to work with the HTML5 canvas; PreloadJS helps you to load the application assets; SoundJS to work with all kind of sounds; and finally, TweenJS provides interpolation functions for easing effects. Together, they allow you to create graphical and interactive applications in an easy and fast manner.

The thing is, the CreateJS suite does not focus on game development, thus, it lacks of important structures and algorithms that helps you to develop games. creatine logo

Having this in mind, I’m developing Creatine, which the first version was published today. Creatine aims to provide all algorithms and structures present in games today and that are not implemented on the CreateJS suite.

Take a look at some examples above, use the following code as base:

<!DOCTYPE html>
<html>
<head>

<script src="http://code.createjs.com/createjs-2013.12.12.min.js"></script>
<script src="creatine-0.1.min.js"></script>

<script>
    var canvas   = null;
    var stage    = null;
    var director = null;

    function init() {
        // code here

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

    // update stage every tick
    function onTick() {
        stage.update();
    }
</script>
</head>
<body onLoad="init();">

<canvas id="canvas" width="600" height="300">alternate content</canvas>

</body>
</html>

 

Creating some Random Scenes

Let’s create some random scenes using Creatine. First you need to create the base objects:

function init() {
    canvas   = document.getElementById('canvas');
    stage    = new createjs.Stage(canvas);
    director = new creatine.Director(stage);
    
    director.replace(newScene());
    
    createjs.Ticker.addEventListener('tick', onTick);
}

Together with the base object, we create a new scene and add it to director at line 6, and registered 2 events at lines 8 and 9. The line 6 uses the function newScene(), let’s define it:

function getRandomColor() {
    var letters = '0123456789ABCDEF'.split('');
    var color = '#';
    for (var i = 0; i < 6; i++ ) {
        color += letters[Math.round(Math.random() * 15)];
    }
    return color;
}

function createScene() {
    var scene = new creatine.Scene();

    var background = new createjs.Shape();
    background.graphics.beginFill(getRandomColor());
    background.graphics.drawRect(0, 0, canvas.width, canvas.height);
    scene.addChild(background);

    return scene;
}

The createScene function create a new empty scene and add a background with a random color. Now, when the user click on the stage let’s change the scene. Put this on init:

stage.on('stagemousedown', onClick);

And create the function onClick:

function onClick() {
    director.replace(createScene());
}

Done! Now check it out the result:

 Changing Scenes with Effects

To put some effect on the scene transition, just change the onClick function:

director.replace(createScene(), new creatine.transitions.MoveOut(creatine.LEFT));

Resulting on:

Learn More

To see more examples, check it out the official repository: https://github.com/renatopp/creatine

To know more about creatine, take a look at the official page: http://guineashots.com/creatine/

Read more

jscramble logo

I was looking for what HTML5 game developers do to protect their source codes. Coincidentally, Emanuale Feronato made post last week about JScrambler, which seems to be the state-of-the-art of free tools in protection for  Javascript codes.

Protecting your code is important for several reasons. Javascript is an interpreted client-side language, which means that the browser of the final user will read the code and execute it to run the game, and this same code can be accessed by the user simply looking in the page source code.

Now, suppose that your code is neither minified or obfuscated. In this case, the final user will see the exactly the lines you wrote. With this, he can: copy and modify all components of your game with the minimum effort and re-distributed as a completely new one; hack your code to submit scores without even playing your game; among other undesirable things.

Notice that, as Javascript runs in client-side, there is no real way to avoid the user to see your code and to stop him to try to decode it. But, you can make your code as harder as possible to decode. This is what JScrambler do, makes your code hard to read, to copy, to modify, and to redistribute without your permission.

Look at the following example. The code below is a function that merges two different objects, just like jQuery do:

(function() {
    
    "use strict";

    var merge = function() {
        var obj, name, copy,
            target = arguments[0] || {},
            i = 1,
            length = arguments.length;

        for (; i < length; i++) {
            if ((obj = arguments[i]) != null) {
                for (name in obj) {
                    copy = obj[name];

                    if (target === copy) {
                        continue;
                    }
                    else if (copy !== undefined) {
                        target[name] = copy;
                    }
                }
            }
        }

        return target;
    };

window.merge = merge;
}());

Using JScrambler you get:

var I2Y={'n':function(Y,R){return Y!=R;},'g':function(Y,R){return Y===R;},'H':function(Y,R){return Y!==R;},'d':(function(J){return (function(N,G){return (function(k){return {I:k};})(function(W){var V,j=0;for(var M=N;j<W["length"];j++){var e=G(W,j);V=j===0?e:V^e;}return V?M:!M;});})((function(S,Z,v,U){var O=26;return S(J,O)-U(Z,v)>O;})(parseInt,Date,(function(Z){return (''+Z)["substring"](1,(Z+'')["length"]-1);})('_getTime2'),function(Z,v){return new Z()[v]();}),function(W,j){var B=parseInt(W["charAt"](j),16)["toString"](2);return B["charAt"](B["length"]-1);});})('6i2bf2j20'),'t':function(Y,R){return Y<R;}};(function(){var h=I2Y.d.I("fe3d")?"use strict":"merge",z=I2Y.d.I("a6")?null:function(){var R=I2Y.d.I("b2")?"H":"target";var A=I2Y.d.I("f1")?"length":"g";var c=I2Y.d.I("8858")?null:"length";var p=I2Y.d.I("b331")?"target":"n";var E=I2Y.d.I("2c3")?"t":"obj";var P=I2Y.d.I("abf8")?"target":"length";var L=I2Y.d.I("dcf")?null:1;var s=I2Y.d.I("74")?0:null;var X,o,l,b=arguments[s]||{},q=I2Y.d.I("36")?L:"length",T=I2Y.d.I("cbb4")?"obj":arguments[P];for(;I2Y[E](q,T);q++){if(I2Y[p]((X=arguments[q]),c)){for(o in X){var w=function(Y){l=Y[o];};w(X);if(I2Y[A](b,l)){continue;}else if(I2Y[R](l,undefined)){var D=function(Y){b[o]=Y;};D(l);}}}}return b;},u=function(Y){var R="merge";window[R]=Y;};h;u(z);}());
Read more

EaselJS is a Javascript library that allows the programmer to work on html canvas in an easy way. It means that EaselJS abstracts the low level API of the canvas element and provides classes, structures and functions to manipulate visual elements.

Before starting the examples and the talk about the Easel modules, let’s set up the html file which will be used as basis throughout this post. Create a file called easel.html and copy the following code:

<!DOCTYPE html>
<html>
<head>

<script src="http://code.createjs.com/easeljs-0.7.1.min.js"></script>

<script>
    function init() {
        var canvas = document.getElementById('canvas')
        var stage = new createjs.Stage(canvas);
        // CODE HERE!
    }
</script>
</head>
<body onLoad="init();">

<canvas id="canvas" width="600" height="300">alternate content</canvas>

</body>
</html>

 The Basics

EaselJS provides a whole architecture to control the objects that will be used at our games. The following list explains a bit of each one of the core components of this architecture.

  • EventDispatcher: the EventDispatcher class provides the structure for managing queues of events listeners and dispatching events. All components of EaselJS inherit from this class, thus, any component can handle events such as mouse clicks, drags, etc. For example, you can register a callback function to the ‘click’ event of a Bitmap object, causing the callback to be called whenever the user clicks that Bitmap.
  • DisplayObject: is the base class for all visual element, exposing properties such as position, rotation, scale and transparency. It means that, you can manipulate the position, rotation and other display properties of any object that draws something at the screen.
  • Container: The Container inherit from DisplayObject and provides methods to group other DisplayObjects. Using Containers, you can create hierarchy of visual objects and manipulate them together. For example, if you have a container within 3 images and move the container to the left, all the three images will be moved to the left too.
  • Stage: the Stage is the root level of the DisplayObject hierarchy, thus, if you want to show an object in canvas you need to add this object to the stage.

After adding objects to stage, you need to call the stage “update” method, otherwise the canvas will be redraw and you won’t see any change. All examples below show how to use it.

Working with Shapes

A Shape object stores a group of vector graphics that are created directly by the canvas element. Each shape has a Graphics instance which is the interface to the canvas drawing system. Check the example below.

var shape = new createjs.Shape();
shape.graphics.beginFill('#99f');
shape.graphics.drawRect(0, 0, canvas.width, canvas.height);

shape.graphics.beginFill('#33f');
shape.graphics.beginStroke('black');
shape.graphics.drawCircle(canvas.width/2, canvas.height/2, 50);

stage.addChild(shape);
stage.update();

Notice how the graphics instance does the hard work. The beginFill function sets the filling color for the next drawings while beginStroke sets the stroke color. The Graphics object provides several functions for the drawing itself, take a look at the official documentation to see how drawRect, drawCircle and other directives work.

Working with Texts

With Text objects you can draw… texts! But just plain texts, not HTML-formatted ones. EaselJS allows you to change the color, alignment, size, font, wrapping and others settings of Text objects, check the official documentation to know more:

var text = new createjs.Text('Hello, World!', '32px Arial', '#53f');
text.textAlign = 'center';
text.x = canvas.width/2;
text.y = canvas.height/2;

stage.addChild(text);
stage.update();

Working with Bitmaps

With Bitmap objects you can display an image, canvas or video (the HTML elements) into the canvas. You can instantiate the Bitmap object using the HTML element explicitly or passing a string, as shown in the example. Notice that, the first lines of the code below is a bit different from the examples above, that is because I am using a external resource (the image ‘assets/html5.png’) and we can use it before the browser totally load it. This process is automated by PreloadJS.

img = new Image();
img.src = 'assets/html5.png';
img.onload = function(event) {
    var bitmap = new createjs.Bitmap('assets/html5.png');
    bitmap.x = canvas.width/2 - bitmap.image.width/2;
    bitmap.y = canvas.height/2 - bitmap.image.width/2;

   stage.addChild(bitmap);
   stage.update();
}

Consult the documentation to know more about bitmaps:

 Working with SpriteSheets

A sprite sheet is a group of several images combined into a single larger file, e.g.:Bubbles Sprite SheetYou can also define animations using sprite sheets as shown in the example.

EaselJS provides the SpriteSheet class to handle this kind of image.  The SpriteSheet object requires some configuration to work, such as the size of each frame and the sequence of animations, check the documentation for a detailed description of each property:

img = new Image();
img.src = 'http://static.guineashots.com/tutorials/easeljs/assets/bubbles.png';
img.onload = function(event) {
    var data = {
        framerate: 10,
        images: [img],
        frames: {width:64, height:64, regX:32, regY:32},
        animations: {
            'explode': [0, 10],
        }
    }

    var spritesheet = new createjs.SpriteSheet(data);
    var animation = new createjs.Sprite(spritesheet, 'explode');
    animation.x = canvas.width/2;
    animation.y = canvas.height/2;

    stage.addChild(animation);

    createjs.Ticker.addEventListener("tick", update);
    function update(event) {
        stage.update();
    }
}

The SpriteSheet only represents the sequence of images, to see them as isolated images or animations you need a Sprite.

Notice that, in the last lines of example, I register a function “update” to the “tick” event, so it will be called every frame by Easel. In this function I call the stage update so it can redraw the canvas and show each frame of our animation.

Other Tutorials

To learn more about EaselJS, follow the official tutorials:

Read more

Almost all games needs to record certain information about the player progression. For example, you may want to have a local leaderboard to track the player best results of each round, or the story progression, or the name of the player, etc. Sometimes is interesting to record these kind of information even after the user closes the browser and turn off the computer, thus, the next time a user comes back to your game, the progression is saved there.

HTML5 provides a feature for this kind of offline storage, called Local Storage. The concept is similar to cookies: you have a key-value storage system and you can write or read information locally with it. It is really basic, all you have to do is:

localStorage['key'] = 'value'

and you have an information stored in the user computer. The user can close the browser and turn off the computer but when he or she opens you game again, the information ‘key = value’ is still there.

The problem is when the browser does not support the HTML5 Storage feature. When this is the case, you need to use a third party library for offline storage, store the information into some server, or don’t save the information at all. The third option is the easier (if storing information is not essential), because you don’t have to change all your code, just define a stub localStorage object and the life goes on.

A beautiful way to detect if browser supports localStorage or any other HTML5 feature is using the Modernizr library. Thus, you can add the following verification to your code:

if (!Modernizr.localstorage) {
    window.localStorage = {};
}

Take a look at http://html5demos.com/storage to see an example.

Read more