Mar 22

A Pattern for handling concurrent edits to a MongoDB Document in Node.js

Lately I’ve been working on converting my space strategy game (Astriarch) to multiplayer using Node.js, Mongodb, and Mongoose.

One problem I faced while making the game multiplayer is handling concurrent edits to the mongo game documents. Here is the scenerio: two players decide to send ships (edit the document) at the same time. If we are lucky, there are no problems, however there is a chance that both players get the latest version of the document one after the other (before either one of them has time to save the document), then concurrently edit and save the document. What this means is that the last person to save the document wins, the first person’s edits are lost.

This problem can be handled in a couple of ways:

  1. Change the model so that anytime there is the possibility of concurrent edits to the document, a new collection (or model) is created for each user’s edits, then at some point in the future those edits are merged into the document when it is guaranteed that only one process is modifying the document.
  2. Use a nonce field in your document to protect against concurrent edits as described here.

The problem with option #1 is that it is more difficult to implement, it means making your model and processing more complicated, and you still need to guarantee that at some point you can safely merge in the changes to your document by ensuring only one thread/process is modifying the document at that time.

The key to option #2 is that a user will only be able to modify the document if the nonce field has not been changed since that user last fetched the document, this is done by providing the nonce within the update command.

models.PostModel.update({"_id":postId, "nonce":doc.nonce}, data, callback);

Depending on your application, if you are not able to update the document because someone else has updated it, you may simply want to return an error for the user with the latest document so that the user may choose to perform the edits and try to save again.

For my application, I wanted to make a generic function for handling concurrent edits to a mongo document, that way I could leverage this function in each context where edits to the document had to be made.

Here is a Github Gist of the “savePostByIdWithConcurrencyProtection” function and a sample of how it is used:

Notice how the savePostByIdWithConcurrencyProtection takes a transform function that it will execute to perform the actual work of the edit on the document object, and then handles the rest of the logic of performing the update while ensuring the nonce is used in the update as well as recursively retrying until some limit is reached.

You can see an example of how to use this function in the AppendPostText method where the transform function simply appends the text passed into the function to the document.

This pattern allows reuse of the same complex concurrent edit protection and retry logic in many different areas of my application.

Apr 23

Create your first Node Module and publish it to the NPM registry

Installing Node Modules through NPM

NPM is the Node Package Manager, it makes it easy to install external libraries and frameworks for use in your own projects. With NPM installed you can simply type:

npm install module-name

Upon running this command, npm will fetch that module from the repository and place it within the “node_modules” directory within your project. You can also install modules globally by adding the -g argument, installing a module globally places the code within the “node_modules” directory where the node binary is installed.

 

Steps to create your own public npm module

  1. Create a new repository on github and clone it locally
  2. Create a package.json file to describe your module
  3. Create and Test the code for your module
  4. Publish your module to NPM

 

Start creating your first NPM module

To create your own module, you’ll want to have a public repository on GitHub to house the source code. After cloning your new module repository to your local machine, run:

npm init

This will walk you through a set of prompts that allows you to specify details about your new module.
NPM Init

Most of these details are pretty obvious, and for many of the prompts you can just select the defaults. Entry point is the javascript file that will be invoked when consumers of your module “require” it, this file will include the main logic for your module, or if it is a large module you can export public functions found with other files (typically in the lib directory). After filling in the required information, a package.json file will be created with all the entered details

Create and Test the code for your module

Obviously, you’ll want your node module to do something useful, so start building out the functionality your module will provide. For my sample module, let’s say I want to make a function to calculate the distance between two points, my index.js file might look like this:

exports.dist = function(p1, p2){
        return Math.sqrt(Math.pow(p2.x - p1.x, 2) + Math.pow(p2.y - p1.y, 2));
};

Next we can create a number of files to test the code we’ve created. For the dist function I’ve defined I can create a file to test it with the following code:

var myMod = require('./../index.js');
var p1 = {x:1, y:1};
var p2 = {x:4, y:5};
var dist1 = myMod.dist(p1, p2);
console.log("Distance between: ", p1, " and ", p2, " is:", dist1);

In the package.json file I specified the following command to run for the test script:

