How to implement a 2D Cellular Automaton in JavaScript?

Question

So far I have this:

const rand = (min, max) => Math.floor(Math.random() * (max - min + 1) + min)

// rule:
  // if an even number of nodes are touching
  // the center node, then flip
  // else skip.

// rule:
  // for the start nodes (top row),
  // they are randomly turned on and off.

const cellularAutomaton = [
  [0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0],
]

const update = () => {
  let int = rand(0, 7)
  let row = cellularAutomaton[0]
  row[int] = row[int] ? 0 : 1
  // now, how to update the remaining rows?
  for (let i = 1, n = cellularAutomaton.length; i < n; i++) {
    row = cellularAutomaton[i]
    for (let k = 0, m = row.length; k < m; k++) {
      let neighbors = surrounding(i, k)
      let count = sum(neighbors)
      if (even(count)) {
        row[k] = row[k] == 1 ? 0 : 1
      }
    }
  }
}

const even = value => value % 2 == 0

const sum = neighbors => {
  let sum = 0
  let u = 0
  while (u < 3) {
    let v = 0
    while (v < 3) {
      let value = neighbors[u][v]
      if (value != null) {
        sum += value
      }
      v++
    }
    u++
  }
  return sum
}

const surrounding = (row, column) => {
  let prevRow = cellularAutomaton[row - 1]
  let nextRow = cellularAutomaton[row + 1]
  let left = cellularAutomaton[row][column - 1]
  let right = cellularAutomaton[row][column + 1]
  let neighbors = []

  if (prevRow) {
    let a = prevRow[column - 1]
    let b = prevRow[column]
    let c = prevRow[column + 1]
    neighbors.push([a, b, c])
  } else {
    neighbors.push([null, null, null])
  }

  neighbors.push([left, null, right])

  if (nextRow) {
    let a = nextRow[column - 1]
    let b = nextRow[column]
    let c = nextRow[column + 1]
    neighbors.push([a, b, c])
  } else {
    neighbors.push([null, null, null])
  }

  return neighbors
}

let i = 0

const watch = () => {
  i++
  if (i == 100) {
    clearInterval(interval)
  }
}

const render = () => {
  let out = []
  let a = '■'
  let b = '□'

  for (let i = 0, n = cellularAutomaton.length; i < n; i++) {
    row = cellularAutomaton[i]
    let outrow = []
    for (let k = 0, m = row.length; k < m; k++) {
      let value = row[k]
      if (value) {
        outrow.push(a)
      } else {
        outrow.push(b)
      }
    }
    out.push(outrow.join(' '))
    out.push('\n')
  }

  console.clear()
  console.log(out.join(''))
}

const draw = () => {
  update()
  watch()
  render()
}

const interval = setInterval(draw, 1000)

Am I doing this correctly? I have never seen an implementation of cellular automata and so don't know if there is a more efficient way of accomplishing it. Please let me know how to improve this. What can be done differently or more effectively? In particular, finding the neighbors I'm not sure if I've done that well. Also, what do 2D cellular automata typically do on the edges? Do they wrap them to the other side? So everything has the same number of neighbors? I'm not sure exactly how the theory maps to code, and if in theory the neighbors number is the same for every box.

Note: I have in this CA a random "seed" in the first row to initialize values. That is by design, I want to "play a beat to the automaton" essentially, and this random function seed is just a pretend beat (without getting too fancy for this post).

As a side note, if you have any suggestions on inspiration on the types of rules that can be created, please leave a comment, I would like to build arbitrary CAs and not sure where to start.

Answer 1

Review

• Use semicolons

• Use 0 based indexing. Your rand function does not need the + 1

• Use const for values that do not change. For example in function surrounding all variables can be constants prevRow, nextRow, left, right, neighbors, a, b, and c

• In performat code avoid conditional statements and expressions, when possible.

  You have the line row[k] = row[k] == 1 ? 0 : 1 The value of row[k] will only ever be 1 or 0. The ternary is slower than adding 1 and bitwise AND 1. The line row[k] = (row[k] + 1) & 1; will flip the value between 0 and 1

Game of Life

Updating

In the game of life there are two states, the previous state and the new state. You are mixing the two by writing the new board state into the same array as you read the previous board state.

This means that the birth and death of cell to the left and in the row above will be incorrectly counted.

The correct method is to double buffer the board state.

Two arrays, one holds the previous state of the cells and one the new state. Each tick of the game of life you swap the two arrays.

Count neighbors cells from previous state and update the current state. Render the new state and swap the buffers, The current state becomes the previous, and the old previous state is used to set the next new state.

See rewrite

Edges

There are as many strategies for edges as you may wish to imagine.

There is no right or wrong method. The original Game of Life I believe was imagined on an infinite board thus edges are not considered.

Using edge warps (use cell on opposite edge) would most closely match an infinite board.

If you use bounded edges then cells outside the grid are configured to a state that does not generate or kill cells on the edge.

Performance

