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://chopikus.github.io/game-of-liife.
The compute next states of the grid, I implemented Hashlife in C++ using Webassembly.
To visualize grid and cells I simply used Javascript Canvas API, it works fast enough.
When it comes to providing an interface between JS and C++, Emscripten is the best choice; as it provides support for multithreading, supports allocating lots of RAM in the browser, Google Test also works just fine.
Since Hashlife algorithm heavily relies on caching results, it requires a lot of RAM.
Therefore, saving some memory on nodes is preferred.
This Node class structure works well enough:
struct Node {
/* ____
/ \
|A B|
|C D|
\___/
*/
uint8_t kn; // first bit n, rest bits -- k
std::shared_ptr<Node> a,b,c,d;
uint64_t hash; // precomputed
auto operator<=>(const Node&) const = default;
uint8_t k() const;
bool n() const;
};
To prevent memory leaks and easily track Node's reference count, std::shared_ptr is used.
Although some might say std::shared_ptr uses too much memory, it helps remove quite a lot of unused nodes when running, saving quite a lot of RAM.
What happens if we scale out so much that one pixel corresponds to more than one cell?
Drawing the same pixel multiple times doesn't seem as a great idea.
To fix that, the following is usually done: 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.
In code it looks roughly like this:
/*Following function pushes coordinates of ON cells in node up with (2^level):1 precision.*/
void Hashlife::_append_alive_cells(const NodePtr& node, std::vector<Cell>& output,
uint8_t level,
int64_t x, int64_t y,
int64_t min_x, int64_t min_y,
int64_t max_x, int64_t max_y) {
/* if current node doesn't have any ON cells, pass*/
if (!node->n()) {
return;
}
if (node->k() == level) {
output.push_back({x, y});
return;
}
int64_t offset = size >> 1;
_append_alive_cells(node->a, output, level, x, y, min_x, min_y, max_x, max_y);
_append_alive_cells(node->b, output, level, x + offset, y, min_x, min_y, max_x, max_y);
_append_alive_cells(node->c, output, level, x, y + offset, min_x, min_y, max_x, max_y);
_append_alive_cells(node->d, output, level, x + offset, y + offset, min_x, min_y, max_x, max_y);
}
To draw the cells, the C++ backend passes the list of ON cells. Since each cell is simply a pair of numbers, the faster option is to create array on heap in C++ and pass the memory view to JS.
See this Emscripten doc for more info.