for f in tests/*; do echo "$f"; node "$f"; done; echo 'passed!'; exit 0

This command will be executed when I run:

npm test

Which should output something like this:

tests/test.js
Distance between:  { x: 1, y: 1 }  and  { x: 4, y: 5 }  is: 5
passed!

Publish your module to NPM

Now that you’ve written and tested the code for your node module, it’s time to publish it to the npm registry. Before you can publish your new module you’ll need to register a user on the npm website, or you can create a user with the adduser npm command. Finally you are ready to publish your module, simply issue the command:

npm publish

You will be prompted for the credentials for the user you just created and if all goes well, your module will be available for other to install using the npm install command:

npm install module-name

When making changes to your module you’ll have to update the version number in the package.json file and then reissue “npm publish” this will ensure users of your module can get the latest code.

Now that you’ve published your module you and others can leverage that useful code in other node projects!

References

npm developers guide
How to Module

Mar 23

Installing and switching between multiple versions of Node.js: n vs. nvm

nodejs-light

The need for a Node Version Manager

Sometimes it is necessary to be able to quickly switch between versions of Node.js without having to uninstall and reinstall a new version. Perhaps one project is written for an older version of Node.js and works on that version, but you’d like to easily test it against a newer version of Node, or perhaps other projects you manage require a newer version of node and you need to be able to switch back and forth. There are two very good Node version management tools for this purpose: n and nvm, they work somewhat differently and each tool has its’ own advantages and disadvantages. I’ll be discussing these differences based on my experience using them on the Mac OS X platform, there will be minor differences in the paths on a linux distro like Ubuntu and for the Windows platform you’ll want to use other packages (nvmw or Nodist).

n at a glance

GitHub: https://github.com/visionmedia/n
Install: $ npm install -g n
Path to Script: /usr/local/bin/n
Node Versions Path: /usr/local/n/versions
How n gets a new version: Downloads Binary Node tar.gz file for platform
How n switches versions: Copies files from /usr/local/n/versions/ to /usr/local/

nvm at a glance

GitHub: https://github.com/creationix/nvm
Install: curl https://raw.github.com/creationix/nvm/master/install.sh | sh
Path to Script: ~/.nvm/nvm.sh
Node Versions Path: ~/.nvm/
How nvm gets a new version: Downloads and compiles source node distribution (binary option also available)
How nvm switches versions: updates $PATH variables to point to requested version within ~/.nvm/ directory

n vs. nvm

Although both n and nvm achieve the same goal (allows installing and switching between node versions), n will move your node files always to the same path (/usr/local/bin/node), so you’ll always know that your current executable lives there. One of the downsides of n is that is will only download and install binary node distributions, for older releases (pre-v0.8.6) you’ll have to compile and install the version on your own and then manually copy the files into your /usr/local/n/versions/ directory in order to switch to those versions. On the other hand, since nvm downloads, compiles and installs from the source files, it will work for just about any node.js version. One downside is that since nvm simply manipulates the $PATH variable to point to the requested version some programs and IDEs (such as WebStorm) that need to point to a full path will have to use the full ~/.nvm//bin/node path.

Can I use both n and nvm?

Sure, but you might not want to use both at the same time since they will conflict. If you want to disable nvm just comment out the line that sources the script file from your .profile or .bashrc file:

[[ -s ~/.nvm/nvm.sh" ]] && . ~/.nvm/nvm.sh

and then run:

source .profile

to remove the nvm script from your path.


If you need to run node versions older than v0.8.6, I’ve found that it’s convenient to install them using nvm, then after it’s installed simply copy the folder over from the nvm directory to the n path:

nvm install 0.6.21
sudo cp -fr ~/.nvm/v0.6.21 /usr/local/n/versions/0.6.21

This allows you to use these versions going forward in n.

Nov 09

Getting started with Node.js, Express and Jade using the WebStorm IDE

Node.js

Over the last few weeks I’ve been experimenting with Node.js and learning about how to use some of the great packages written for it. Node.js is a popular framework for building scalable server-side applications in JavaScript. To achieve high concurrency and scalability, Node.js leverages JavaScript’s event loop and function callbacks for longer running processes so that complex concurrent thread locking logic is not required. Manuel Kiessling’s Node Beginner Book goes through a great Node.js tutorial and explains in detail how to call long running processes (such as a database query or disk I/O operation) and not cause the request to block other operations.

In this post I’ll be explain how to quickly get up and running with Node.js and Express, a great web application framework for Node.js that handles a good bit of the plumbing described in the Node Beginner Book such as building a request router. Before diving into the WebStorm IDE and Express, I suggest you go through the Node Beginner Book tutorial so that you have a better understanding of the core Node.js platform.

The WebStorm IDE

If you are ready to see how WebStorm and Express make Node.js development fast and enjoyable, go to www.jetbrains.com/webstorm/, and download and install the trial version. Also ensure you’ve already installed node.js over at nodejs.org.

Once you have WebStorm installed, fire up the IDE and we can create our first Node.js Express application using the Jade template engine.

Click “Create New Project” from the welcome screen.


Enter a project name, project location and choose “Node.js Express App” as the project type.


On the next screen you need to ensure WebStorm knows where the node executable files are and make sure you have “Jade” selected as the template engine:

After clicking ok, WebStorm will use npm (the node package manager) to download express and jade to your project directory under the “node_modules” folder.

Project Directory Structure

Let’s take a look at the directory structure created by WebStorm:
In the main directory WebStorm has created app.js, our main entry point for our Node.js application, app.js has been initialized to use some modules, configure the template engine to jade, setup routes and start listening on the configured port (which in our case happens to be 3000). You can also see we have a node_modules directory setup by npm for the packages our project required, and a public directory for our client side javascript, css, images, etc… You’ll also notice that we have a directory called routes, and one called views. The index.js and user.js files we have within routes contain functions that correspond with the configured url routes within the app.js file:

app.get('/', routes.index);
app.get('/users', user.list);

Finally, the views directory contains our jade templates which are rendered on the server then passed to the client when responding to a request (more on the jade templates later).


Routes

WebStorm allows us to quickly go to the definition of functions using Ctrl + Left Mouse click on Windows or Command + Left click on Mac.



The index.js route file is very straightforward:

exports.index = function(req, res){
  res.render('index', { title: 'Express' });
};

“exports” just means that this function is going to be available to other files which “require” this file. Notice that each route takes the “req” and “res” as parameters, corresponding to express Request and Response objects. Currently, all our index function does is tell the Response object to render the “index” view passing a JavaScript object as data to the index template.

Jade Templates

Since we are using the Jade template engine, the file that goes along with the index view is: in “routes/index.js” and looks like this:

extends layout

block content
  h1= title
  p Welcome to #{title}

Notice the Jade template syntax is very clean, you can build your HTML markup without using a ton of angle brackets and your tags are automatically closed for you. Jade templates are sensitive to whitespace at the start of lines, you can use tabs or spaces, but not both. Indenting signifies that the indented tags will be rendered within the non-indented tag above it. The “#{titile}” will be replaced with the word “Express” because that is the value of the corresponding title variable in the data object we passed into the res.render call.
Finally notice the “extends layout” at the top of the Jade template, that says that we are leveraging the parent template’s markup (within layout.jade) and that this index.jade template will override blocks defined in the parent.
Here is the contents of “views/layout.jade” that renders the rest of our page content:

doctype 5
html
  head
    title= title
    link(rel='stylesheet', href='/stylesheets/style.css')
  body
    block content

You can learn more Jade template syntax here.

Starting up the Node server

Now that we’ve seen a bit of what was created in our new Node.js Express project, let’s start up the Node.js server and see what it looks like in the browser. To do that we click the green run button on the top toolbar in WebStorm, if we wanted to debug the app (to be able to set breakpoints, step through our server JavaScript code, and set watch variables), we could hit the debug button just next to the run button instead.

Once you see: “Express server listening on port 3000″ point your browser to: http://localhost:3000 and you’ll see a less than exciting page saying “Welcome to Express”.

Let’s code some additions

Now that we’ve started our Node.js server and seen what we have so far, let’s expand on it a bit and learn a little more about Node.js and the Jade template engine. Notice that we also have a user.js route that is invoked by app.js when you navigate to http://localhost:3000/users. First off, let’s just add a link to that url from our index page. We’ll simply add to our index.jade file:

  a(href='/users') Users

Make sure this new line is indented under the “block content” line within the file so it is treated as a child element to the content block.

Now for the fun stuff, right now all our user.js route does is

res.send("respond with a resource");

let’s make it so our user.js contains a list of users and renders that list out with a new Jade template.

If we were building a real app we would want to put our supporting User objects, and any database calls in a separate file, but for our example, we’ll just create a User “class” within routes/user.js:

var User = function(fname, lname, phone) {
    this.FirstName = fname;
    this.LastName = lname;
    this.Phone = phone;
};

var users = [];

We’ve now created a structure for our User objects containing FirstName, LastName and a Phone number, we also have an array called “users” to hold the list of the users our application knows about. Let’s now create an “init” function to populate our users array.

exports.init = function() {
    users.push(new User('Matt', 'Palmerlee', '818-123-4567'));
    users.push(new User('Joe', 'Plumber', '310-012-9876'));
    users.push(new User('Tom', 'Smith', '415-567-2345'));
}

Also we need to invoke this init method somewhere, let’s add a call to it at the end of our app.js file:

user.init();

Now, let’s change the method that is called when you navigate to “/users” so that it renders out a new jade template for this route that will list the users we know about:

/*
 * GET users listing.
 */
