Conway's Game of Life is one of the most well-known cellular automata.
It was developed by the British mathematician John Conway in 1970.
The game rules are simple:
As you can see, the state at each generation is only determined by the original configuration of the grid, not requiring user input.
The simplest algorithm to compute next generation is a direct one, storing all the cells of a finite grid.
Note that we need to store current and next generation separately on computation: otherwise cells won't be computed all at once.
Overall it requries O(n*m) time and space to compute one generation forward.
The disadvantages of this approach are clear, it doesn't work fast enough for big patterns, and requires too much memory.
Instead of storing all cells of the grid it is sufficient to store the positions of ON cells.
We could compute the result for less cells as well: if all of our neighbours have OFF state, the cell will be OFF for the next generation.
If all active cells at current generation are inside of rectangle ((min_x, min_y), (max_x, max_y)), it is sufficient to compute next cells in rectangle ((min_x-1, min_y-1), (max_x+1, max_y+1)).
Compared to the first approach, this one works much better for infinite small patterns, such as glider.
We store only 5 cells at a time, and compute the result for 25 cells at a time.
This explanation of the algorithm by John H Williamson is much better than any I could write.
To summarize shortly, we store the grid as a block of 2^n by 2^n cells, take 2^(n-1) by 2^(n-1) nodes in the middle, and for those nodes compute 2^(n-2) generations forward.
As name suggests, hashing is very actively used, for repetitive patterns this algorithm gets faster and faster with time.
The project's repository is here: https://github.com/chopikus/game-of-life.
The compute next states of the grid, I implemented Hashlife in Rust using wasm-bindgen.
Previously I used C++ and Emscripten to do this project, however I stumbled upon weird memory issues that are hard to reproduce and depend on specific Emscripten versions. Besides, all of computation was done on a single thread, so UI became unresponsive if pattern was too heavy.
I moved the grid computation code to Rust to ensure memory safety.
Cells are visualized with OffscreenCanvas, which is now supported in all major browsers.
Overall, 3 different threads are used: one for cell computation, one for canvas drawing, and another for UI.
What happens if we scale the grid out so much that one pixel corresponds to more than one cell?
To make sure drawing cells stays performant, we use the following algorithm.
if a whole square of 2^k by 2^k pixels corresponds to one pixel, we draw that pixel white if that square has at least one ON cell.
This algorithm can be best described with code:
/*Following function pushes coordinates of ON cells in node up with (2^level):1 precision.*/
fn append_alive_cells(&self, node: Rc, output: &mut Vec| , level: u8, x: i64, y: i64, bounds: [i64; 4]) {
if !node.n() {
return;
}
let size: i64 = 1 << node.k();
let [min_x, min_y, max_x, max_y] = bounds;
if x + size <= min_x || x > max_x {
return;
}
if y + size <= min_y || y > max_y {
return;
}
/* Following if statement allows to compute with 'level' precision. */
if node.k() == level {
output.push(Cell{x: x - self.shift_x, y: y - self.shift_y});
return;
}
let offset: i64 = size >> 1;
let [a, b, c, d] = node.unwrap_children_cloned();
self.append_alive_cells(a, output, level, x, y, bounds);
self.append_alive_cells(b, output, level, x + offset, y, bounds);
self.append_alive_cells(c, output, level, x, y + offset, bounds);
self.append_alive_cells(d, output, level, x + offset, y + offset, bounds);
}
| The fastest solution seems to be to pass the list of i64 numbers, where each pair corresponds to a cell coordinate.
Rust backend returns a pointer to a vector and it's size, which is then converted to BigInt64Array in JS.
Also the buffer of BigInt64Array is transferrable.