Optimizing code (Conway's Game of Life)

Question

I just made this console version of the Conway's Game of Life. It works well for "small" grids, 100 x 100 pixels for example, but is terribly slow for bigger ones. Can you help me to optimize it, so it can run faster?

#define _WIN32_WINNT 0x0500
#include <windows.h>
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <string>
using namespace std;

const int m = 100;
const int n = 100; // size of the grid area
const int num_iter = 1000; // number of iterations to run

int main(){

    srand(time(0)); // the initial conditions of the grid should be random
    int n_count = 0; // variable for counting the neighbors of a particular point
    int iter = 0; // variable for counting the number of iterations done
    int grid[m][n] = {0};
    int newgrid[m][n] = {0}; // arrays filled with 1's and 0's representing a living or dead cells respectively

    HWND myconsole = GetConsoleWindow();
    HDC mydc = GetDC(myconsole);
    COLORREF WHITE = RGB(255,255,255);
    COLORREF BLACK = RGB(0,0,0);

    for(long i=0;i<m;i++){ // this for initializes the grid with random 1's
        for(long j=0;j<n;j++){
            if(rand()%2==0) grid[i][j] = 1;
        }
    }

    while(iter < num_iter){ // while loop controlling the number of iterations to be done
        for(long i=0;i<m;i++){
            for(long j=0;j<n;j++){ // nested for to count the number of neighbors of each cell
                if(i-1>=0) if(grid[i-1][j]==1) n_count++;
                if(j-1>=0) if(grid[i][j-1]==1) n_count++;
                if(i+1<=n) if(grid[i+1][j]==1) n_count++;
                if(j+1<=n) if(grid[i][j+1]==1) n_count++;
                if((i-1>=0)&&(j-1>=0)) if(grid[i-1][j-1]==1) n_count++;
                if((i-1>=0)&&(j+1<=n)) if(grid[i-1][j+1]==1) n_count++;
                if((i+1<=n)&&(j-1>=0)) if(grid[i+1][j-1]==1) n_count++;
                if((i+1<=n)&&(j+1<=n)) if(grid[i+1][j+1]==1) n_count++; // all possible 8 neighbors checked and counted by now
                if(grid[i][j]==1){ // if the cell is alive and...
                    if(n_count<2) newgrid[i][j] = 0; // ...it has less than 2 neighbors, then it dies
                    else if(n_count>3) newgrid[i][j] =0; // ... it has more than 3 neighbors, then it dies
                    else if((n_count==2)||(n_count==3)) newgrid[i][j] = 1; // ... it has 2 or 3 neighbors, then it lives
                }
                else if(n_count==3) newgrid[i][j] = 1; // if the cell is dead and it has 3 neighbors, then it lives
                n_count = 0;
            }
        }
        for(long i=0;i<m;i++){ // nested for to display a white pixel if the cell is alive, or black if it is dead
            for(long j=0;j<n;j++){
                grid[i][j] = newgrid[i][j];
                if(grid[i][j]==1) SetPixel(mydc,i+50,j+40,WHITE);
                else SetPixel(mydc,i+50,j+40,BLACK);
            }
        }
        Sleep(1);
        iter++;
    }

    ReleaseDC(myconsole, mydc);
    cin.ignore();
    return 0;
}

http://stackoverflow.com/questions/40485/optimizing-conways-game-of-life — NPE, Feb 07 '15 at 21:11
I'm voting to close this question as off-topic because it belongs on CodeReview. — Barry, Feb 07 '15 at 23:56

Mike Nakis · Accepted Answer · 2015-02-07T21:31:25.933

3

I suppose optimizing Conway's Game of Life is a science in and of itself, and I am sure this is covered pretty well in the link provided by NPE, but if I may suggest something, SetPixel is an awful waste of time.

So, two optimizations:

Only do SetPixel for those pixels that actually change. Instead of this:

        grid[i][j] = newgrid[i][j];
        if(grid[i][j]==1) SetPixel(mydc,i+50,j+40,WHITE);
        else SetPixel(mydc,i+50,j+40,BLACK);

do this:

        if( grid[i][j] != newgrid[i][j] )
        {
            grid[i][j] = newgrid[i][j];
            if(grid[i][j]==1) SetPixel(mydc,i+50,j+40,WHITE);
            else SetPixel(mydc,i+50,j+40,BLACK);
        }

Stop using SetPixel altogether; try obtaining a bitmap, locking it to get access to its memory buffer, directly manipulating the bytes of the memory buffer to store your colour values in it, and then in the end unlocking it and blitting it to the device context. It may sound like a lot of work, but trust me, it will actually represent a huge performance improvement over gazillions of calls to SetPixel.

edited Feb 07 '15 at 21:31

answered Feb 07 '15 at 21:15

Mike Nakis

56,297
11
110
142

what can I use instead SetPixel? – user3787097 Feb 07 '15 at 21:16
I see you accepted my answer, would you like to tell us which of my two suggestions you followed and how much improvement you witnessed? – Mike Nakis Feb 07 '15 at 21:58
I have already implemented the first one. Indeed, it helped a lot. As for the second one, I really did not understand what did you write. Rigth now I'm searching for bitmap + C++ in google to see what can I get from that. – user3787097 Feb 08 '15 at 01:13
Okay, since I see you are using plain old GDI, this article explains everything there is to know about memory DCs and bitmaps: http://www.codeproject.com/Articles/224754/Guide-to-Win-Memory-DC and this article shows how to read and write the actual pixel data of a bitmap: http://www.codeproject.com/Articles/2841/How-to-replace-a-color-in-a-HBITMAP – Mike Nakis Feb 08 '15 at 02:30

Optimizing code (Conway's Game of Life)

1 Answers1