exports.list = function(req, res){
    res.render('users', {'users':users, 'title':'Users'});
};

The data we pass to the (soon to be created Jade template) is an object containing our users array and a title.

Now let’s create our new view Jade file. Right click on the views directory in WebStorm and select “New -> Jade File” and name it “users.jade” this is what it should look like:

extends layout

block content
    ul
        each user in users
            li #{user.FirstName} #{user.LastName}
                p(style="margin-left:5px")=user.Phone

Notice that we are again extending the main layout file and overriding the content block. Now things are getting a bit more interesting, we are looping through the users array passed into the jade template and for each element we’ll create an html list item with the user object’s FirstName and LastName as well as the Phone number.

Now that we’ve made these changes, we’re ready to see them in action, if you still have the node server running, you can simply click the “Rerun” button towards the bottom of the WebStorm IDE.



Once we’ve restarted the server, browse again to http://localhost:3000/users and we should see our new users list:



Now we are on our way towards making a full-fledged Node.js application using Express and Jade templates with the help of the WebStorm IDE.

Node.js Resources

Here are some great resources for you to learn more about the tools and technologies I’ve discussed:
Node.js
Express
Jade
Node Beginner Book
Getting Started with Node.js on StackOverflow

Sep 13

Chem Fight: js13KGames HTML 5 Chemistry Battle Game

