Just for the record, I hate the theme of LD 32, “unconventional weapon”. There were a bunch of good themes on the final voting round, like “grow”, “companion” and “abandoned”, but they have lost for “unconventional weapon”, gosh…

Well, we have to do what we have to do. The theme is what it is and now I have to use it. Unfortunately, I’m writing these after 2:30 hours of brainstorming and I still have no clue of what to do.

I really want to use AI, so I trying to add some agents (enemies, allies, creatures, companions, whatever), and giving my artistic and resource limitation, I thinking in use tile maps. That’s all I got for now and it may be useless tomorrow.

I’ll keep you updated.

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

So, what is happening here? Almost March and I didn’t post anything useful here, hum? Well, I’m working hard on Behavior3 and on my Ph.D project. There is a lot of interesting things happening, and I hope to share some with you in time. For now, let’s talk about some major changes on Behavior3 Editor.

First of all, Behavior3 Editor and Behavior3JS are now individual projects, each one with its own repository. Check it out:

In the first version (0.1.0), I tried to make a visual editor, a visual debugger and, common to these two, a viewer. The viewer were responsible for drawing the blocks and connections in a canvas, the editor were responsible for the edition of blocks and connections (adding, removing, selecting, changing properties, moving, etc) and the UI needed to handle that. The debugger were planned to control the execution of the tree and view the information of nodes. This architecture were suppose to be modular and easy to handle, but…

It was a complete nightmare, when you had to change something, you never knew  if you had to look to the editor or to the viewer, and when you modified something in the viewer, you had to build it (because editor were dependent on the built viewer), copy the built file to editor – then, you find a small typo, change again, repeat the process, over and over. Moreover, despite the fact that the editor worked fine, it was depending on the HTML elements, i.e., any change on the HTML stops the internal functions, any change to the internal functions stops the HTML elements.

To overcome these problems, I firstly merged the Viewer and Editor, so you don’t have to search inside two projects to find a piece of code that you want to change. The repetition of the build process was also solved, but the internal functions of the Editor were still coupled to the HTML elements.

AngularJS was the solution. A javascript MVC framework with two-way binding. Man, that’s awesome. So, I removed the dependence of jQuery and almost all other 3th party libraries, including foundation. I had to rewrite menu, scrolls and all other nice visual features, but at the end, it was worth and worked pretty well (some bugs on firefox, unfortunately). Check it out the general scheme:

b3editor - architecture

Current Behavior3 Editor Architecture – App and Editor are completely independent. App calls editor and listen to editor events.

With these architectural changes, I can add more features to b3editor. I already pushed a tree management (now you can add, edit and remove several trees) and I’m going to implement project management. To have a better follow up, check the issue list https://github.com/renatopp/behavior3editor/issues. I hope to release the next version of B3 in the next 2 months.

Thanks for @grifdail, @elmarquez and @FunkMonkey  and Daniel Balster for suggestions and patches on this version.

Read more

As the first post of the year, I wish you all a great 2015!

This last year was crazy, lot of changes in my Ph.D., several projects, great trips. As a reminder to myself, I will summarize my activities of 2014 relevant to this blog and record the promises of new year`s resolution for 2015.

2014

In April of 2014 I created this blog with 2 things in mind: I wanted to motivate myself to keep a frequency in my Game Dev studies by forcing me to always write a new articles here; and to serve me as a development diary so I could put ideas and thoughts here and after some time, I could revisited all my steps towards game industry. After 9 months, I wrote 39 posts and got more than 11 thousands views. I received some feedback (less than I wanted and more than I expected), via comments here and email. I thank you all for the audience, feedback and discussions.

In the half of the year I finally decided what to do in my Ph.D.. After months of (almost) unfruitful areas, researches and experiments, I decided to move on and research something related to game AI development, but with the requirement to also have something to do with robotics (there is a lot of methods and models fulfill that!). After some weeks of research and lot of readings, I decided to go in the direction of Behavior Trees, once it has some nice successful applications and big support on the game industry and now its being applied on robotics.

In consequence of my developments in the Ph.D. and my studies on Game Dev, I started 2 open source projects: Creatine and Behavior3JS. Creatine is my set of tools to develop games within CreateJS, while Behavior3JS is an implementation of Behavior Trees to JavaScript. I use Creatine to create my games while I use Behavior3JS to games and to my research. B3 received a lot of attention since its release (about 2 months in this moment), it already has 32 stars and 5 forks on github (it is my most-successful project).

Talking about games, I created 3 games for ludum dare but didn’t complete a few others. I’m really happy with my games this year – despite the unfinished ones – they weren’t great games but they have their importance to me. The last game of the year was Baa-Ram-Ewe, which earned the #35 place on the competition (there were more than 2600 submissions), I am really happy with this result and I hope to do better next time.

2015

For this next year, I want to:

  • Publish some papers about BT and machine learning;
  • Update and improve Creatine and Behaivor3JS;
  • Write more than 40 posts here in the blog and receive more than 11000 visits;
  • Write more ludum dare games and finally finish some full game;
  • I plan to work on the game industry, so I decided to learn – really learn – C++.

I thank again for all comments, talks, suggestion and critiques, on this blog, reddit, github and any other mean.

Read more