skip to Main Content

I’m working on some code for a javascript implemenation of Conway’s Game of Life Cellular Automata for a personal project, and I’ve reached the point of encoding the rules. I am applying the rules to each cell, then storing the new version in a copy of the grid. Then, when I’m finished calculating each cell’s next state, I set the first grid’s state to the second’s one, empty the second grid, and start over. Here’s the code I used for the rules:

//10x10 grid
let ecells = [[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, 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]];

let cells = empty_cells;

let new_cells = cells;

let paused = true;

function Cell(x, y) {
    return cells[y][x];
}

function Nsum(i, j) {
    if (i >= 1 && j >= 1) {
        return Cell(i - 1, j) + Cell(i + 1, j) + Cell(i, j - 1) + Cell(i - 1, j - 1) + Cell(i + 1, j - 1) + Cell(i, j + 1) + Cell(i - 1, j + 1) + Cell(i + 1, j + 1);
    }
}

//One can manually change the state of the cells in the "cells" grid, 
//which works correctly. Then, one can run the CA by changing the "paused"
//value to false.

function simulation() {
    for (i = 0; i < cells[0].length; i++) {
        for (j = 0; j < cells.length; j++) {
            if (Cell(i, j)) {
                ctx.fillRect(20*i - 0.5, 20*j, 20, 20);
                if (!paused) {
                    if (Nsum(i, j) == 2 || Nsum(i, j) == 3) new_cells[j][i] = 1;
                    else new_cells[j][i] = 0;
                }
            }
            else {
                ctx.clearRect(20*i - 0.5, 20*j, 20, 20);
                if (!paused) {
                    if (Nsum(i, j) == 3) new_cells[j][i] = 1;
                    else new_cells[j][i] = 0;
                }
            }
        }
    }
    if (!paused) cells = new_cells;
    new_cells = empty_cells;
    requestAnimationFrame(simulation);
}

simulation();

The rule logic is inside the nested for loop, Nsum is the function that calculates the neighborhood sum of the current cell. I say ncells[j][i] instead of ncells[i][j] because in a 2d array you address the row first.

I didn’t try much, but I can’t imagine a solution. Help!

2