• Array indexing has a little overhead, reducing the number of times you index into an array will reduce this overhead.

  Rather than use a 2D array you can use a 1D array and reduce array indexing.

• Your method of counting neighbors i s horrifically inefficient. You create 3 new arrays, then iterate each, testing for not null to count living cells.

  You need only count the state of the cells, there is no need to create a copy of each cell. See Rewrite

  The example uses two lookup arrays to provide offsets to neighbor cells. The board array is a 1D array and only cells at the edge need to compute the cell index from x and y coordinates.

• The console is not a very fast method of displaying data. In this case you can use a canvas bitmap and write cells directly to pixels. See rewrite.

Rewrite

The rewrite implements a Conway's Game of Life 160 by 160 cells displaying the result in a canvas element.

Notes

• It is written to be performant, however it can be a lot faster (using single thread JS can do million + cells) but the code starts to get very complicated due to the optimizations.

• Edge cells are handled differently than the rest and use the value on the opposite edge to count as neighbors.

• The update function returns a count of living cells. This is used to reset the game when all cells are dead.

• Special Note Count optimization

  When counting neighbors the loops exits when the neighbor count equals 4 as the rule set has the same outcome for counts 4,5,6,7,8 so there is no point counting above 4.

  If you change the rule sets you may have to remove the optimization.

  Additionally there are other early exits from the counting loop.

"use strict";

const RESET_TIME = 1000; // in millisecond
const TICK_TIME = 32;    // in millisecond
const SIZE = 160;         // in cells

// Cell rules
const DIE = -1, BIRTH = 1, NO_CHANGE = 0;

// RULES index of items is neighbor count. 
// 5 Items as rules for count 4,5,6,7,8 have same outcome
// First rule set for dead cells, second for live cells
const RULES = [
    [NO_CHANGE, NO_CHANGE, NO_CHANGE, BIRTH,     NO_CHANGE],
    [DIE,       DIE,       NO_CHANGE, NO_CHANGE, DIE]
];
// MAX_COUNT max living neighbors to count
const MAX_COUNT = RULES[0].length - 1;

// next two arrays are offsets to neighbors as 1D and 2D coords
const NEIGHBOR_OFFSETS = [
    -SIZE - 1, -SIZE, -SIZE + 1,
    -1,                1,
     SIZE - 1,  SIZE,  SIZE + 1
];
const EDGE_OFFSETS = [ // as coord pairs, x, y for cells at edge
    -1, -1, 0, -1, 1, -1,
    -1, 0,         1, 0,
    -1, 1,  0, 1,  1, 1
];

// double buffered board state
var BOARDS = [new Array(SIZE * SIZE).fill(0), new Array(SIZE * SIZE).fill(0)];
var currentState = 0;

// canvas for display
const display = Object.assign(document.createElement("canvas"), {width: SIZE, height: SIZE});
display.ctx = display.getContext("2d");
display.pixels = display.ctx.getImageData(0, 0, SIZE, SIZE);
display.buf32 = new Uint32Array(display.pixels.data.buffer);
const PIXELS = [0, 0xFF000000];  // Uint32 pixel value NOTE channel order ABGR
                                 // eg 0xFF000000 is black 0xFF0000FF is red
document.body.appendChild(display);
display.addEventListener("click", randomize);  // click to restart

// start game
randomize();
tick();


function randomize(density = 0.1) {
    const b = BOARDS[currentState % 2];
    var i = b.length;
    while (i--) { b[i] = Math.random() < density ? 1 : 0 }
    render();
}
function render() {
    const b = BOARDS[currentState % 2], d32 = display.buf32;
    var i = b.length;
    while (i--) { d32[i] = PIXELS[b[i]] }
    display.ctx.putImageData(display.pixels, 0, 0);
}
function update() {    
    var x, y = SIZE, idx = SIZE * SIZE - 1, count, k, total = 0;

    // Aliases for various constants and references to keep code line sizes short. 
    const ps = BOARDS[currentState % 2];        // prev state
    const ns = BOARDS[(currentState + 1) % 2]; // new state
    const NO = NEIGHBOR_OFFSETS, EO = EDGE_OFFSETS, S = SIZE, S1 = SIZE - 1;
    while (y--) {
        x = SIZE;
        while (x--) {
            count = 0;
            if (x === 0 || x === S1 || y === 0 || y === S1) {
                k = 0;
                while (k < EO.length && count < MAX_COUNT) {
                    const idxMod = (x + S + EO[k]) % S + ((y + S + EO[k + 1]) % S) * S;
                    count += ps[idxMod];
                    k += 2;
                }
            } else {
                k = 0;
                while (k < NO.length && count < MAX_COUNT) { count += ps[idx + NO[k++]] }
            }
            const useRule = RULES[ps[idx]][count];
            if (useRule === DIE) { ns[idx] = 0 }
            else if (useRule === BIRTH) { ns[idx] = 1 }
            else { ns[idx] = ps[idx] }
            total += ns[idx];
            idx --;
        }        
    }
    return total;
}

