Conway's Game of Life in C++

Question

This is my attempt at Conway's Game of Life. It works, and it's the most complicated program I've made to date. I'm sure it's pretty poorly done. Any ideas on how I can improve on it?

#include <iostream>
#include <cstdlib>


const int gridsize = 75; //Making this a global constant to avoid array issues.

void Display(bool grid[gridsize+1][gridsize+1]){
    for(int a = 1; a < gridsize; a++){
        for(int b = 1; b < gridsize; b++){
            if(grid[a][b] == true){
                std::cout << " *";
            }
            else{
                std::cout << "  ";
            }
            if(b == gridsize-1){
                std::cout << std::endl;
            }
        }
    }
}
//This copy's the grid for comparision purposes.
void CopyGrid (bool grid[gridsize+1][gridsize+1],bool grid2[gridsize+1][gridsize+1]){
    for(int a =0; a < gridsize; a++){
        for(int b = 0; b < gridsize; b++){grid2[a][b] = grid[a][b];}
    }
}
//Calculates Life or Death
void liveOrDie(bool grid[gridsize+1][gridsize+1]){
    bool grid2[gridsize+1][gridsize+1] = {};
    CopyGrid(grid, grid2);
    for(int a = 1; a < gridsize; a++){
        for(int b = 1; b < gridsize; b++){
            int life = 0;
        for(int c = -1; c < 2; c++){
            for(int d = -1; d < 2; d++){
                if(!(c == 0 && d == 0)){
                    if(grid2[a+c][b+d]) {++life;}
                }
            }
        }
            if(life < 2) {grid[a][b] = false;}
            else if(life == 3){grid[a][b] = true;}
            else if(life > 3){grid[a][b] = false;}
        }
    }
}

int main(){

    //const int gridsize = 50;
    bool grid[gridsize+1][gridsize+1] = {};

    //Still have to manually enter the starting cells.
    grid[gridsize/2][gridsize/2] = true;
    grid[gridsize/2-1][gridsize/2] = true;
    grid[gridsize/2][gridsize/2+1] = true;
    grid[gridsize/2][gridsize/2-1] = true;
    grid[gridsize/2+1][gridsize/2+1] = true;

    while (true){
        //The following copies our grid.

        Display(grid);     //This is our display.
        liveOrDie(grid); //calculate if it lives or dies.
        system("CLS");
    }
}

Answer 1

Two major suggestions:

First, let's try speeding everything up by taking advantage of the nature of Conway's Game of Life and the way C++ handles pointers. When you evaluate Conway's Game of Life, it's a two part process. First you copy all of the entries into a new array, then you do your computation referring to that new array, and update the original one. This process takes \$ O \left( n^{2} \right) \$, and involves a major memory copy; for small sizes that shouldn't be a problem, at larger sizes, the cost incurred by the memory copy will become non trivial, so let's reformulate the design a little:

Conway's Game of Life itself is an application of cellular automata, where the state G of the grid at time t is a function of of the state at a time t-1. More specifically, it would be of a form like this: G(t)=R(G(t-1)) where R() is some rule function determining which cells live and which cells die. This direct dependence offers us an interesting solution to the memory copying conundrum--what if we store two grids, one to represent G(t) and one to represent G(t-1)? Then we can get away with reading G(t-1), applying our rule and updating G(t). This however brings us back to the first question--how do we update G(t-1) then? do we just copy G(t)'s memory? C++ offers us a more convenient approach actually, we can swap the pointers instead: as G(t) is fully described by G(t-1) if we simply swap the pointers for the two arrays, so the pointer for G(t-1) refers to G(t)'s memory region, and G(t) refers to G(t-1)'s memory region, then we can apply the update rule, update G(t) to be G(t+1), overwriting the old memory used to store G(t-1), which prevents us from needing to copy the grids ever, which will significantly speed up the simulation in case n>500 in my experience.

The second comment is on code abstraction, cellular automata as a whole is a good place to explore this, because it's such a general field. It's not necessary to make your Conway's Game of Life code work, but it will make it easier if you come up with interesting variations you want to test. Right now you have the update rule, R() represented as a single function, liveOrDie, this can be re-factored into several smaller tasks however, which has the advantage of making the system more modular and easier to tweak. How then can we break down this rule into smaller, more modular components? Let us start by listing the actual procedure performed by the update function:

