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
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: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.
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:
Here’s the core of your problem:
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:
What do you think
arrayOne
andarrayTwo
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:
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:
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 themap
method.)In your
simulation
function, you read only fromcells
and write only tonewCells
, just like you’re currently doing. However, at the end of the function, what you do is swap the two arrays:or, more compactly in modern JS:
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 nownewCells
, but that doesn’t matter, since they will just be ignored and overwritten when the function is called again.)