Update: This post now has a part 2, in which I make some changes to increase
the board's performance. Read that here.
Lately in doing research on WebAssembly I've been looking around for examples
of things implemented in it. In this search I've come across several blog
posts that claim to be Conway's Game of Life in WebAssembly, but upon opening them,
I find they are actually just Rust!
Now I mean no shade towards Rust or those posts (and if that's what you're
curious about doing, I recommend the fantastic Conway's Game of Life
guide from Rust and WebAssembly) but around here I take pride in being
accurate to the point of pedantry. Rust is very much not WebAssembly, and
despite how much we front-end developers may get them conflated in our heads,
this feels like a distinction worth making!
So of course I knew what I had to do . . .
Welcome to Conway's Game of Life, actually implemented in WebAssembly:
What you're looking at here is Conway's Game of Life where all of the game code
is written in pure, raw, not-a-compiler-in-sight WebAssembly. Its performance is
pretty comparable to the Rust versions I've found, and I'm glad to say the code for it isn't
even that much of a mess!
Let's dive into how it works together, shall we?
Overview
As with most things in wasm we need to decide ahead of time what we are going
to implement directly in it, and what things are going to stay in the Javascript
part. I went with implementing the core game logic in wasm, leaving the initialization
and display code in JS.
I chose the first because I didn't want to have to deal with getting a float
value back from Math.random() in wasm, and the second because DOM manipulation,
canvas, and WebGL are all a bit of a pain to do manually from WebAssembly.
For convenience in this implementation I am using a byte per cell. Packing a bit
per cell into less memory space would be great, but I'm trying to keep it
relatively simple at first. I'm planning to revisit that in a later post though.
Code samples
For now, let's look at a few selections from the code (links to full source will be
at the bottom of the page).
I start the wasm module out with 1 page of memory (64 KiB), and define global
variables for the board dimensions, the length of each board buffer (in bytes),
the locations of each buffer, and which one is currently selected.
You can see that each of these gets initialized in the next function:
In the case that $growMemoryForBoards fails it will crash the WebAssembly
module, but considering I don't have a backup plan for how to make do with
less memory, that's acceptable to me.
Manipulating the board
Next let's check out some of the basic board manipulation functions that our
Javascript code calls during initialization and display:
As you can see both rely on another function called $getIndexForPosition, check
its return value to make sure it didn't give -1, and then add that position to
the current board pointer. Not too bad so far!
That helper function $getIndexForPosition is also relatively simple:
It again does some basic bounds checking, then some math with the board with,
row and column. Generally this all matches so far to how you might implement
this in any other language.
Updating the board
Okay so this is where stuff starts to get a bit messy. WebAssembly ostensibly
has loops, but they're really more just a conditional jump. So the main function
for updating the board (which has to iterate through every position) gets to
be a bit verbose:
(func $tick (export "tick")
(local $row i32)
(local $column i32)
(local $value i32)
i32.const 0
local.set $row
loop $rows
;; start at the beginning of a row
i32.const 0
local.set $column
;; for every column in the row
loop $columns
;; compute new value
local.get $row
local.get $column
call $getNewValueAtPosition
local.set $value
;; place in next board
call $swapBoards
local.get $row
local.get $column
local.get $value
call $setValueAtPosition
call $swapBoards
;; increment column
local.get $column
i32.const 1
i32.add
local.tee $column
;; loop back if less than width
global.get $boardWidth
i32.lt_s
br_if $columns
end
;;increment row
local.get $row
i32.const 1
i32.add
local.tee $row
;; loop back if less than height
global.get $boardHeight
i32.lt_s
br_if $rows
end
;; swap to the new board
call $swapBoards
)
(func $tick (export "tick")
(local $row i32)
(local $column i32)
(local $value i32)
i32.const 0
local.set $row
loop $rows
;; start at the beginning of a row
i32.const 0
local.set $column
;; for every column in the row
loop $columns
;; compute new value
local.get $row
local.get $column
call $getNewValueAtPosition
local.set $value
;; place in next board
call $swapBoards
local.get $row
local.get $column
local.get $value
call $setValueAtPosition
call $swapBoards
;; increment column
local.get $column
i32.const 1
i32.add
local.tee $column
;; loop back if less than width
global.get $boardWidth
i32.lt_s
br_if $columns
end
;;increment row
local.get $row
i32.const 1
i32.add
local.tee $row
;; loop back if less than height
global.get $boardHeight
i32.lt_s
br_if $rows
end
;; swap to the new board
call $swapBoards
)
The $swapBoards function here is not that important to look at, it just
changes the current board flag so that $getBoardPtr returns the correct one.
I am kind of annoyed that I have to swap the board back and forth all the time,
but we'll see if that becomes an issue later.
But what's this $getNewValueAtPosition function? Let's have a look at that!
This is (effectively) an unrolled loop. I could make this code shorter
by un-unrolling my loop, but I couldn't find a way to do that which didn't
immediately result in more instructions being run overall, so for the moment
I'm leaving it like this.
But once you know what each chunk is doing, yeah it's pretty simple! Each of the
$getValueAtPosition calls adds either a 0 or a 1 to the stack, and then we add
all of those up, store it in a variable, and check it against our various possible
outcomes.
Not that bad really, it's just rather verbose.
And the glue
Lastly let's look at some of the JS that ties this together. I'm not going to
look that closely at the bit that loads the WebAssembly and initializes the
module - I assume most (sane) folks are using a bindings generator or bundler
or something else that does that for them. But let's look at the board initialization
and drawing code.
Starting with the board initialization, you can see it's rather short:
Oh the pleasures of a high-level language - the conciseness is just lovely isn't it?
And hopefully you can see why I didn't want to import Math.random() into my
WebAssembly - then I'd have to deal with floats, and more iteration, and it'd just
not be fun.
This is a pretty simple use of the <canvas> element, I think maybe in the
future if I want to optimize this I'd probably look into only updating the
changed cells or something like that, so that it doesn't need to redraw
the entire board each time. But on anything up to about a 400x300 grid
this was staying at roughly 5ms per frame on my machine, which should be
suitable for keeping about 60 frames per second - particularly if I can
optimize the board update function a bit as well.
Final thoughts
So there it is! A Conway's Game of Life implementation actually done in
real WebAssembly. I hope you enjoyed this brief look into what goes into
writing this sort of algorithm in the language, and more than anything I
hope you appreciate your compilers for all the fantastic work they do for
you.
As promised the full source files used in this post are linked below.