Introducing Chem Fight

Chem Fight Logo

I’m currently putting the final touches on my latest HTML5 game: Chem Fight – the chemistry battle game. I started building the game about a month ago for the js13KGames competition. The goal of the competition is to build an HTML5 game in 13 Kilobytes or less when all the game’s code and assets are zipped up. Even though I am not very knowledgeable about Chemistry, I thought it would be fun to build a chemical-based game similar to the card game Magic the Gathering, where you would purchase elements from the Periodic Table and attack your opponent with them. Also, I thought that playing this game might be a good way to learn a little about chemistry, chemical compounds and reactions.

Game Mechanics

The game mechanics of Chem Fight are pretty simple, you are given a number of “Atom Bucks” which are used to purchase single atoms from the periodic table (i.e. you can purchase Helium [He] with atomic number 2, for two Atom Bucks). In each turn, players attack with a single atom, the defender is shown only the valence electron count of the attacking atom and is given a chance to choose a number of atoms for defense. If the attacking atom will bond with one or more of the defender’s chosen atoms, it is considered a successful defense and the defending player is given a number of Atom Bucks and Energy Units as a bonus. If there is no known possible compound between the attacking element and any of the defending elements, the attack is successful and the defending player is damaged based on the atomic number of the attacking element. The defender is penalized for any unbonded defending elements (this is to discourage players from just defending with every element they own each time). Energy units must be spent to regain the unused defending elements, if the player has insufficient energy, their health is damaged for the deficit. At the end of each turn, players earn a number of Atom Bucks and are given the chance to purchase more elements.

Simple Right? If you are done reading, try out Chem Fight now.

Helpful Hints

Here are some hints that might help you out:

  • Currently the game is broken up into 3 rounds, after each round the opponent gets a bit smarter and each player starts with more health, energy and atom bucks.
  • Noble gasses are special because they cannot be used for defense or defended against, but to purchase a Noble gas, energy must be spent.
  • Purchasing a variety of elements will help players defend against more possible attackers.
  • Typically, heavier elements and elements found in the middle of the Periodic Table (Groups 2 though 16) are better for attacking, and lighter elements found on the sides of the Periodic Table (Groups 1, 17, and 18) are better for defense.
  • Typically if the opponent is attacking with an element with 1 valence electron, you should be able to defend using a Hydrogen (because the 2s electron subshell will be filled)

Hope you enjoy playing Chem Fight, perhaps you’ll learn some chemistry while you are at it!

Aug 16

Learning the Dart Structured Web Language by solving the water bucket logic problem

The Water Bucket Logic Problem

You may have seen this logic problem: You have two buckets, one holds 3 gallons of water and one holds 5 gallons of water, there is also a source of water nearby. How do you measure out exactly 4 gallons?

I was recently asked to build a program that determines the solution to the problem in the least amount of steps (fills, transfers, dumps, etc…) with any given value for bucket sizes and goal fluid amount. I’ve been meaning to learn Google’s Structured web language: “Dart” so I figured I would kill two birds with one stone and see if I could solve the problem and learn Dart in the process.

Learning Dart

Over at the official dartlang website, there is a great “Tour of the Dart Language” page that does a good job describing the highlights of the language.

The Good

Since Dart has optional static types, classes, and generics and since you can compile Dart to JavaScript, it maybe a very good language to build large JavaScript projects with in the future.

One of the nice things in Dart is classes, and they have this nice syntactic sugar for assigning constructor parameters to members:

class BucketAction {
  String action;
  int fillLevelA;
  int fillLevelB;
  
  
  BucketAction(this.action, this.fillLevelA, this.fillLevelB);
}

You can also create class members as “final” so they cannot be modified after initialization, when you construct a class with final members you’ll need to use the “:” (colon) notation to specify final variable initialization though the initializer list:

class Bucket {
  final int capacity;
  int fillLevel;
  String id;
  
  Bucket(capacity, this.id) : capacity = capacity,
                     this.fillLevel = 0;
...
}

