Programming

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

For all my academic works, experiments, personal projects, tests or any other problems that I can solve by writing a program, I try to use Python. Well, Python is my main language and after 6 years of experience with it, I can say that I love this language. More yet, I’m only passionate for coding today because of it. Python is an easy language to learn and to program, intuitive and clear. Everything you can do with other languages, you can do in Python with half effort and double love. It has several useful builtin libraries and a lot of epic frameworks, being used for web development, scientific computing, networking and in several other areas. But and for games?

There are several frameworks used for game development, and I will talk about some of them here. Notice that, my focus is on 2D game development and does not mention any 3D engines.

Pygame is the most known engine for Python and it is a binding for the C++ SDL 1.x. The community of Pygame is huge and there is a lot of tutorials out there, and, like SDL, Pygame is very mature and stable. The downside is, Pygame is slow as hell and provides a poor support to hardware acceleration, making it nearly impossible to run a heavy game on old computers. I feel that it is pretty hard to optimize the code and when I do it, several other problems occurs such as tearing and unstable fps. Despite the community size, Pygame is rarely updated (the last release is from 2009).

Pyglet is the alternative to Pygame. It is built upon opengl and it is a lot faster than Pygame. The Cocos2D engine was created as a framework upon Pyglet. The problem is, Pyglet is unstable, with a lot of problems, mainly on Mac OS. The community is nearly zero, it is poor documented and is also rarely updated (with less activities than Pygame).

Any other library using Pygame and Pyglet (such as Spyral, Ignifuga and Cocos2D) have the same problems already cited.

Pygame and Pyglet are the main option for game dev in Python, but there is also an opengl binding called PyOpenGL, which can be used to low level development. As far as I known, there is no promising library using it as basis.

Together with all problems already cited, there is the difficult to distribute a python game. You can use py2exe or cx_freeze to do so, but is pretty easy to do the reverse engineering and access the complete code and resources. Moreover, games are heavy applications in all senses and require a lot of optimization to run fast (at least 30fps), and this scenario is for C++. The slow speed is inherent to the Python and is not really a problem for most of the applications, including scientific computing, but for games is a real concerning.

The only real use for Python in commercial games today is as a script language, and even this is more rare to see.

Read more

In my Ph.D. program, every student must sign in into the “Teaching Practice” course. In this course, we have to help the teacher on his undergrad class, making lectures, evaluating the practical projects, etc. In this semester, the undergrad students had to implement a minimax search to play chess and I was in charge of developing the game to be the basis for them, so they can focus on the AI problem.

This chess game is not actually Chess, it is a simplified mini-game called Pawn Battle. In this mini-game you can set up the board with all the chess pieces, except the king. To win a Pawn Battle game, a player must promoted one of its pawns or eliminate all opponent’s pawns.

The project, called liac-chess, can be found on github and it is open to contributions.

liac-chess

The biggest difficult in programming a chess game is to develop the artificial intelligence. You must choose the right algorithms and data structures, and they must be well developed in order to achieve a reasonable performance in computation speed and play well the game.

This precaution about the algorithms and data structures is necessary due to the amount of possible states in a chess game. The chess game has a average branching factor of 35. This means that, for each configuration of the board, there are, in average, 35 possible movements. So to compute 2 movements ahead, there are 35^2 (1225) possible positions, and to 5 movements there are 35^5 (52,521,875), to 10 movements there are 35^10 (2,758,547,353,515,625) possible states!

I write here some conclusions about how to represent the board, to generate the piece movements, and how to search the best state, given my experience developing a bot for liac-chess. Everything about chess programming, including what I’m writing here, you can find on the site http://chessprogramming.wikispaces.com/, which is a specialized wiki for chess programming. Highly recommended.

Board Representation

The first challenge when programming a chess game is to decide how you will represent the game board. This choice will imply how you will generate the moves for each piece and how you will evaluate the state. Besides the board itself, you also need additional information about the game, e.g., the en passant position, whom is the turn, etc.

