Tags: #c++
I was talking to a friend about cellular automata using Conway's Game of life as an example. Curious again after so many years that I've read it, I read again carefully the wikipedia page and I found it fascinating.
What is the better way to learn more? Implementing! However I do not want to implement it in a boring way. I want to have interesting features. Let's first talk a little bit about this 0-player fascinating game.
Rules (from Wikipedia):
In a matrix containing cells in all the space, being alive or dead, with no empty space, for each cell we apply the following rules at the same time:
And to add some fun, let's define what we want from the implementation
Many implementations use a structure like matrix[x][y], having a vector of vectors. There are two prolems I see with those implementations
The second possibility is to use a vector and calculate the position using the simple math y*cols+x, but it's error prone hence I want it inside the structure.
For each cell, I need to check the surrounding cells. Deal with indexes is error prone and also super boring. I want to create a view on the top of the matrix. In addition, I want this view to rotate automatically if the limit is reached.
Rotating over the X axis
Rotating over the Y axis
There are implementations using booleans, ints, structs, etc. I want to have it abstracted and rule dependent. To make it independent, I need to receive rule and counting
Now let's go to the code
We are abstracting type and the storage. Let's use vector as a default.
template<typename Type, typename Storage=std::vector<Type>>
struct matrix {
Storage data;
int cols, rows;
To make it more interesting, let's disable copying and add the move constructor and assignment
//... Constructor and boiler-plate code ...
matrix(int cols, int rows) : data(cols*rows), cols(cols), rows(rows) { }
matrix(const matrix& o) = delete; //disable copy
matrix(matrix&& o) : data(std::move(o.data)), cols(o.cols), rows(o.rows) { }
matrix& operator=(const matrix& other) = delete; //disable copy
matrix& operator=(matrix&& other)
{
data = std::move(other.data);
cols = other.cols;
rows = other.rows;
return *this;
}
And finally let's get the position. I am returning a type reference to allow the nice syntax of matrix(x, y) = value;
Type _get_pos(int x, int y) const {
return x + (y*cols);
}
Type& operator () (int x, int y) {
return data[_get_pos(x,y)];
}
const Type& operator() (int x, int y) const {
return data[_get_pos(x,y)];
}
bool valid(int x, int y) const {
return _get_pos(x,y) < data.size();
}
This code has less boiler plate and it's nicer to implement
Now we will abstract the type and receive a matrix reference.
template<typename Type>
struct matrix_view {
matrix<Type> &_data;
const int _x, _y;
const int cols, rows;
matrix_view(matrix<Type> &data, int x, int y, int cols, int rows) :
_data(data), _x(x), _y(y), cols(cols), rows(rows) { }
Now we have to calculate the real index based on the virtual index and rotate to the other side if the boundary is reached. It will simplify a lot the life of the one's using this.
Type _get_x(int x) const {
int rx = _x + x;
if( rx >= _data.cols ) { rx -= _data.cols; }
if( rx < 0 ) { rx += _data.cols; }
return rx;
}
Type _get_y(int y) const {
int ry = _y + y;
if( ry >= _data.rows ) { ry -= _data.rows; }
if( ry < 0 ) { ry += _data.rows; }
return ry;
}
Type& operator () (int x, int y) {
return _data(_get_x(x), _get_y(y));
}
First, we need to receive from outside the rule, counter and cell type. Also, I cannot change the same matrix I am processing, as all operations should happen at the same time. To make it more interesting, to minimize copying, I am switching the received matrix with my internal one
//The life processor don't know cell types. It's the processor and counter dependent
template <typename Rule, typename Counter, typename CellType>
struct life_processor {
matrix<CellType> _nm; //internal matrix used to calculate and swap
Rule _rule;
Counter _counter;
life_processor(const matrix<CellType> &v) : _nm(v.cols, v.rows) {
}
For every iteraction, we need to, cell by cell, count the surrounding and apply the rules.
matrix<CellType> step(matrix<CellType> &m) {
for(int y=0; y < m.rows; ++y) {
for(int x=0; x < m.cols; ++x) {
auto mv = get_surrounding(m, x, y);
int count = _counter(mv);
//Let's apply the rules
_nm(x, y) = _rule(mv, count);
}
}
And instead of copying, let's swap and move to make it even faster !
std::swap(m, _nm);
return std::move(m);
First, let's implement the function to get the surrounding cells. With the matrix_view it is super easy.
template<typename T>
matrix_view<T> get_surrounding(matrix<T> &data, int x, int y) {
matrix_view<T> mv(data, x-1, y-1, 3, 3);
return std::move(mv);
}
And now we will implement the counter. Its responsibility is counting how many living cells we have in the view
//life_counter and life_rule are specific to int type.
struct life_counter {
int operator() (matrix_view<int> &mv) {
int total = 0;
for(int y=0; y < mv.rows; ++y) {
for(int x=0; x < mv.cols; ++x) {
//Let's not count itself
if(x == 1 && y == 1) {
continue;
}
if( mv(x, y) != 0 )
total += 1;
}
}
return total;
}
};
Time to implement the rule. To make it more interesting, instead of flipping the value, let's track the age of the cell
struct life_rule {
int increase_until(int val, int max) {
++val;
if( val > max ) return max;
return val;
}
int operator() (matrix_view<int> &view, int count) {
int cur_cell = view(1, 1);
//Any live cell with two or three live neighbours lives on to the next generation.
if( cur_cell != 0 && (count == 2 || count == 3) ) {
//To make it interesting, let's increase generation
return increase_until(cur_cell, 10);
}
//Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.
if( cur_cell == 0 && count == 3 ) {
//Baby cell !
return 1;
}
//Any live cell with fewer than two live neighbours dies, as if caused by underpopulation.
//Any live cell with more than three live neighbours dies, as if by overpopulation.
return 0;
}
We are almost done. We have the processor and the rule+counter. We just need to fill the matrix with random values and call our processor. All the auxiliar functions are in the example file.
matrix<int> v(cols, rows);
fill_random(v);
auto life = get_life(v);
while(true) {
show_matrix(v);
v = life.step(v);
}
I hope you enjoyed as much as I enjoyed writing!
Any comments or questions, compliments ?
Reach me on twitter - @thiedri