Game of Life implementation is too slow

Question

I was tasked with implementing Conway's Game of Life. It seems to work fine but the implementation is lacking as I find that it takes a long time to generate the next generation of the grid. I'm looking for flaws and tips to speed up the process. Currently, I can only refresh the display twice a second.

The grid class and all its methods: Grid.h

#pragma once
class Grid {
private:
    int species = 0;
    static int currentGrid[1024][768];
    static int nextGenGrid[1024][768];
    const int WIDTH = 1024;
    const int HEIGHT = 768;
public:
    Grid(int species);
    int getHeight();
    int getWidth();
    int checkCell(int x, int y);
    int checkNextGenCell(int x, int y);
    void changeCell(int x, int y, int species);
    void changeNextGenCell(int x, int y, int species);
    int numOfNeighbors(int x, int y);
    int Reproduce(int x, int y);
    void nextGen(int x, int y);
    void Update(int xStart, int xEnd);
    void Transition(int xStart, int xEnd);
};
    int Grid::currentGrid[1024][768];
    int Grid::nextGenGrid[1024][768];

Grid.cpp

 #include <stdlib.h>
 #include <algorithm> 
 #include <random>
 #include "Grid.h"
 #include <time.h> 

int Grid::currentGrid[1024][768];
int Grid::nextGenGrid[1024][768];
//populate the grid with different species of cells
Grid::Grid(int species) {
    this->species = species;
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> dist(0, species);
    for (int i = 0; i < WIDTH; i++) {
        for (int j = 0; j < HEIGHT; j++) {
            //0 represents a dead cell
            currentGrid[i][j] = (int)dist(gen);
        }
    }
}
//return height of grid
int Grid::getHeight() {
    return HEIGHT;
}
//return width of grid
int Grid::getWidth() {
    return WIDTH;
}
//check species of a cell
int Grid::checkCell(int x, int y) {
    return currentGrid[x][y];
}

//change species of cell with int supplied
//shouldn't be called, only change next generation
void Grid::changeCell(int x, int y, int species) {
    currentGrid[x][y] = species;
}

//check species of a nextGen cell
int Grid::checkNextGenCell(int x, int y) {
    return nextGenGrid[x][y];
}

//change species of a nextGen cell with int supplied
void Grid::changeNextGenCell(int x, int y, int species) {
    nextGenGrid[x][y] = species;
}


//return the number of neighbors of the SAME species for a LIVING cell
int Grid::numOfNeighbors(int x, int y) {
    int numOfNeighbors = 0;
    //check conditions for specific species
    if (checkCell(x, y) != 0) {
        int xStart = std::max(x - 1, 0);
        int xFinish = std::min(x + 1, WIDTH - 1);
        int yStart = std::max(y - 1, 0);
        int yFinish = std::min(y + 1, HEIGHT - 1);
        for (int curY = xStart; curY <= xFinish; curY++) {
            for (int curX = yStart; curX <= yFinish; curX++) {
                //check if same species and ignore itself
                if (checkCell(x,y) == checkCell(curY, curX) && !(curY == x && curX == y)) {
                    numOfNeighbors++;
                }
            }
        }
    }
    return numOfNeighbors;
}
//will look for 3 neighbors of the SAME species to ressurect a dead cell
//return the species that has 3 neighbors to this cell OR return 0 if condition not met
int Grid::Reproduce(int x, int y) {
    int xStart = std::max(x - 1, 0);
    int xFinish = std::min(x + 1, WIDTH - 1);
    int yStart = std::max(y - 1, 0);
    int yFinish = std::min(y + 1, HEIGHT - 1);
    for (int i = 1; i <= species; i++) {
        int numOfLivingNeighbors = 0;
        for (int curY = xStart; curY <= xFinish; curY++) {
            for (int curX = yStart; curX <= yFinish; curX++) {
                if (checkCell(curY, curX) != 0) {
                    //check if same species and ignore itself
                    if (checkCell(curY, curX) == i && !(curY == x && curX == y)) {
                        numOfLivingNeighbors++;
                    }
                }
            }
        }
        if (numOfLivingNeighbors == 3) {
            return i;
        }
    }
    return 0;
}
//call numOfNeighbors for living cell or Reproduce for dead cell, then update the corresponding nextGenGrid cell
void Grid::nextGen(int x, int y) {
    if (checkCell(x, y) != 0) {
        int neighbors = numOfNeighbors(x, y);
        if (neighbors < 2 || neighbors > 3) {
            changeNextGenCell(x, y, 0);
        }
        else {
            changeNextGenCell(x, y, checkCell(x, y));
        }
    }
    else {
        changeNextGenCell(x, y, Reproduce(x, y));
    }
}
//update the m x n cells of the grid to the next generation
void Grid::Update(int xStart, int xEnd) {
    //populate nextGenGrid with results
    for (int i = xStart; i <= xEnd; i++) {
        for (int j = 0; j < HEIGHT; j++) {
            nextGen(i, j);
        }
    }
}
//now transition currentGrid to nextGenGrid
void Grid ::Transition(int xStart, int xEnd) {
    for (int i = xStart; i <= xEnd; i++) {
        for (int j = 0; j < HEIGHT; j++) {
            changeCell(i, j, checkNextGenCell(i, j));
        }
    }
}