Dart also allows for declaration of generics, which makes it easy to show how you are using an array such as a list of strings (List<String>):

List<BucketAction> bucketActions = new List<BucketAction>();

Dart includes the ability to easily query the DOM like you would through jQuery, just import the html library at the top of your code and call the query method to get the appropriate HTML DOM element:

#import('dart:html');
...

void main() {
  
  CanvasElement canvas = query("#canvas");
  
  CanvasRenderingContext2D context = canvas.context2d;
  
  InputElement valueA = query("#valueA");
...
}
The Bad

Dart is not quite ready for prime time, and using it with your existing projects or other js libraries will be difficult for now since you have to port those libraries over to dart. The good news is that Google is actively developing the language and the tools and they also have plans to create a standards body once the platform has matured.

The Ugly

One thing I thought was especially cumbersome while programming in Dart is string concatenation with variables, instead of just using the “+” operator like you would in JavaScript you need to use this dollar sign/curly brace syntax for interpolation:

var st = 'Step: ${animationBucketActionStep + 1}';

Now the fun stuff: The Water Bucket Logic Problem

Just choose your parameters using the sliders and click the calculate button, the code will determine the best solution, and then draw the steps out on the canvas for you:

Source Files

GraduatedCylinder.dart – The full Dart source code, or you can download all the code including the Dart editor project files in this: GraduatedCylinder-DartProject archive.

May 07

Stratiscape – A layered approach to HTML5 Canvas drawing

When I created my first HTML5 game I was surprised that the canvas element in HTML5 didn’t support multiple layers that could be painted on independently. Independent stacked layers would help in many situations when animating only a portion of a game (like the main character) so that the system doesn’t have to repaint backgrounds or other elements that remain mostly static. One way to get around this limitation is to have multiple stacked canvas elements that are painted independently and serve the same layered functionality I wanted. There are some canvas libraries that already support layers, but many of them were very heavy and added much more functionality than I needed for my game. That’s when I decided to build Stratiscape, a simple HTML5 layered canvas library.

Using the Stratiscape library is straightforward, it is a matter of creating an instance of the main Stratiscape class, defining one or more drawn objects for your canvases and then adding those objects to a stratiscape layer, and finally setting up the drawing interval. This article will show you how to build a simple animated stratiscape page, in the background we’ll draw a blue rectangle, and in the foreground we’ll have some circles that will bounce around inside the rectangle.

To create an object of the Stratiscape class, we pass in a config object that defines how we want the layers created:

document.stratiscapeDraw = new Stratiscape({'containerId':'canvasContainer',
		'layers':[
			{'name':'canvasBackground', x:0, y:0, width:640, height:480, 'backgroundColor':'black'},
			{'name':'canvasForeground', x:0, y:0, width:640, height:480}
		]
	});

In our config object, one of the required properties is ‘containerId’ which should be the id of the element we want all of our generated canvas elements to reside, so we’ll want to make sure our page has a div with an id that we specified in our config object: “canvasContainer” like this:

Next let’s figure out what we want to draw and how we’ll draw it, to do this in Stratiscape, we define a subclass of the DrawnObject class and we should at least define two methods init and draw.

Here is a simple example of a “Rectangle” drawn object, the init function takes some position and size parameters as well as a couple of colors to use when we draw it.

Rectangle = Stratiscape.DrawnObject.extend({ //rectangle drawn object class

	init: function(x, y, width, height, fillColor, strokeColor) {
		this.x = x;
		this.y = y;
		this.width = width;
		this.height = height;
		this.fillColor = fillColor;
		this.strokeColor = strokeColor;
	},
	
	draw: function(ctx) {
	
		ctx.fillStyle = this.fillColor.toString();
		ctx.strokeStyle = this.strokeColor.toString();
		ctx.fillRect(this.x,this.y,this.width,this.height);  
		ctx.strokeRect(this.x,this.y,this.width,this.height);  
	}
});

Notice the draw method is passed a “ctx” object, which is the 2d context for the layer (canvas) that the Rectangle is a child of.

In order to make our stratiscape object actually draw, we’ll need to periodically call the main draw method on the stratiscape object like this:

window.setInterval(function() {stratiscapeDraw.draw() }, 1000 / 60);

Now all we have to add instances of our Rectangle Drawn Object to a layer of our stratiscape object and the library will take care of the rest.

document.stratiscapeDraw.getLayer('canvasBackground').addChild(new Rectangle(10, 20, 200, 150, "#369", "#FFF"));

The results of this are a bit uninteresting:

Let’s make our sample a bit more exciting and leverage the fact that we have two independent layers, lets make another class inheriting from drawn object, a circle:


