javascript

Last updates on Skald Engine:

Color utility functions

PixiJS handle colors by its int value (e.g., 0xFFFFFF), so I created a bunch of function to convert or manipulate colors in this format. Right now you can:

  • Convert color from/to RGB format (array, [255, 255, 255]).
  • Convert color from/to HEX format (string, ‘#FFFFFF’).
  • Convert color from/to HSL format (array, [255, 1, 1]).
  • Get the individual color channels (red, blue, green, hue, saturation, lightness).
  • Saturate a color by a given amount.
  • Desaturate a color by a given amount.
  • Covert the color to greyscale.
  • Lighten a color by a given amount.
  • Darken a color by a given amount.
  • Spin the color by the hue space by a given angle.
  • Blend two colors.
  • Tint (blending a color to white).
  • Shade (blending a color to black).

 

Utility for random generators

I also added a bunch of function to generate random numbers and other  stuff related:

  • `random.choose()` to choose a value from an array.
  • `random.inclusiveRandom()` which is similar to Math.random(), but it can include the 1 (i.e., it generates a number in interval [0, 1]).
  • `int()` to generate a random integer.
  • `polar()` to generate a number between -x and x.

Easing function and modifiers

I add more easing functions, a general bell curve and a gaussian shaped (using the normal distribution formula without the normalization term). So they can be used to generate interesting effects.

I also added two function that modifies the easing functions, one for mirroring the result of the easing (it repeat the ease function 2 times, but it invert the result of the second half), and one for repeating (pretty straightforward). I am still testing this format, so I don’t know if I’m gonna keep it.

Particle systems!

Added an initial implementation of particle system. there are some improvements to be made, but it is working pretty good.

Game config changes

I decided to remove the manifest as parameter of the game and added it as an item of the configuration. This should keep consistence among the API.

Additionally, I added a startScene and a preloadScene option, so the game can initialize and run a preload scene during the manifest loading, and start automatically the main scene when the game starts.

To help you in this initialization process, I also added a `start` event, triggered after the preload (if there is any item on the manifest), and added a default preload scene.

Scene stacking

I thought I could live without it, but I was wrong, so we have scene stacking now. Now you can add or remove scenes over the base scene (the one called with `play` method). The scenes are attached to the base scene, so if you remove the base, all scenes in the stack will die too.

 

Next steps

For the next alpha release, I want to add an event pool for event recycling (so we don’t have to create a new event instance everytime an event is triggered), and simplify the scene API. Right now the scene API is very limited and unintuitive.

Read more

I’ve been talking a lot about Behavior Trees (BTs) lately, partially because I’m using them for my PhD. But although, BTs provide a powerful and flexible tool to model game agents, this method still have problems.

Suppose you want to model a bunch of sheeps (just like my last Ludum Dare game “Baa Ram Ewe”), these sheep have simple behaviors: “run from cursor”, “stay near to neighbor sheeps”, “don’t collide with neighbor sheeps” and “follow velocity and direction of neighbors”. A sheep can also have 4 states: “idle” when it is just eating grass, “obey” when it is being herded by the player (using the mouse), “stopping” between obey and idle, and “fear” when a predator is near. The behaviors are always executing, but they may have different weight for different states of the sheep. For example, when a sheep is “obey”-ing, it try to be near other sheeps more than when it is eating grass or running scared.

Modeling this as a Behavior Tree is hard because:

  1. BTs don’t really model states well. There is no default mechanism to define or consult which state an agent is; and
  2. All behaviors are executed each tick, thus this agent wouldn’t exploit the BT advantages of constrained executions.

Notice that, you still can model these sheeps with BTs, but the final model would be a lot more complex than it would be using other simple methods.

In previous posts, I also talked about how Behavior Trees have several advantages over Finite State Machines (FSMs). But, in cases like this a FSM is a lot useful and considerably easier to use than BTs.

Implementation

Like my Behavior Tree implementation, I want to use a single instance of a FSM to control multiple agents, so if a game has 100 of creatures using the same behaviors, only a single FSM instance is needed, saving a lot of memory. To do this, each agent must have its own memory, which is used by the FSM and the states to store and retrieve internal information. This memory is also useful to store sensorial information, such as the distance to nearest obstacles, last enemy position, etc.

First, consider that all states and machines have a different id, created using the following function:

function createUUID() {
  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;
}

and to simply inheritance, we will use the Class function:

function Class(baseClass) {
  // create a new class
  var cls = function(params) {
    this.initialize(params);
  };
  
  // if base class is provided, inherit
  if (baseClass) {
    cls.prototype = Object.create(baseClass.prototype);
    cls.prototype.constructor = cls;
  }
  
  // create initialize if does not exist on baseClass
  if(!cls.prototype.initialize) {
    cls.prototype.initialize = function() {};
  }

  return cls;
}

We will use a Blackboard as memory for our agents. Notice that, this is the same blackboard used in my behavior trees.

var Blackboard = Class();
var p = Blackboard.prototype;

p.initialize = function() {
  this._baseMemory = {};
  this._machineMemory = {};
}

p._getTreeMemory = function(machineScope) {
  if (!this._machineMemory[machineScope]) {
    this._machineMemory[machineScope] = {
      'nodeMemory'     : {},
      'openNodes'      : [],
      'traversalDepth' : 0,
      'traversalCycle' : 0,
    };
  }
  return this._machineMemory[machineScope];
};

p._getNodeMemory = function(machineMemory, nodeScope) {
  var memory = machineMemory['nodeMemory'];
  if (!memory[nodeScope]) {
    memory[nodeScope] = {};
  }

  return memory[nodeScope];
};

p._getMemory = function(machineScope, nodeScope) {
  var memory = this._baseMemory;

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

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

  return memory;
};

p.set = function(key, value, machineScope, nodeScope) {
  var memory = this._getMemory(machineScope, nodeScope);
  memory[key] = value;
};

p.get = function(key, machineScope, nodeScope) {
  var memory = this._getMemory(machineScope, nodeScope);
  return memory[key];
};

We will also use a state object that implements the following methods:

  • enter“: called by the FSM when a transition occurs and this state is now the current;
  • exit“, called by the FSM when a transition occurs and this state is not the current one anymore; and
  • tick“, called by the FSM every tick in the machine. This method contains the actual behavior code for each state.
var State = statejs.Class();
var p = State.prototype;

p.initialize = function() {
  this.id = statejs.createUUID();
  this.machine = null;
}

p.enter = function(target, memory) {}

p.tick = function(target, memory) {}

p.exit = function(target, memory) {}

Our FSM will have the following methods:

  • add(name, state)“: adds a new state to the FSM, this state is identified by a unique name.
  • get(name)“: returns the state instance registered in the FSM, given a name.
  • list()“: returns the list of state names in the FSM.
  • name(memory)“: return the name of the current state. It can be null if there is no current state.
  • to(name, target, memory)“: perform a transition from the current state to the provided state name.
  • tick(target, memory)“: tick the FSM, which propagates to the current state.

Notice that, some methods must receive the blackboard and the target object as parameters, which can be a little annoying – this is the downside of using a single FSM to control multiple agents – but the cost is small compared to the gain in memory.

The target parameter is usually the agent being controlled, but in practice it can be any kind of object such as DOM elements, function or variables.

var FSM = statejs.Class();
var p = FSM.prototype;

p.initialize = function() {
  this.id = statejs.createUUID();
  this._states = {};
}

p.add = function(name, state) {
  if (typeof this._states[name] !== 'undefined') {
    throw new Error('State "'+name+'" already on the FSM.');
  }

  this._states[name] = state;
  state.machine = this;

  return this;
}

p.get = function(name) {
  return this._states[name];
}

p.list = function() {
  var result = [];
  for (var name in this._states) {
    result.push(name);
  }

  return result;
}

p.name = function(memory) {
  return memory.get('name', this.id);
}

p.to = function(name, target, memory) {
  if (typeof this._states[name] === 'undefined') {
    throw new Error('State "'+name+'" does not exist.');
  }

  // exit current state
  var fromStateName = memory.get('name', this.id);
  var fromState = this.get(fromStateName);
  if (fromState) {
    fromState.exit(target, memory);
  }

  // change to the next state
  var state = this._states[name];
  memory.set('name', name, this.id);
  state.enter(target, memory);

  return this;
}

p.tick = function(target, memory) {
  var stateName = memory.get('name', this.id);
  var state = this.get(stateName);
  if (state) {
    state.tick(target, memory);
  }
}

Example

Using a simple Boiding algorithm, we have 3 states: “idle”, “obey” and “stopping”.

var StoppingState = Class(State);

StoppingState.prototype.enter = function(target, memory) {
  // when this state is initiated, it resets the timer
  memory.set('starttime', new Date().getTime(), this.machine.id, this.id);
}

StoppingState.prototype.tick = function(target, memory) {
  var mx = game.stage.mouseX;
  var my = game.stage.mouseY;

  // transition to obey
  if (euclidDistance(target.x, target.y, mx, my) < SHEEP_OBEY_DISTANCE) {
    this.machine.to('obey', target, memory);
  }

  // transition to idle
  var starttime = memory.get('starttime', this.machine.id, this.id);
  var curtime = new Date().getTime();
  if (curtime - starttime > 3000) {
    this.machine.to('idle', target, memory);
  }

  // call the boid algorithm with specific weights
  flock(target, memory.get('neighbors'), [0.0, 0.1, 1.0, 0.4])
}

Use the mouse to move the white balls:

Continue reading Finite State Machines in Javascript

Read more

Following the new milestone of CreateJS, I just released Creatine 0.2.0!

This version has some cool new additions to the library:

  • Tile Maps: now you can load maps created with Tiled by using the new TMXMap. It supports all maps projections of tiles (orthogonal, isometric and staggered) and all type of layers (tile, image and object). Check it out the examples.
  • Jukebox: a helper class to handle music and sound playback. With this class, you can set different volume setting for music and sounds, and play random sounds from a group.
  • Storage: a helper class to handle persistent data using the HTML5 localStorage. With this class you overcome the type limitation in localStorage (it only accept string variables) and , thus, can save and retrieve objects, numbers, arrays, etc.
  • Entity-Component-System: a ultra basic implementation of ECS model, I hope to provide more features in the future.

Moreover, there are some other modifications on the existing features:

  • Sizers now manage scale and registration point properties of children.
  • Fixed an initialization bug present in several transition.
  • A complete update to the class and inheritance model of creatine, following the new style of CreateJS.

Together with this new version, I also published the new website for creatine (the old one http://guineashots.com/creatine now redirects to the new site):

http://creatine.guineashots.com

Right now I’m updating my boilerplate to follow the new releases and to include a new improved architecture.

Read more

After some weeks working on this, I finally released the first version of Behavior3JS, my javascript library for behavior trees.

http://behavior3js.guineashots.com

I wrote 2 tutorials this month about implementing a behavior tree from scratch (here and here), which content was based on this library. Together with the core classes and nodes, I also released an online and visual editor, where you can design your behavior tree with custom nodes and export it to JSON format.

b3editor

Unfortunately, I couldn’t release the visual debugger together (I will travel next week, so I preferred to release what I had right now), but for sure, this is the priority for the next versions.

Take a look in this project on Github: https://github.com/renatopp/behavior3js

I recommend you to also take a look at the user guide, so you can have an idea of how this works: https://github.com/renatopp/behavior3js/wiki

Read more

Fast links for other parts and tutorials:

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


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

We will implement here:

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

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

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

** Remember: all nodes must inherit from BaseNode.

Composites

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

Sequence

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

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

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

    return SUCCESS;
}

Priority

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

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

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

    return FAILURE;
}

MemSequence

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

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

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

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

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

    return SUCCESS;
}

 

MemPriority

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

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

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

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

    return FAILURE;
}

Decorators

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

Inverter

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

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

    if (!child) {
        return ERROR;
    }

    var status = child._execute(tick);

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

    return status;
}

Actions

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

Wait

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

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

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

ChangeColor

Change the color of the target object.

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

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

    return SUCCESS;
}

ChangePosition

Choose a random position for our target object.

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

    return SUCCESS;
}

Conditions

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

IsMouseOver

Verifies if the mouse is over our target object.

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

Example: Jumping Box

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.

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

Read more