Conway’s Game of Life

For those who don’t know the Game of Life, it is a cellular automaton invented by the mathematician John Conway in the 70’s. The game consists in watching the evolution of a set of cells that interact with each other following 4 simple rules:

1. Any live cell with fewer than two live neighbours dies, as if caused by underpopulation.
2. Any live cell with more than three live neighbours dies, as if by overcrowding.
3. Any live cell with two or three live neighbours lives on to the next generation.
4. Any dead cell with exactly three live neighbours becomes a live cell.

It’s amazing to see the amount of literature available about this game. You can check the wikipedia article for an example.

So, a few weeks ago our professor on High Performance Computating challenged us to implement a Game of Life without if statements. The difficulty lies in all the special cases to take into account when you use a matrix data structure to represent the cells. The special cases are those cells that have less adjacent neighbours than the normal cells, like corners and cells in the borders of the matrix. Avoiding conditional branches inside large loops is usually a very good practice to improve the performance of your code, since a branch instruction is a very costly operation for the cpu.

The challenge itself wasn’t very difficult, so a few weeks ago when I was bored I decided to implement it using Qt 4 toolkit. It was also an excuse to try the new QtCreator IDE, which, by the way, I found amazing.

Let’s take a look at my solution:

void GameOfLifeWidget::setMatrices()
{
    m_lifeMatrix = new int*[ m_rows + 2 ];
    m_nextMatrix = new int*[ m_rows + 2 ];
    for( int i = 0; i < m_rows + 2; i++ )
    {
        m_lifeMatrix[i] = new int[ m_cols + 2 ];
        m_nextMatrix[i] = new int[ m_cols + 2 ];
        for( int j = 0; j < m_cols + 2; j++ )
        {
            m_lifeMatrix[ i ][ j ] = 0;
            m_nextMatrix[ i ][ j ] = 0;
        }
    }
}

void GameOfLifeWidget::iterate()
{
    int neighbours = 0;
    int **aux;
    int currCell;
    for( int i = 1; i < m_rows; i++ )
    {
        for( int j = 1; j < m_cols; j++ )
        {
            neighbours = m_lifeMatrix[ i - 1 ][ j - 1 ] + m_lifeMatrix[ i ][ j - 1] +
                         m_lifeMatrix[ i + 1 ][ j - 1 ] + m_lifeMatrix[ i - 1 ][ j ] +
                         m_lifeMatrix[ i + 1 ][ j ] + m_lifeMatrix[ i - 1 ][ j + 1 ] +
                         m_lifeMatrix[ i ] [ j + 1 ] + m_lifeMatrix[ i + 1 ][ j + 1 ];
            currCell = m_lifeMatrix[ i ][ j ];
            m_nextMatrix[ i ][ j ] = !( currCell == 1 && ( neighbours   3 ) ) &&
                                    ( currCell == 0 && neighbours == 3 );            

        }

    }
    aux = m_lifeMatrix;
    m_lifeMatrix = m_nextMatrix;
    m_nextMatrix = aux;
    update();
}

To avoid the special cases we can create a matrix with extra borders. We will never iterate over these borders, but they make the actual borders a common case with 8 adjacent neighbours just like every other cell.

The method iterate is called every 500 milliseconds and it calculates the matrix of cells  for the next iteration. It does so by looping through the matrix and counting the number of neighbours for every cell. Then it applies AND’s and OR’s operations that combine the 4 rules of the game to find out if the cell must live or die.

And now the mandatory snapshot:

Game of Life Snapshot

You can also download the source code from here and, if you can make it compile, spend hours watching how life evolves.

Note: There is an issue with Qt re-painting the whole grid on every iteration which makes the cpu go high, I know why it happens but I haven’t had the time to fix it, but you can do whatever you want since it’s GPL

---

Possibly related posts: (automatically generated)

• Networks
• Conway’s Game of Life in Flex

Explore posts in the same categories: Programming

Tags: Game of Life, High Performance Computing, Qt

You can comment below, or link to this permanent URL from your own site.