Circle = Stratiscape.DrawnObject.extend({ //circle drawn object class

	init: function(x, y, radius, fillColor, strokeColor, velocity, angle) {
		this.x = x;
		this.y = y;
		this.radius = radius;
		this.fillColor = fillColor;
		this.strokeColor = strokeColor;
		this.velocity = velocity;
		this.angle = angle;
	},
	
	draw: function(ctx) {
	
		ctx.strokeStyle = this.strokeColor;
		ctx.fillStyle = this.fillColor;
		ctx.lineWidth = 1;
		ctx.beginPath();
		ctx.arc(this.x,this.y,this.radius,0,Math.PI*2,true);
		ctx.closePath();
		ctx.fill();
		ctx.stroke(); 
	}
});

Notice that we’ve given the circle class a velocity and angle, this is because we want to have our circles bouncing around our canvas layer. Let’s add an update method to the circle class that we’ll call repeatedly to change the circle’s location based on the angle and velocity.

    update: function() {
		var offsetX = 0;
		var offsetY = 0;
		if(this.velocity != 0)
		{
			offsetX = this.velocity * Math.cos(this.angle * Math.PI/180);
			offsetY = this.velocity * Math.sin(this.angle * Math.PI/180);
		}
		
		this.x -= offsetX;
		this.y -= offsetY;
		
		//check for collisions with our rectangle
		var top = 15 + this.radius, left = 20  + this.radius, bottom = 465 - this.radius, right = 620 - this.radius;
		if(this.x <= left) {
			this.x = left;
			this.angle += this.angle < 90 ? 90 : -90; 
		} else if(this.x >= right) {
			this.x = right;
			this.angle += this.angle > 180 ? 90 : -90; 
		} else if(this.y <= top) {
			this.y = top;
			this.angle += this.angle > 90 ? 90 : -90;
		} else if(this.y >= bottom) {
			this.y = bottom;
			this.angle += this.angle > 270 ? 90 : -90;
		}
		
		if(this.velocity <= 0)
			this.layer.removeChild(this);
			
		if(this.angle > 360)
			this.angle = this.angle%360;
		if(this.angle < 0)
			this.angle = 360 + this.angle;
	},

Now all we have to do is add some of these circles to our foreground layer and setup our interval to call the update method on each circle.

document.canvasForeground = document.stratiscapeDraw.getLayer('canvasForeground');
		
for(var i = 9; i >= 0; i--)
{
	var radius = (i + 1) * 5;
	document.canvasForeground.addChild(new Circle( 100 + radius, 75 + radius, radius, "#008000", "#FF0", 100/radius, (45 + (i * 90))%360));
}

setInterval(function() 
		{
			for(var i in document.canvasForeground.children)
			{
				document.canvasForeground.children[i].update();
			}
			document.canvasForeground.needsDisplay = true;//set "dirty" flag
		}, 1000/30);

Notice that after calling the update method on each of the foreground layer's children, I need to set the "needsDisplay" flag to true on the canvas layer. This tells Stratiscape that changes have been made to the layer and that it must be re-drawn. Stratiscape will set the needsDisplay flag for you whenever adding or removing a drawn object from the layer, however, because we are just moving our objects around we must explicitly tell the layer that updates have been made and that it should re-draw itself on the next draw cycle. We could repaint a simple scene like this as often as we like and we would likely not see any performance degradation. However, for large, complex scenes where repainting might be more intensive, only drawing when objects have changed is an important optimization to make games and animation run smoothly.

Here is our full simple sample in action:

Download the full source for this sample here: Stratiscape simple sample
Checkout the other Stratiscape library samples and download the full source from github here:
Stratiscape - Layered Canvas Library

Apr 29

HTML5 Canvas Drawing Speed Testing using Stats.js and jsperf.com

Lately I’ve been doing some performance testing of different canvas drawing functions, I specifically wanted to test the performance of drawing radial gradients vs. arcs and images.

To facilitate my testing I used Stats.js – a graphical performance monitor you can easily add to your sites to test milliseconds between javascript calls and frames per second.

Another great resource for testing javascript performance is jsPerf.com, to create a test you simply add your setup and teardown code and then specify the code you want to test the performance of.

You can see my Canvas Draw Tests jsPerf, it gives you a nice graph of the historic runs by browser.
Feel free to run your own test using your favorite browser.

HTML5 Canvas Drawing Speed Tests

I’ve also included the code and test page I wrote here so you can try it out for yourself and tweak the test for your own needs if you like.



Sorry your browser doesn’t support the HTML5 canvas!





Results

I’m not done with my tests, I’d like to do further investigating and compare the performance of drawing paths and other shapes as well. At this point, it seems image drawing is across the board faster. I was actually surprised that in some browsers it seems that drawing radial gradients is faster than drawing a filled circle (arc). As I work on my next HTML5 game these performance testing methods will be helpful to figure out how to keep the game running at high frame rates. Another good resource for tricks to keep canvas drawing as fast as possible is the very good tutorial over at HTML5 Rocks: Improving HTML5 Canvas Performance.

