HTML 5 Game of Life – Web Workers

I like JavaScript.  I admit it.  I used to hate it, but then things changed.  What changed?  A few months back I decided to take a crack at learning some of the new HTML 5 APIs by implementing John Conway’s Game of Life in JavaScript using web workers and a 2D canvas tag for display.  The end result was a lot of fun and a pretty cool pet project: HTML5-GoL.

Game Of Life: Devs-In-A-Cabin & STL Code Retreat & HTML 5

Screenshot of HTML5-GoL animation

John Conway’s Game of Life is a simple algorithm for cellular automaton where each new generation can be computed by calculating the number of neighbors each cell has in the previous generation.  A living cell will stay alive if it has 2 or 3 neighbors (diagonals count).  A dead cell will spawn new life IFF it has exactly 3 neighbors.  Simple.

A few months back Amos King got a number of developers together for a weekend of hacking and talking shop at a cabin near St. James, MO (#devsinacabin).  The idea was for every developer come prepared to give a quick talk on something … I hacked together the basics of this HTML5 implementation the day of and presented that night.

Not long after, Mario Aquino and James Carr put together a Code Retreat here in St. Louis where pairs of developers repeatedly tried to implement the Game of Life in many different languages and styles in 40 minute chunks.  I cleaned up my code a bit before hand to show one implementation that actually had graphics (I cheated, I know). FYI both Mario and James have put together JavaScript implementations of GoL also.

The main goal of the project was to teach me some of the new HTML 5 based JavaScript API changes that everyone has been talking about (not quite the multi-media extravaganza of The Wilderness Downtown, but decent).  The HTML 5 spec is a HUGE collection of new APIs and markup changes that are aimed at solving a lot of common web problems in a standardized way.  One of the best examples of the need for standardization can be seen in the Apache Shindig project.  While hacking my way through their internal pub/sub code I found a huge blocks of code handling communicating between the container and a given gadget depending on the browser hacks needed to talk back and forth.  For HTML 5 compliant browsers this was a single postMessage function call.

Without too much trouble I was able to put something together that leveraged web workers for calculating each new “world” state outside of the main UI event loop and a simple 2D canvas tag to display all of the live and dead cells. There are a ton of other HTML 5 features I would love to add (mouse interaction, local storage and loading of customer patterns, etc), but those are for another day.  For now the code is up on GitHub with a nice home page including an example implementation (JSpec tests for all of the actual game logic).

Click the above picture to go there and see it in action
and keep reading below to find out how I used web workers to offload my hard computations…

Web Workers: Multi-Threaded JavaScript

The event oriented nature of JavaScript can be a nice feature and a huge pain int he a$$.  Simple button click events and AJAX calls are easy, but try to do any significant calculations and you quickly run into UI problems.  Trying up your one and only JavaScript thread on an animation loop or complex parsing task means your UI becomes unresponsive and sluggish.  Take the time to break all of your work into small chunks and hundreds of setTimeout and setInterval calls and you might go cross-eyed.  Enter Web Workers.

Web Workers are separate JavaScript threads that can be spawned by the main UI thread and will download and execute a specified .js file from the same domain.  The UI thread and the new worker can communicate by asynchronous message passing of String values (and vanilla JSON objects, although this isn’t technically in the spec).  In addition, web workers can’t manipulate the DOM or anything on the page directly.  So what can they do?  They can run in parallel of your UI code and leverage any other normal native API that your UI code can (web sockets, XMLHttpRequest, local storage, etc).  This means that you can offload large computations and server communication to the second thread and leave your main thread for dealing with the user and the DOM.

*** From several soures and the spec itself, it sounds like Web Workers are not designed to be cheap to create and start.  This doesn’t mean that implementations have to make these expensive operations, but the idea is that you won’t create hundreds of these.  Instead create one or two and reuse them.  I noticed that besides the extra network hits to grab the actual code to run int he worker, there was occasionally a noticeable pause as the worker thread was spawned.  Since the UI thread will have continued on during this time, it is probably a best practice to have the worker and UI threads coordinate their work with some “I a alive and ready” type messages. ***

In the Game of Life code I wanted to use a Web Worker to do the generation-to-generation calculations since I figured this would be the bulk of the processing time and my naive 2D array implementation required a fair amount of calculations for large “worlds”.  The gol-client.js file is the jumping off point.  The main chunk of code is executed after the DOM is loaded and creates the necessary objects used to draw on the canvas and creates a new Web Worker loaded with gol-worker.js.

var message_actions = {
	log: function(message) {
	  console.group('Client Received Message');
	  console.log( message );
	  console.groupEnd();
	}
}

$(function() {
	var context = document.getElementById('gol_canvas').getContext('2d')
	var canvas = new GoLCanvas(context, 50, 401)
	canvas.clear()

	message_actions.draw = function(delta) {
		canvas.draw(delta)
	}

	var worker = new Worker('./lib/gol-worker.js')

	worker.addEventListener('message', function (event) {
		message_actions[event.data.action](event.data.data)
	}, false);
})

First thing first, the worker loads up a secondary library file containing the actual Game of Life logic using the importScripts(”) command.  The worker is the only one that actually knows about the Game of Life algorithm and matrix (“world”).  After creating a new matrix it randomly seeds the world and kicks off a timer to calculate a new generation each X ms and post the changed positions back to the main UI thread.

importScripts('gol.js')
postMessage({ action: 'log', data: 'Starting' })

for(var x = 0; x < SIZE; x++) {
  for(var y = 0; y < SIZE; y++) {
    if(Math.floor(Math.random() * 2) == 1) {
      matrix.spawn(x, y)
    }
  }
}

setInterval(function() {
  postMessage({ action: 'draw', data: matrix.ticktock() })
}, 200)

*** Initially I assumed that the calculations for each new board would be time consuming and I would be able to run them continuously and post back changes to the UI thread after each one without any waits.  Turns out it is fast and spamming messages to the UI thread can cause some hiccups in performance more than just waiting.  I haven’t had a chance to examine what really happened but in Chrome on Windows I was seeing some really strange behavior when I flooded the UI thread w/ messages too fast.  I am not sure if their is a message buffer I was overflowing or if it was just choking on the throughput. ***

All in all workers are a piece of cake and really helpful.  I noticed some performance differences between Firefox and Chrome (hint Chrome was faster) but I can’t blame one particular thing or another.  It might just be my crap code.

Along with offloading large processing tasks web workers can be used for background server communication, as a proxy for helping multiple client windows to talk to each other, persistent data stores, and common processors that can have life cycles beyond the scope of a single page but across multiple requests for a whole web-app (shared web workers).

>> Another post discusses some of my findings w/ using the Canvas tag to display the world … …

Resources

• Homepage of my code (hosted on GitHub, includes running example)
• HTML5Test.com (great resource for finding out if your current browser is “modern” or not)
• Bocoup web log (lots of good articles)
• Web Worker spec (includes some nice examples)
• HTML 5 spec from WHATWG
• Mozilla Web Workers tutorial
• The Wilderness Downtown and Google’s Chrome Experiments (inspiration)