function tick() {
    const living = update();
    currentState++;
    render();
    if (living) {    
        setTimeout(tick, TICK_TIME);
    } else {
        randomize();
        setTimeout(tick, RESET_TIME);
    }
}

canvas {
  width: 640px;
  height: 640px;
  image-rendering: pixelated;
  border: 1px solid black;
}

Click canvas to reset

Answer 2

Correctness

First of all, your algorithm doesn't seem to implement the lattice state update correctly: as soon as you update the state of one cell, the neighbor counts of any adjacent cells will change. Usually this isn't supposed to happen: most CA are defined so that, conceptually, every cell changes state at the same instant.

This means that, when updating the lattice, you'll need some way to remember what the neighborhood of each cell looked like before you started updating them. There are several possible ways to do this (some of which I'll mention further down), but one common solution is double buffering.

Basically, what that means is that you maintain two copies of the cell state array: one that contains the states of the cells on the current time step, and another one that will contain the states of the cells on the next time step. In your update loop, you read from the current array and write to the next-generation array. Once you're done, just swap the arrays and start over.

Edge cases

Again, there are plenty of options for handling cells at the edges, and you can pick whichever one you want:

1. Just assume that any cells outside the array always stay in some fixed state (e.g. state 0).

2. Wrap the edges around, so that the bottom row is adjacent to the top row, and the rightmost column is adjacent to the leftmost.

3. Expand the array as the cells spread, so that the pattern evolves as if it's on an infinite lattice with no edges.

4. Do something else. Really, whatever you want. Maybe make the edges into mirrors, so that each edge cell counts as one of its own neighbors. Or update the edge cells according to some external input. Or something.

Options 2 and 3 above have the advantage that the cellular automaton will locally behave the same way at all points, making the edges invisible. Most other options will tend to result in unusual behavior near the edges, either because the cells beyond the edge don't obey the same CA rule as the cells inside the lattice or because the cell adjacency graph looks different near the edges.

Option 3 does have some obvious performance concerns, especially if the CA rule you're using tends to feature rapidly spreading patterns of cells. Thus, options 1 and 2 are probably the most popular ones for simple CA implementations.

Efficiency

OK, this is a deep rabbit hole. For a brief glimpse of how deep, take a look at my earlier answer on optimizing cellular automata in Java. And that doesn't even get into any really advanced optimization techniques.

Here's a few quick general things to keep in mind:

• Optimize for the general case, not for (literal) edge cases. In particular, consider handling the edges of the lattice in a separate update loop so that you can remove any edge-handling conditionals from your main update loop.

• Precalculate everything you can. If you can save even one nanosecond per cell in your main update loop by spending 10,000 times as much time precalculating stuff outside the loop, that's worth it as soon as your lattice is bigger than 100 × 100 cells.

• Try to avoid updating cells that you don't need to. I've given some concrete suggestions for that at the end of the earlier answer linked above, but one option is to maintain a list of cells that have just changed and only updating those cells and their neighbors on the next time step. (Or, alternatively, also include the neighbors of any cells that have changed in the list so that it directly includes every cell that may need updating next time.)

  Note that the performance gain from doing this will depend a lot on the CA rule, and may sometimes be negative. For rules where most cells change only rarely, this optimization can be a huge gain. For rules where most cells change nearly all the time, you're better off just updating every cell in a well optimized loop.

• Precalculate and store the neighbor counts. This optimization is specific to "totalistic" rules where the next state of each cell only depends on its own state and the number of active neighbor cells. In that case, instead of counting the active neighbors of each cell on each time step, you can store the count in the state array alongside the state of the cell itself and, whenever a cell changes state, increment or decrement the neighbor counts of any adjacent cells.

The last two optimizations above can also be used to eliminate the need for double buffering. Basically, instead of reading from one array and writing to another, an alternative way to ensure that cell state updates happen "simultaneously" is to queue them up in a list and then, once you've determined which cells actually need to change, loop though the list and actually update the cells. Again, see the linked earlier answer for an example.

JavaScript specific tips

Since you're using JS, here's a couple of specific things to consider:

• Instead of using setInterval() for scheduling your timesteps, consider moving all the heavy computation into a web worker thread. That way your page will remain responsive even if the updates end up consuming more CPU time than expected.

• Instead of using classic JS arrays, consider using typed arrays instead. They're more compact and likely faster than classic arrays, and they work really well for transferring data to and from web workers, too.

• If you really want to optimize your inner update loop, you could always try rewriting it in WebAssembly. But that kind of micro-optimization should really only be done after all other practical optimization options have been used.

Finally, perhaps the most efficient optimization might be to rewrite your CA simulation as a WebGL fragment shader instead of JS code. That way it could run on the GPU, which is a lot better suited for this kind of computation than the CPU. You could also use shaders both for the actual CA state update and for rendering the resulting lattice to the screen, if that's what you want to do.

I've never done this myself, so I have no specific tips to give, but WebGL shaders are certainly capable of this, and much more. (See e.g. Shadertoy for some examples.)