Thiago Cafe - Programming is fun !
Created by thiago on 2017-09-10 10:42:42

Having fun in life!

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

Matrix data structure

Many implementations use a structure like matrix[x][y], having a vector of vectors. There are two prolems I see with those implementations

  1. Memory is not contiguous. The first vector is just a vector of pointers
  2. It's boring and lacks abstraction. Although it is simple to implement, if I want to rotate the matrix or change anything I cannot implement easily

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.

Matrix view

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

Decouple the rule and data type

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

Writing the code

Now let's go to the code

Implementing the matrix

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();
}    

implementing the matrix view

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));
}

Implementing the life processor

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);

Implementing the rules and counter

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

...

Other comments

No comments !