Skip to main content
fsm

Finite State Machines in Javascript

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:

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

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

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.

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.

Example

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

Use the mouse to move the white balls:

(more…)

preview

Architectural Changes on Behavior3 Editor

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.

node_selector

Implementing A Behavior Tree – Part 2

Fast links for other parts and tutorials:

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


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

We will implement here:

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

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

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

** Remember: all nodes must inherit from BaseNode.

Composites

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

Sequence

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

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.

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.

 

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.

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.

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!

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.

ChangePosition

Choose a random position for our target object.

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.

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:

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!

bt_architecture

Implementing A Behavior Tree – Part 1

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.

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).

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.

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.

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.

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.

banner800x300

My Experience Within Ludum Dare 30

banner800x300

Ludum Dare 30 ended some days ago, but unfortunately I couldn’t post this before, so much work to do, so many projects! Anyway, In this post I will tell my experience within this last Ludum Dare, my third one.

Before the announcement of the theme, I was making some plans:

  • I wanted to do something with Behavior Trees. As commented on the last posts here, BT is part of my research in the doctorate program, and LD is a good event to have some real practical experience with it;
  • I wanted to use AI for several agents. A lot of trouble implementing a behavior trees for this compo and then using it in a single NPC? It seems a waste;
  • I wanted to make a game not literally connected to the theme. The thing is, most people take the theme literally and make the default game option, specially the composed words such as “lost in space”, “connected worlds” or anything involving dead things (which means you are going to have zombies).

On Friday night the theme came out: Connected Worlds. At first I hate it, I was expecting something like “you are already dead” or “no one can see you” (I have a cool idea to make something related to these themes), but was Connected Worlds. Then, still on Friday, I made some brainstorm and came out with:

  • A game that uses the theme metaphorically: each person is an independent individual, with its life, with its own world. Thus, connecting worlds refers to connecting people. Therefore, a relationship game in which the player must help the agents (which I call chibis) to connect themselves and to fall in love.
  • Following the idea of using behavior trees on this game, I planned to each chibi be autonomous, controlled by the behavior trees, i.e., they move and talk by themselves, without the command of the player.
  • I predicted that I would spend a lot of time with the behavior trees, thus, the game mechanics needed to be simple: drag and drop! maybe a reflex game! Finally I came up with the following: the player must let the chibis talk with each other in order to make couples; he or she also must drag problems away. Problems are: meddler chibis (which interrupt talks); birds (which poop on chibis); and rains (which wet the chibis).

chibi_plan

After the planning I slept (bad night, unfortunately ;/), and Saturday I started the development.

Tools Used

Same as always:

  • createjs for canvas drawing, preloading, tweening and sound control;
  • creatine for the game structures (such as scenes and layouts);
  • inkscape and gimp for graphics;
  • sxfr or similar, guitapro and audacity for sound and music;

 

Gameplay

First thing I’ve implemented, a simple drag and drop mechanics with trivial gravity implementation. I’ve spent some time on this to organize the game architecture and some more time later to fix all bugs after the BT implementation.

I think I’ve spent about 10 hours on this.

Graphics

Graphics needed to be simple, I couldn’t lose much time on this because I was already late on my schedule (BT implementation at this point were very buggy). I also wanted that they would be cute. Then simple + cute = chibis!

chibis
Example of cute little Chibis
mychibis
My Chibis

I also needed a feedback to the conversation, showing to the player that the chibis are talking to each other. I remembered that The Sims do that brightly with the conversation balloons. Thus I also drew something similar.

balloons
Some conversation Balloons, inspired on The Sims

To differentiate the static objects to the draggable ones, I tried to draw white borders on draggables and no border for the statics, but at the end I think this made no difference to the player.

I spent about 6 hours on this.

AI

IMG_36472

This was the tough part. I was risking the whole game when I decided to base the gameplay on this, but I tried anyway. My idea was – using behavior trees to control all actions of the chibis – but I had to implement the BT from scratch! Of course, I’ve looked for BT implementation in javascript, but all frameworks I found seemed very poor to me. Thus, I started the development based on the paper [Marzinotto, 2013], which have a formal description of the model.

And of course, implementing a fully functional behavior tree in few hours basing it on some paper is completely insane. There was a lot of bugs, man, A LOT. This forced me to learn that debugging BTs without a visual help is VERY, VERY, VERY HARD.

I used the following structure for my behavior tree library:

  • AIBehaviorTree: is the tree class, it only have the root node and a function to propagate the tick signal. This function receive the “target” object, which, in this case, was the Chibi object;
  • AIBaseNode: all nodes inherit this one. It doesn’t have much code, just a wrapper to help me debug the model;
  • AIInternalNode: nothing special;
  • AILeafNode: nothing special too;
  • AIDecorator: nothing special tooo;

and with this I’ve implemented the base internal nodes:

  • AISequence: the sequence composite node (similar to the AND operator);
  • AIPriority: the priority composite node (similar to the OR operator);
  • AIMemSequence: similar to the sequence node, but it remembers which child returned the RUNNING state at the last tick, and doesn’t execute the children before this node, i.e., The Mem Sequence execute directly the last RUNNING node, skipping previous children. To know more about this consult the reference.
  • AIMemPriority: similar to the AIMemSequence.
  • AIMemRandom: similar to the Mem nodes, but it choose its children randomly.

With all this implemented, I had my little improvised and buggy BT framework. Notice that, all this code have ugly hacks. I NEEDED THIS WORKING!

Other important detail. Nodes on the BT does not store any control variable on the tree structure, this allowed me to use a single BT to all chibis. To make this work, each chibi object have a “memory” variable (an empty javascript object) in which the tree nodes can write and read information. For example, a “Wait” action write how much chibi is waiting on this memory, e.g., target.memory.tree.node[id].timeWaiting += fdelta .

Other problem related to developing a game based on behavior trees it that, modeling the agent behaviors without a visual tool is also pretty hard!

Firstly, it is not trivial to decide which behaviors an agent will have, and how to implement them to coordinate with each other. After too many hours I had 21 unique actions, 15 unique conditions, and 2 unique decorators; resulting in 92 nodes to model the chibis. With this, I’ve also learned that modeling this kind of thing is pretty hard programmatically, you need a visual tool to understand what is really happening to the model.

I spent more than 20 hours on this!!!!!

Fluffy Things

In the last 4 hours I had to fix some minor bugs and to make things more beautiful (or, at least, not totally crap). Than I made the visual to all screens (menu, credits, …), including deciding the name of the game and the logo. In the last 2 hours I also could create a tutorial and 4 different levels to the game (which is not that cool because there is no real variation on the levels neither they are challenging).

So, 4 hours on this.

 

Sounds and Musics

Unfortunately, I couldn’t manage to create sound effects nor music. I don’t have much experience on this and probably would take more than 4 hours to make something reasonable.

Summary

GOOD:

  • First Ludum Dare that I didn’t change the plan in the half of the compo!
  • Behavior Tree worked very well and there were no relevant bug at the final version of the game;
  • Despite the time I spent on it, the visual of the game is pretty good;
  • There are very few games on Ludum Dare that uses AI as this one, I’m very proud of it;

BAD:

  • Constant fear of failing to finish it;
  • Very hard to model behavior trees programatically;
  • VERY hard to debug behavior trees without visual helper;
  • Mechanics is incredible boring and repetitive;
  • I couldn’t finish several aspects of the game, but the worse was the sound and not fixing the crap mechanics;

 

ss5-gameplay

(VIEW LUDUM DARE ENTRY | PLAY LOVE CRAFT)