Apr 10

Creating a Hex Grid for HTML5 Games in Javascript

In my last post, I described how to do some of the calculations for determining the required measurements to build a hexagon. Today I’ll show you how to take that a step further and build a hex grid or game-field out of those hexagons.

Let’s start with the overview and pseudo-code for populating our grid of hexes.

Overview/Pseudocode:

  1. Populate each row while we have vertical space on the canvas
  2. After each hex (column), increment the x direction by the width of the hex + the side length until we run out of horizontal space on the canvas
  3. Every other row must be offset in the x direction by the width of the hex minus the side length divided by two
  4. After each row increment the y direction by 1/2 the height of the hex

Simple version of JavaScript code:

HT.Grid = function(/*double*/ width, /*double*/ height) {

this.Hexes = [];

var row = 0;
var y = 0.0;
while (y + HT.Hexagon.Static.HEIGHT <= height)
{
   var col = 0;
   var offset = 0.0;
   if (row % 2 == 1)
   {
      offset = (HT.Hexagon.Static.WIDTH - HT.Hexagon.Static.SIDE)/2 + HT.Hexagon.Static.SIDE;
      col = 1;
   }
   
   var x = offset;
   while (x + HT.Hexagon.Static.WIDTH <= width)
   {
      //first parameter of the hexagon constructor is the hexId
      //   which we'll discuss more later
      var h = new HT.Hexagon(null, x, y); 
      this.Hexes.push(h);

      col+=2;
      x += HT.Hexagon.Static.WIDTH + HT.Hexagon.Static.SIDE;
   }
   row++;
   y += HT.Hexagon.Static.HEIGHT / 2;
}

};

That is pretty straight-forward, but before we have a usable grid we may want to add a few more things. If you notice my Hexagon constructor has an "Id" member, the purpose of the Id is to give each hex a unique string identifier, this makes it easy to reference each hex, either programmatically, or for debugging. I like to give my hexes a Letter prefix based on the row plus a number based on the column, but you can do whatever works for you.

Here is my simple function for getting the hex identifiers I want:


HT.Grid.Static = {Letters:'ABCDEFGHIJKLMNOPQRSTUVWXYZ'};

HT.Grid.prototype.GetHexId = function(row, col) {
	var letterIndex = row;
	var letters = "";
	while(letterIndex > 25)
	{
		letters = HT.Grid.Static.Letters[letterIndex%26] + letters;
		letterIndex -= 26;
	}
		
	return HT.Grid.Static.Letters[letterIndex] + letters + (col + 1);
};

Hex Distance:

Finally, since it is common in games to need to figure out the distance between two hexes, we probably want a function that takes two hexagons and returns a distance. To facilitate this, we'll need to assign some coordinates to each of our hexagons that will make it faster and easier to calculate distances when necessary. James McNeill has a very good post on his PlayTechs blog about hex grids where he describes a coordinate system for hex grids, and how to use that coordinate system to find distances between hexes.
Basically, instead of a coordinate system based on the rows and columns, we have columns (shown in green), and diagonal rows (shown in red). Once we have assigned coordinates to our hexagons as shown, we can use the following equation to calculate the distances between two hexes:
\frac{|\Delta x| + |\Delta y| + |\Delta x - \Delta y|}{2}

Here is my JavaScript function that returns the distance between two hexes in the grid:

HT.Grid.prototype.GetHexDistance = function(/*Hexagon*/ h1, /*Hexagon*/ h2) {
	var deltaX = h1.PathCoOrdX - h2.PathCoOrdX;
	var deltaY = h1.PathCoOrdY - h2.PathCoOrdY;
	return ((Math.abs(deltaX) + Math.abs(deltaY) + Math.abs(deltaX - deltaY)) / 2);
};

Note: I'm using the PathCoOrdX and PathCoOrdY members of my Hexagons in the above function, which I populate in my full version of the Grid constructor, but I won't go into how I do that in this post, basically the PathCoOrdX comes from the column variable, and PathCoOrdY is populated in a second pass. You can download the full Grid.js code to see the exact method I use.

The Fun Part:

I've put together a simple form and canvas, similar to what I did in my last post, so that you can see the Hex Grid in action, and play with the parameters. I've also added another option that allows you to switch the hex orientation that you can play with.



Orientation:

Hex Based on Side Length

Side Length (z):

Ratio of Width:Height (4:3, r = 1.333), (2/√3, r = 1.1547...)

Hex Based on Width and Height

Width:

Height:

Source Files

Grid.js - The full source code for the grid class, or you can download all code for these Hexagon articles in this GitHub repo: HexagonTools.

Apr 05

Fun with Hexagon Math for Games