You can represent everything in the good and old oriented object style, with a game class that includes the board as a matrix of pieces, and other values. This is the easiest way to implement the AI, and will work, at least for a few number of states (in my computer, this can reach 4 movements ahead, approximately 1,500,625 states, in 3 or 4 seconds).

For a high-level AI bot, this implementation is pretty rough. You need more efficiency. I think, the best option here is the bitboard representation, which is relatively easy to implement and very fast to use.

In the bitboard representation you use a bitarray, containing 0 or 1, with 64 positions, one for each board cell. You will have several bitboards to present the board, e.g., for the black bishops, white knights, etc., as you can see on the image below.

bitboardThe great advantage of the bitboard is that you can use bitwise operator on it, this include flipping, mirroring and rotating the board. If you use a bitboard to store, for example, all position that the black queen can attack, you can also verify if the queen can attack some piece by a simple AND operation. Here you can see a lot of information about general setwise operations that you can apply to bitboards.

Move Generation

There is a lot of techniques to implement the generation of moves in the chess, depending heavily on the board representation. The move generation is the slowest part on the AI process, so it must be carefully implemented and tested.

Specifically to the bitboard representation, you can use the ray or line techniques, where you trace a ray/line in some direction and store all cells below this ray/line. By storing these cells on a bitboard, you can perform the operations commented on the “Board Representation”.  Check it out this link and this other.

Searching The Best State

The search algorithm is the main component of a chess AI, and is – again – essential to choose, implement and test a good algorithm. For games like chess (zero-sum games), the minimax is the most common algorithm by far. In general all algorithms for this kind of game is based on the minimax, such as its compact version, the negamax.

A simple and efficient way to search the best state is by using the negamax algorithm using the alpha-beta pruning. The alpha-beta can reduce significantly the search space, allowing the algorithm to evaluate more movements ahead than it would be possible by only the negamax algorithm.

There are other techniques you can apply in order to enhance the search speed, for example the transposition table and the iterative deepening.

Another feature you may need is to run the search in a separated thread and stop it when necessary. For example, the default time limit per move on liac-chess is 5.9, more than that you receive an infraction (with 5 infractions you lose the game). Thus, given a time limit, you can stop the search and perform the best move that the algorithm founded so far.

State Evaluation

An evaluation function computes how much a given board configuration is good. Notice, that “good” is an abstract term on chess, due to its complexity, so the evaluation is high based on heuristics. The heuristics used in the evaluation are the main component to generate good and natural moves.

You can evaluate several aspects of the game, e.g., the material evaluation (how much pieces each player have), the positional evaluation (how good is the position of the pieces), among other things.

There are several studies trying to identify how important each kind of piece is, take a look at this table. In general, we know that: a bishop is equal (or slightly better) to knights; two bishops, or two knights, or one bishop and one knight are better than one rook; one bishop, one knight and one rook is better (or equal) than a queen.

A piece can have a more or less value depending on the condition of the board, for example, a pair of bishops is better than a bishop and a knight. There is a lot of heuristics for the piece evaluation, implement what you think is the most important for your bot.

For the positional evaluation you can use predefined matrices within the values for each piece relative to each board cell (called piece-square tables).

Conclusions

Developing liac-chess was a fun experience, I’ve learn a lot of computer chess =].

Notice that, you won’t find any AI bot on the project page, only a random bot that we used as baseline to the student’s bots. I don’t know if a will share my bot, because the liac-chess is being used by the undergrad class and it is important that they program it itself.

What I can is that, I only used the piece values for material evaluation and the piece-square tables for positional, together with a negamax search and alpha-beta pruning. My bot had great performance, winning almost every game against the students bots (it loose 1 game and tied some ones).

I failed on the representation and move generation, using a matrix to store the pieces and a bad implementation of the Ray attack. Using the time limit as 5.9 seconds, I could only compute 4 movements ahead.

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