and now for where the main gets executed:

#include <stdlib.h>
#include <iostream>
#include <thread>
#include <windows.h>
#include "Dependencies\glew\glew.h"
#include "Dependencies\freeglut\freeglut.h"
#include "Grid.h"
static const int numOfSpecies = 8;
static const int numOfThreads = 8;
Grid grid = Grid(numOfSpecies);
int threadWidth = grid.getWidth() / numOfThreads;

void nextGrid(int tid) {
    grid.Update(threadWidth * tid, threadWidth * (tid + 1) - 1);
}

void transitionGrid(int tid) {
    grid.Transition(threadWidth * tid, threadWidth * (tid + 1) - 1);
}

void refreshScreen(void) {
    std::thread t[numOfThreads];
    //populate nextgengrid with threads, split the task
    for (int i = 0; i < numOfThreads; i++) {
        t[i] = std::thread(nextGrid, i);
    }
    //join all threads back
    for (int i = 0; i < numOfThreads; ++i) {
        t[i].join();
        if (i == numOfThreads - 1) {
        }
    }
    //transition the nextGenGrid to the currentGrid
    for (int i = 0; i < numOfThreads; i++) {
        t[i] = std::thread(transitionGrid, i);
    }
    //join all threads back
    for (int i = 0; i < numOfThreads; ++i) {
        t[i].join();
    }
    glutPostRedisplay();
}

void display(void)
{
    glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
    glLoadIdentity();
    glOrtho(0.f, grid.getWidth(), grid.getHeight(), 0.f, 0.f, 1.f);
    glColor3f(0.0f, 0.0f, 0.0f);
    glPointSize(1.0f);
    glBegin(GL_POINTS);
    for (int i = 0; i < grid.getWidth(); ++i) {
        for (int j = 0; j < grid.getHeight(); ++j) {
            switch (grid.checkCell(i, j)) {
            case 0:
                //black
                glColor3f(0.0f, 0.0f, 0.0f);
                break;
            case 1:
                //red
                glColor3f(1.0f, 0.0f, 0.0f);
                break;
            //...you get the idea
            case 10:
                //dark green
                glColor3f(0.0f, 0.5f, 0.0f);
                break;
            }
            glVertex2f(i, j);
        }
    }
    glEnd();
    glutSwapBuffers();
}

int main(int argc, char **argv) {
    //use factors of 1024 divide the grid evenly between threads
    //width of the screen 1 thread is responsible for
    glutInit(&argc, argv);
    glutInitDisplayMode(GLUT_RGB | GLUT_DOUBLE);
    glutInitWindowSize(1072, 768);
    glutCreateWindow("The Game of Life");
    glutDisplayFunc(display);
    glutIdleFunc(refreshScreen);
    glutMainLoop();
    return 0;
}

Answer 1

Your code is very straightforward and easy to understand, which is great! Keep that up!

Profile

Whenever you're dealing with performance, the most important thing you can do is to profile your code to see where the slowdowns are. I can't tell just by looking at your code which part is slowing it down. I do see some things you could improve, though.

Don't Send Individual Pixels to OpenGL

The biggest problem I see is that you're manually setting each pixel in the world on every loop. That's going to be time consuming. What you could do instead is upload the grid as a texture and blit it to the screen by drawing a screen-aligned textured quad with it. Rather than having a case statement that outputs a different color for each cell, simply call glTexImage2D() to upload the data as a 1-channel grayscale texture. You can then either use it directly to texture a quad (which would probably be too dark to show much, as you only have 10 values), or apply a fragment shader to sample it and do something with the result. For example, that case statement in display() could be moved into a shader, and possibly turned into a look-up table instead.

Use Your Named Constants

You've gone to the trouble to use named constants for a number of values in your code, but you've neglected to use them everywhere. For example, in the definition of your Grid class, you have this:

static int currentGrid[1024][768];
static int nextGenGrid[1024][768];
const int WIDTH = 1024;
const int HEIGHT = 768;

Why wouldn't you define WIDTH and HEIGHT before currentGrid and nextGenGrid, and then use them to define those 2 arrays? Like this:

const int WIDTH = 1024;
const int HEIGHT = 768;
static int currentGrid[WIDTH][HEIGHT];
static int nextGenGrid[WIDTH][HEIGHT];

Also, you've multiply defined currentGrid and nextGrid both in the header (just after the class definition) and in the source file. I'm a little surprised your compiler doesn't warn you about that.

Also, why use constants and then have a getWidth() and getHeight() method that simply return the constants? If they can never change, and the constants are public, there's no need for those accessors.

Other Optimizations

There are other types of optimizations you can make. One route to take is memoization. This is where you cache the results of a calculation and re-use it when your inputs are the same. You can get significant speed-ups by doing this with your grid. See this article for more info.