• Iterate over all of the cells and update them
• To update a cell, look up it's neighbors (in Conway's Game of Life we use the Moore neighborhood)
• Look at a cells neighbors and decide whether it will live or die (apply the rule to a cell)
• Update the contents of a cell according to it's rule

This list of tasks lends itself to defining three separate functions

• void update(G(t),G(t-1)), which will perform the updating itself
• int neighbors(G,x,y), which will return the number of neighbors of a cell indexed at (x,y)
• bool rule(neighbors,lod,x,y) which will look at a specific cell and decide whether it lives or dies (lod is the state of the cell, live or dead)

The basic outline could then be something like this:

update(G(t),G(t-1)){
 for(x: 1..size)
  for(y: 1..size){
    G(t-1)[x+y*size] = rule(neighbors(G(t),x,y),G(t)[x+y*size],x,y)
  }
 swap = G(t-1)
 G(t-1) = G(t)
 G(t) = swap
}

The advantage to this model is if you want to change the function of the rule, or the neighborhood, say apply periodic bounding, you can easily change only the definition related to that part of the code. Hope that helps.

Answer 2

const int gridsize = 75; //Making this a global constant to avoid array issues.

It's good convention to use all capitals for global constants, for example:

const int GRIDSIZE = 75;

And now that it looks like a global constant, you can drop the the comment as it became pointless.

---

Instead of:

if(grid[a][b] == true){

you can write simply:

if (grid[a][b]) {

---

In your Display method, the way you write the newline is a bit strange:

if(b == gridsize-1){
    std::cout << std::endl;
}

The method would be more natural and simpler this way:

for (int a = 1; a < gridsize; a++) {
    for (int b = 1; b < gridsize; b++) {
        if (grid[a][b]) {
            std::cout << " *";
        } else {
            std::cout << "  ";
        }
    }
    std::cout << std::endl;
}

---

You should use a consistent style for naming your methods. Either all methods should start with a capital letter or none of them. Personally I prefer naming with lowercase and underscores, for example live_or_die, copy_grid.

---

It would be good to pay more attention to coding style: indent properly, and instead of:

if(grid2[a+c][b+d]) {++life;}

write like this:

if (grid2[a+c][b+d]) {
    ++life;
}

---

This works only in Windows:

system("CLS");

This would work in UNIX-like systems:

system("clear");

... but ideally it would be best to rewrite this in a platform independent way.

Answer 3

One major thing: do not pass C-arrays to functions as they will decay to a pointer.

In C++, you should just use storage containers (from the standard library or Boost) instead of C-arrays, which are more proper for passing storage data to functions (they will not decay to a pointer).

You may consider a 2D std::vector of bools:

std::vector<std::vector<bool> > grid;

However, given some of its issues, you may have to consider an alternative, such as an std::vector of ints. If you don't want to take any chances, you may choose the one with ints.

Another option is an std::array (C++11 only), if no resizing is needed:

std::array<std::array<bool, gridsize+1>, gridsize+1> grid;

For whichever one you choose, you may then have a typedef so that you don't have to type out the entire statement everywhere:

typedef std::vector<std::vector<bool> > Grid;

typedef std::array<std::array<bool, gridsize+1>, gridsize+1> Grid;

Declarations will be very short:

Grid grid;

Miscellaneous:

• Keep your function naming consistent. One starts with a lowercase letter and two others start with a capital letter. Choose whichever naming convention you prefer or are required to use.

• Prefer "\n" over std::endl for newlines. The latter also does a flush, which takes longer.

• Comments should not state the obvious and should only give useful clarification:

  //const int gridsize = 50;
  

  Commented-out code is ugly, especially when presenting the code as a final product.

  //This is our display.
  

  The function name already conveys its purpose. However, if you want to document each function, then make it more formal than this, and also mention its arguments and return values, if any.

  //This copy's the grid for comparision purposes.
  

  Consider proof-reading your comments, otherwise it can make the program seem sloppy.

Answer 4

If you're going to do it in C++, then you might as well use a class. For example, if grid were a data member of a class, and the various functions were methods of the same class, then you wouldn't need to pass the grid as a parameter to each of the various functions methods.

a and b aren't bad variable names, but i and j would be more conventional names to use as loop indices; or you could use row and col.

Indentation isn't quite correct in the liveOrDie function: the 3^rd for loop should be indented further to the right.

Capitalization isn't quite consistent: you use camelCase for liveOrDie but PascalCase for CopyGrid.

So far as I can see, by copying the grid you implemented the rules correctly.

Any idea's on how I can improve on it?

You could:

• Test it more
• Let user choose starting cells
• Make it display in a GUI
• Make it faster
• Make it a variable-size (or near-unlimited-size) grid

Answer 5

Any idea's on how I can improve on it?

The biggest improvement I can think of would be to avoid storing and processing the entire grid. Although there are exceptions, generally Conway's game of life patterns have a lot of empty space. At present your program is spending a lot of time and memory on this empty space.

I would recommend just storing the live cells, and calculating the next generation of live cells from this. For example, you could use an unordered set (which has O(1) access time) and just consider those cells which are either in the set or in an adjacent cell. No other cell will become alive in that generation, so you don't need to consider them.

For large patterns you will find that this approach is considerably more efficient in both time and space requirements, and also you don't need to specify the grid size up front, which is useful for new patterns for which you don't yet know how they will grow.

Answer 6

This isn't a huge issue, but one thing I would do is define macros at the top named ALIVE and DEAD so that you can use these keywords rather than true and false. To me, this would make the code clearer.

#define ALIVE true
#define DEAD false

In the liveOrDie function, I would also change the variable name life to the more descriptive neighbors or parents.

//Calculates Life or Death
void liveOrDie(bool grid[gridsize+1][gridsize+1]){
    bool grid2[gridsize+1][gridsize+1] = {};
    CopyGrid(grid, grid2);
    for(int a = 1; a < gridsize; a++){
        for(int b = 1; b < gridsize; b++){
            int neighbors = 0;
            for(int c = -1; c < 2; c++){
                for(int d = -1; d < 2; d++){
                    if(!(c == 0 && d == 0)){
                        if(grid2[a+c][b+d]) {++neighbors;}
                    }
                }
            }
            if(neighbors < 2) {grid[a][b] = DEAD;}
            else if(neighbors == 3) {grid[a][b] = ALIVE;}
            else if(neighbors > 3) {grid[a][b] = DEAD;}
        }
    }
}

Answer 7

@Koradalien and others have captured the key points on overall structure, but I'd add a couple of local changes that might also be useful. [ I've left in the buffer copying etc.] Essentially: You can change a bunch of the conditionals into table look ups, and remove the end of line check in Display entirely by moving it to the outer loop.

For Display:

void Display(bool grid[gridsize + 1][gridsize + 1])
{
    const char* cellImage[2] = { "  ", " *" };
    for (int a = 1; a < gridsize; a++)
    {
        for (int b = 1; b < gridsize; b++)
        {
            std::cout << cellImage[grid[a][b]];
        }
        std::cout << std::endl;
    }
}

Similarly, in live of die, (or in rule):

int count[2][3][3] =
{
    {
        { 0, 0, 0 },
        { 0, 0, 0 },
        { 0, 0, 0 }
    },
    {
        { 1, 1, 1 },
        { 1, 0, 1 },
        { 1, 1, 1 },
    }
};
bool lives[9] = { 0, 0, 0, 1 }; // zero fills the rest.
//Calculates Life or Death
void liveOrDie(bool grid[gridsize + 1][gridsize + 1])
{
    bool grid2[gridsize + 1][gridsize + 1] = {};
    CopyGrid(grid, grid2);
    for (int a = 1; a < gridsize; a++)
    {
        for (int b = 1; b < gridsize; b++)
        {
            int life = 0;
            for (int c = -1; c < 2; c++)
            {
                for (int d = -1; d < 2; d++)
                {
                    life += count[grid2[a + c][b + d]][c + 1][d + 1];
                }
            }
            if (life != 2)
                grid[a][b] = lives[life];
        }
    }
}

OK, some would say the lives array is overkill, but I put it here to demonstrate the technique. Note how you could tinker with the count array to get some easy changes to the rule.

P.S. Full marks for having the grid data have the boundary build in to simplify the rule.

Another thought on unrelated issues. The system("CLR"); is likely to cause flicker. For a console app, you are better just sending the cursor home. See existing question

This gives:

void gotoxy(int x, int y) 
{
    COORD pos = { x, y };
    HANDLE output = GetStdHandle(STD_OUTPUT_HANDLE);
    SetConsoleCursorPosition(output, pos);
}

void cursorHome()
{
    gotoxy(0, 0);
}