Hexagons are great for game grids because, compared to the standard square grid, the distance from the center of a hex to any adjacent hex is the same (assuming you have a “Normal” hex with width to height ratio of 2:√3). In a square grid, moving from one square to an adjacent diagonal square is further away then moving horizontally or vertically to an adjacent square.

The mathematics and programming of Hexagons for a game grid can get a bit more complex than the math and programming for squares. You have to create polygons instead of rectangles, when you create a grid of hexagons you have to offset each row by half the width of the hex, pathfinding can be more complex, and hit detection is more complex.

There are some choices you have to make when creating your hex grid:
How big are my hexagons going to be?
Are my hexagons going to be symmetric? Meaning the width is equal to the height (ratio 1:1, or square). Or will I choose some other ratio of width to height for my hexagons? A “Regular Hexagon” is quite common since all the angles and side lengths are equal (consequently the width to height ratio of regular hexagons turns out to be 2/√3).

The key variables we need to know before we are ready to draw a hexagon are:
Width (w), Height (h), and side length (z). We will also define x and y to be the other sides of the triangle made using the top left angled side as shown in this image:

Width and Height are known

Let’s say we know we want our hexes to be a certain size, so we know the width and height (maybe 100×100), but we also need to know z, the length of each side.

We know from the Pythagorean theorem that we have:
x^2 + y^2 = z^2

Also, from the above image you can see that there is a relationship between x, z and the width, and y and the height, specifically:
2x + z = w
and
2y = h

Now we should be able to solve for z (our side length).
x = \frac{w - z}{2}
y = \frac{h}{2}
Plugging x and y back into pythagoras we get:
(\frac{w - z}{2})^2 + (\frac{h}{2})^2 = z^2
After expanding and simplifying:
-3z^2 - 2wz + h^2 + w^2 = 0
Remember that w and h are constants we have already chosen, so we can solve this using the quadratic formula:

Quadratic formula
x=\frac{-b \pm \sqrt {b^2-4ac}}{2a}
where
ax^2 + bx + c = 0

In our case:
a = -3
b = -2w
c = h^2 + w^2
Thus, to get z (the hex side length from the width and height we can use this formula:
z=\frac{2w - \sqrt {4w^2+12(h^2+w^2)}}{-6}


Side Length and Ratio are known

Now let’s say instead of knowing the width and height for our hexagons, we know we want a certain side length z (say 100) and a certain width to height ratio r (say of 4:3, or 1.3).

We can still use our formulas from above, pythagoras and our formulas relating x, y and z to the width and height. Now since we don’t know the exact width and height, we’ll substitute that ratio (r) variable for w and h:

r = \frac{w}{h}
And using our equations from above:
r = \frac{2x + z}{2y}
Solving for y:
y = \frac{2x + z}{2r}

Now we’ll substitute our value for y into pythagoras:
x^2 + (\frac{2x + z}{2r})^2 = z^2

After simplifying and turning this into quadratic form:
(\frac{1+r^2}{r^2})x^2 + \frac{z}{r^2}x + (\frac{1-4r^2}{4r^2})z^2 = 0

Now for the quadratic we have:
a = \frac{1+r^2}{r^2}
b = \frac{z}{r^2}
c = (\frac{1-4r^2}{4r^2})z^2

If we substitute this into the quadratic, it looks pretty ugly:
x=\frac{-(\frac{z}{r^2}) + \sqrt {(\frac{z}{r^2})^2-4(\frac{1+r^2}{r^2})(\frac{1-4r^2}{4r^2})z^2}}{2(\frac{1+r^2}{r^2})}


Other Great Hex for Game Programming Resources:

Amit Patel’s Thoughts on Grids
PlayTechs: Programming for fun Hex Grids
Hexnet.org’s Introduction to Hexagonal Geometry


Can you do this for me? My HTML5 Hexagon Tools

If you are like me, you skim over all these equations and just want to get to the good stuff, like concrete examples. So I’ve put together a simple form to do these calculations for you using JavaScript. Once you fill out the form you should see a visual representation of the computed hexagon, drawn on a canvas (assuming you have an HTML5 enabled browser).


Hex Based on Side Length

Side Length (z):

Ratio of Width:Height (4:3, r = 1.333), (2/√3, r = 1.1547…)

Hex Based on Width and Height

Width:

Height:

Oops, your browser doesn’t support the HTML5 canvas tag!

Source Files

If you want to take a look at the JavasScript for this here are my source files, you are welcome to use these for your own projects:
HexCalcs.js
HexagonTools.js

HexCalcs.js is mostly just for parsing the forms above and performing the math described in this post. HexagonTools.js defines a Hexagon class that defines all the points in a hexagon and defines a draw method for the canvas.

You can also find the entire HexagonTools library code on GitHub.

In a future post I’ll show how to use the Hexagon class to build a Hex grid.

Older posts «