Image of GOLEM running the Acorn seed

G.O.L.EM. (site; code), hereafter called Golem, was a recent project of mine to build a Game of Life implementation in Clojurescript. This is my third Clojurescript project (coming after shboard and my ill-fated singularity chess game).

Architecturally, Golem is loosely based on the re-frame model of a global app-db state. However, it differs in that there are no “effects” or “interceptors” because interceptors (i.e. middlewares) are not really necessary for an application of this size.1 Pure Reagent already provides tools for tracking and responding to state changes. Also, I usually prefer to stay away from “frameworks” for side projects unless my goal is to learn that framework specifically.

The re-frame README is so excellent that once it’s been read, actually using the framework feels redundant.

One concern I had with this project was ensuring it could “step the game” — calculate and redraw the next state of the board — fast enough. Some common Game of Life algorithms were considered, but they didn’t seem to fit my use case:

  • Hashlife and other “time-compressing algorithms” were rejected because they don’t calculate each intermediate state. We need those intermediate states, because we intend to render them to the screen. So the benefits of using these algorithms are effectively negated.
  • Bitfields were rejected because I wanted an “infinite” board that the user could pan/zoom around. As far as I can tell, bitfields work best when at least one dimension of the board is fixed.

In the end, I went with the simplest option I could think of: the Golem “board” is, conceptually, a plane of tiles, centered on 0,0 and extending for infinity2 in every direction. Living tiles are tracked in a HashSet of [x y] coordinate pairs. All coordinates not present in that set are assumed dead. The step method accepts a current_board — a HashSet for the currently rendered board — and returns a new HashSet to be rendered for the next frame. It’s basically a Clojure version of the following imperative pseudocode:3

new_board = empty set;
for each tile [x y] in current_board:
  for each tile' [x' y'] in 3x3 block of tiles centered on [x y]:
    if tile' is in current_board and tile' has 2 or 3 living neighbors:
      add tile' to new_board
    if tile' is not in current_board and tile' has 2 living neighbors:
      add tile' to new_board
return new_board

The upside of this approach is that there’s almost no incidental complexity in the code expression of the algorithm. The majority of lines reflect the rules of the Game itself, not implementation bookkeeping.

The downside is performance. It uses many objects, is heavy on GC, and can slow down when rendering boards with lots of tiles. I planned to allow the user to increase the tick rate to 60fps, but stepping the game using this algorithm (as I’ve implemented it) takes around 60-100ms per update for very complex boards.

I’m sure additional performance is possible, but the user experience is good enough at lower FPS that I’m satisfied — for now. If I were doing this again, I would probably use a bitmap (or a flat array of booleans, which would require no array resizing or object creation during the step logic).

Originally, core.spec was used for validating state changes. But unsurprisingly, it proved a major performance drain, so it was disabled for production builds. Golem running in development mode has significantly less FPS for this reason.

The UI design was also an exercise in compromise. For example, not all the tiles can necessarily fit into the user’s window. If patterns grow large, they can continue to evolve off the edges of the visible screen. Although invisible, they’re still evolving, and might eventually circle back around into view again.

This is possible because the user only sees a portion of the whole board at once, in Golem referred to as the viewport. Users can move their viewport around, panning and zooming to view areas of interest, like with Google Maps.

Unlike Google Maps, though, Golem offers no drag-to-pan, pinch-to-zoom, or other fancy usabilities. Instead, you use a “control panel” of buttons to pan and zoom the viewport, as well as to adjust the FPS and control time. This was much easier to implement and provides enough utility for basic experiments.

The Golem board is drawn using the HTML Canvas API. Canvas was chosen over plain HTML or SVG because it seemed to promise the best performance, and simplest handling of pan/zoom movements.

My initial approach was similar to what I’ve done in my past in-the-browser Game of Life implementation.4 Each tile was drawn onto the canvas as a rectangle, which may be filled with black, or may be transparent.

I quickly realized a major downside of this approach: the board “grid”, which never changes, was being redrawn on every frame. The redraws were costly: over 20ms in many cases. So I broke the single Canvas in twain: one sub-Canvas would hold the grid, and would only be redrawn on pan/zoom. The other sub-Canvas would hold black squares representing live tiles. Only the live-tile canvas would have to be redrawn every frame.

Additionally, after learning a bit more about Canvas, I realized it was rather wasteful to trigger separate stroke/fill operations per tile. So I altered both Canvas redraw steps to just build a single giant path and then draw it all at once, effectively changing this:

for (const tile of board) {
  canvasCtx.fillRect(x, y, width, height);
}

Into this:

canvasCtx.beginPath();
for (const tile of board) {
  canvasCtx.rect(x, y, width, height);
}
canvasCtx.fill();

With those optimizations in place, per-frame redraws take about 1.5 ms (with about 1ms jitter).

In the end, it was much easier to optimize the redrawing/rendering stage. Compared to the time cost of calculating the next board state, the Canvas redrawing might as well be a rounding error.

Footnotes

  1. At time of writing, 614 LOC ClojureScript and 82 LOC CSS. ↩

  2. Actually constrained to 1,000,000 tiles in every direction. My hope is that this is big enough for anybody.(tm) Growth-without-bounds proved problematic in some cases. e.g. if you create a glider gun, then went AFK, gliders were infinitely spawned and performance could suffer. ↩

  3. See: https://github.com/luketurner/golem/blob/master/src/golem/board.cljs#L73 ↩

  4. Once used as a dynamic heading for my blog; available on Github at: https://github.com/luketurner/blog/blob/4a73854fa265d2aeb752c53f8854a5ce09e0a28f/assets/conway.js ↩