Answers


  1. Let’s start by not bothering with rows vs. columns, because (and this is the nice thing about the game of life), it doesn’t matter. The only thing that matters is what the eight values around a cell are doing, so as long as we stick to one ordering, the code will simply do the right thing.

    Which means we can get rid of that Cell function (on that note, that’s not how you name things in JS. Variables and functions use lowerCamelCase, classes/constructor functions use UpperCamelCase and constant values use UPPER_SNAKE_CASE).

    Then, let’s fix Nsum because it’s ignoring the edges right now, which is not how the game of life works: in order to count how many neighbours a cell has, we need to sum up to eight values, but not every cell has eight neighbours. For instance, (0,0) has nothing to the left/above it. So let’s rewrite that to a loop:

    function getNeighbourCount(i, j) {
      const cells = currentCells;
      let sum = 0;
      // run over a 3x3 block, centered on i,j:
      for (let u = -1; u <= 1; u++) {
        // ignore any illegal values, thanks to "continue";
        if (i + u < 0 || i + u >= cellCount) continue;
        for (let v = -1; v <= 1; v++) {
          // again, ignore any illegal values:
          if (j + v < 0 || j + v >= cellCount) continue;
          // and skip over [i][j] itself:
          if (u === 0 && v === 0) continue;
          sum += cells[i + u][j + v];
        }
      }
      return sum;
    }
    

    We can also take advantage of the fact that we know that we’re setting our update board to zeroes before we start calculating updates, so we don’t need to set any cells to 0: they already are.

    ...
      // by copying the empty cells array, we start with
      // all-zeroes, so we don't need to set anything to 0.
      const next = structuredClone(emptyCells);
    
      for (let i = 0; i < cellCount; i++) {
        for (let j = 0; j < cellCount; j++) {
          // is this cell alive?
          const alive = currentCells[i][j] === 1;
    
          // we only need to calculate this once, not three times =)
          const neighbourCount = getNeighbourCount(i, j);
    
          if (alive && (neighbourCount === 2 || neighbourCount === 3)) {
            next[i][j] = 1;
          } else if (neighbourCount === 3) {
            next[i][j] = 1;
          }
        }
      }
    ...
    

    So if we put all that together, and instead of using a canvas we just use a preformatted HTML element that we print our grid into, we get:

    const cellCount = 10;
    
    // Let's define the same grid, but rather than harcoding it,
    // let's just generate it off of a single number:
    const emptyCells = [...new Array(cellCount)].map((_) => [...new Array(cellCount)].fill(0));
    
    // Then, initialize the current cells from that empty grid.
    let currentCells = structuredClone(emptyCells);
    
    // To see things work, let's add a "glider"
    [[0, 1],[1, 2],[2, 0],[2, 1],[2, 2]].forEach(([i, j]) => (currentCells[i][j] = 1));
    
    // Then, our control logic: we'll have the sim run
    // with a button to pause-resume the simulation.
    let nextRun;
    let paused = false;
    toggle.addEventListener(`click`, () => {
      paused = !paused;
      if (paused) clearTimeout(nextRun);
      else runSimulation();
    });
    
    // And then: run the program!
    showBoard();
    runSimulation();
    
    // It doesn't matter where we put functions in JS: the parser first
    // reads in every function, and only *then* starts running, letting
    // us organize things in terms of "the overall program" first, and
    // then "the functions that our program relies on" after.
    
    // draw our board with □ and ■ for dead and live cells, respectively.
    function showBoard() {
      board.textContent = currentCells
        .map((row) => row.join(` `).replaceAll(`0`, `□`).replaceAll(`1`, `■`))
        .join(`n`);
    }
    
    // our simulation just runs through the grid, updating
    // an initially empty "next" grid based on the four
    // Game of Life rules.
    function runSimulation() {
      const next = structuredClone(emptyCells);
      for (let i = 0; i < cellCount; i++) {
        for (let j = 0; j < cellCount; j++) {
          const alive = currentCells[i][j] === 1;
          const neighbourCount = getNeighbourCount(i, j);
          if (alive && (neighbourCount === 2 || neighbourCount === 3)) {
            next[i][j] = 1;
          } else if (neighbourCount === 3) {
            next[i][j] = 1;
          }
        }
      }
      // update our grid, draw it, and then if we're not paused,
      // schedule the next call half a second into the future.
      currentCells = next;
      showBoard();
      if (!paused) {
        nextRun = setTimeout(runSimulation, 500);
      }
    }
    
    // In order to count how many neighbours we have, we need to
    // sum *up to* eight values. This requires making sure that
    // we check that a neighbour even exists, of course, because
    // (0,0), for instance, has nothing to the left/above it.
    function getNeighbourCount(i, j, cells = currentCells) {
      let sum = 0;
      for (let u = -1; u <= 1; u++) {
        if (i + u < 0 || i + u >= cellCount) continue;
        for (let v = -1; v <= 1; v++) {
          if (j + v < 0 || j + v >= cellCount) continue;
          if (u === 0 && v === 0) continue;
          sum += cells[i + u][j + v];
        }
      }
      return sum;
    }
    <pre id="board"></pre>
    <button id="toggle">play/pause</button>
    Login or Signup to reply.
  2. Here’s the core of your problem:

    let cells = empty_cells;
    let new_cells = cells;
    

    These statements don’t do what you think: instead of making copies of the arrays, they just assign the same array to multiple variables.

    This would be fine if your array was immutable (like, say, strings and numbers are in JS), but since the array is mutable, any changes made to it via one variable will be visible through all the variables. In effect, all those variables are just different names for the same array.


    To show the problem more clearly, here’s a quick snippet you can run right here:

    const arrayOne = [0, 0, 0];
    const arrayTwo = arrayOne;
    arrayOne[0] = 37;
    arrayTwo[2] = 42;
    console.log("arrayOne =", arrayOne);
    console.log("arrayTwo =", arrayTwo);

    What do you think arrayOne and arrayTwo will look like after this code runs?

    The correct answer is that they will both look like [37, 0, 42], because they are just two names for the same array.


    So what should you do instead?

    Probably the most efficient way would be something like this:

    1. Before starting your simulation, create two separate arrays with the same dimensions. One way to do that (which doesn’t require deep-copying objects) is to write a function that creates and returns a new empty array, and then call it twice:

      function makeCellGrid() {
        return [
          [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, 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]
        ];
      }
      
      let cells = makeCellGrid();
      let newCells = makeCellGrid();
      

      The [ ... ] syntax in JavaScript creates a new array every time it is evaluated, so each call to the function will return a completely new array of arrays.

      (Of course it would be nicer if the makeCellGrid function took the width and the height of the grid you want as parameters and returned an array of the requested size. I’ll leave implementing that as an exercise. Using a loop to create the rows is probably the simplest way, although you can also do it e.g. with the map method.)

    2. In your simulation function, you read only from cells and write only to newCells, just like you’re currently doing. However, at the end of the function, what you do is swap the two arrays:

      const tempCells = cells;
      cells = newCells;
      newCells = tempCells;
      

      or, more compactly in modern JS:

      [cells, newCells] = [newCells, cells];
      

      Now you have the array containing the new cell states in cells, ready to be drawn. (You also still have the previous generation’s cell states in the array that is now newCells, but that doesn’t matter, since they will just be ignored and overwritten when the function is called again.)

    Login or Signup to reply.
Please signup or login to give your own answer.
Back To Top
Search