Game of Life generation procession algorithm

Question

I've tried to make Game of Life in console and this is the algorithm I used to generate new generation:

void processGeneration() {
 population = 0;
 int neighbors;
 int tempGrid[ROWS][COLS];
 for(int i = 0; i < ROWS; i++) {
 for(int j = 0; j < COLS; j++) {
 if (grid[i][j] == -1) {
 continue;
 }
 neighbors = countNeighbors(i, j);
 if (grid[i][j] == 0) {
 if (neighbors == 3) {
 tempGrid[i][j] = 1;
 } else {
 tempGrid[i][j] = 0;
 }
 } else if (grid[i][j] == 1) {
 if (neighbors < 2 || neighbors > 3) {
 tempGrid[i][j] = 0;
 } else {
 tempGrid[i][j] = 1;
 }
 }
 }
 }
 for(int i = 0; i < ROWS; i++) {
 for(int j = 0; j < COLS; j++) {
 if (grid[i][j] == -1) {
 continue;
 }
 if (tempGrid[i][j] == 1) {
 population++;
 }
 grid[i][j] = tempGrid[i][j];
 }
 }
}

I'm a bit uncertain if what I did was right, so could you check the algorithm? Also, grid is the grid where I save the cells in and I just use tempGrid to change the values and then copy them to the grid.

int countNeighbors(int row, int col) {
 int neighbors = 0;
 for(int i = row - 1; i < row + 2; i++) {
 for(int j = col - 1; j < col + 2; j++) {
 if (i == row && j == col) {
 continue;
 }
 if (i > -1 && j > -1 && i < ROWS && j < COLS) {
 neighbors += grid[i][j];
 }
 }
 }
 return neighbors;
}

• Jamal: Have you not tested it yourself?
• gues532: @Jamal it's actually my first time ever trying to implement the game of life, although I searched for common shaped generated by this, I can recognize /some/ shapes produced with my algorithm but I just want to be sure of it

Answer 1

Your algorithms looks correct, I could not find any obvious mistakes.

On the other hand, I have a suggestion towards the readability of your code: Use more functions that tell the reader what you're doing right now. For example, instead of saying

if (grid[i][j] == 0) {
 if (neighbors == 3) {
 tempGrid[i][j] = 1;
 } else {
 tempGrid[i][j] = 0;
 }
}

you could write:

int cellIsDead(int x, int y) { return grid[i][j] == 0; }
int hasEnoughNeighboursToComeToLife(int x, int y) { return countNeighbors(x, y) == 3 }
void makeCellComeAlive(int x, int y) { tempGrid[i][j] = 1; }
if (cellisDead(i, j) && hasEnoughNeighboursToComeToLife(i, j)) {
 makeCellComeAlive(i, j);
}

Yes, this takes more time and also probably some global variables (although grid already looks global, so no issue), but it is a) easier to read (see how it almost reads like the rules of the game?) and b) easier to prove to be correct using unit tests. And any decent compiler will inline these function calls at compile time, so no runtime overhead.

Answer 2

You can use the ternary operator in a few places:

if (neighbors == 3) {
 tempGrid[i][j] = 1;
} else {
 tempGrid[i][j] = 0;
}

can be shorten to:

tempGrid[i][j] = (neighbors == 3) ? 1 : 0;

The function countNeighbors is not efficient: you are scanning 9 values and discarding 5 of those. You should instead hard code the four values. [Oops: I actually misunderstood the rules. See comments.]

There is also the business with -1. I assume you are using this to denote the boundaries. It's not clear to me if this trick simplifies or complicates the code. If you don't use -1 values, you would only need to modify countNeighbors to correctly deal with edges and corners. That method would be more complex.

In the following paragraph, I am proposing an alternative design. I am not claiming it is better. Instead of having grid[][] and tempGrid[][], you could have grid[][] and neighborCounts[][]. You call some method to fill the neighborCounts grid only once. That method would deal separately with corners, edges and inner cells. After you have completed neighborCounts you can directly modify grid.

• gues532: why its not efficient ? not sure I understand, also I just though of something neighbors += grid[i][j]; in countNeighbors will cause problems if one of the cells is a border right ? need to check if it's -1 and it it is use continue before adding to the neighbors
• thriqon: Yes, the loop does look inefficient, but I'm pretty sure a compiler will unroll it and get rid of the one case where you are checking for the current position.
• gues532: before doing it in a loop I just made a function that gets i and j and checks if in grid[i][j] cell is alive and I just sent the 8 different neighbors each time to the function, is it more effective ? Also what about what I said about this : "also I just though of something neighbors += grid[i][j]; in countNeighbors will cause problems if one of the cells is a border right ? need to check if it's -1 and it it is use continue before adding to the neighbors"
• toto2: I'm sorry. I had misunderstood the rules: I thought only the four "main" neighbors were checked (up, down, left, right). So your neighbor scanning algorithm was not inefficient.
• toto2: I'm not sure I understand your second comment. What you are currently doing seems OK.