Limitless Life

This is the second time I've implemented John Conway's Game of Life in canvas. The first version works well but was implemented as a pretty naive first pass. With this second version, I wanted to explore a few things

• making the game board stored much more sparsely
• pushing the browser to handling much more data
• moving rendering remotely allowing for multiplayer participation

For this part, I've achieved the first bullet point and am looking at the life wiki for more inspiration.

Sparse Representation

An easy, but naive way to implement the game of life is to use an array or array of arrays to store the game board. For example, a 4x4 board could be stored as

[
  [0, 0, 0, 0],
  [0, 1, 0, 0],
  [0, 1, 1, 0],
  [0, 0, 0, 0]
]

The matrix locations map on to cells on a grid, so array[0][0] represents the top left most cell in a grid.

In order to calculate the next frame, the following pseudocode would suffice

for each row in array
  for each cell in row
    determine life in this cell based on rules

This leads to an O(n) complexity as we visit every cell to calculate the next game state. What's nice here is that we have an O(1) lookup time for neighbors and the number of neighbors to be examined is fixed, so that complexity disappears behing the loops over the game state. The arrays are consuming a lot of unused memory. Depending on the language, storing nulls instead of 0 may help, but we can do better.

The Game Belongs to the Living

Imagine our game board is unbounded. There is a center (0, 0) cell, but instead of having "walls", the game board stretches on to infinity in each of the four directions in 2 dimensions. We can preserve a worst case runtime for calculating next game state with O(n) complexity, but the worst case will be when every cell is populated. We shouldn't expect this to happen often. In general, the complexity will be O(m) where m is the number of live cells plus 8 neighbors which will also need to be checked for life.

Alter our grid store to a dictionary of sets. Access to a key in the dictionary is O(log n) and checking if a key is populated in a row is likewise O(log n). To calculate the next game state, create a temporary set of tuples of cells to check for new life. This set includes all currently populated cells and each of the neighbors of those cells. Our pseudocode now looks like this

for each row in array
  for each cell in row
    for each of the 8 neighbors of cell and the cell itself
      determine life in this cell based on rules

Navigating an Infinite Grid

How do we render an unbounded grid? We must establish a classic MVC style separation of concerns.

There are three main components here

• Cell: An single cell which contains some about of information
• View: The current portions of the world's cells which are being rendered
• World: The infinite grid which mostly exists virtually an which advances steps in a game

The advancements we make here (from version 1) is to separate the world from what is being rendered, this allows the view to scroll and zoom during smoothly without affecting the calculation of the frame. See this portion of code

Next Steps

There are noticeable improvements (as yet unmeasured) in render times for this board as the render complexity is bounded by the number of living cells instead of constant for the board size. We're still doing rendering on the main CPU, though. In some circumstances, we can use the GPU instead which might give us an incredible increase in performance.