Learning C: Conway's Game of Life

Question

I'm learning C, so as a practice problem I implemented Conway's Game of Life. For anyone unfamiliar, the problem is set out here. To summarize, there is a grid of "cells" that can be either alive or dead. This grid is updated in "steps". In each step, live cells with 2 or 3 live neighbors survive, dead cells with 3 live neighbors come alive, and live cells with less than 2 or more than 3 live neighbors die.

I'm mostly looking for C advice (anything I might be doing badly in terms of pointers, references, memory management etc.). That said, architecture and control flow critiques are 100% welcome as well.

One of the specific things I'm wondering about is my logic for not checking neighbors that don't exist on the edges (my implementation assumes cells that are off the board to be dead). Specifically, I'm wondering if there's a more elegant way to implement that than the way I've done it?

Code:

#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include <unistd.h>
#include <time.h>


int i;
int j;
bool** emptyBoard();
void initialPosition(bool** board, char startPos[]);
void printArray(bool** board);
void freeArray(bool** board);
bool** step(bool** board);
void wait(float s);

int width = 50;
int height = 50; 


void initialPosition(bool** emptyBoard, char startPos[] ) {
    for(i=0; i < width; i++) {
        for(j = 0; j < height; j++) {
            *(emptyBoard[i] + j) = (bool) (startPos[(i * width) + j] - '0');
        }
    }
}

bool** emptyBoard() {
    bool **board;//pointer to pointer

    board = malloc(sizeof (bool *) * width);//array of pointers (each pointer to array of ints)
    for (i = 0; i < width; i++) {
        *(board + i) = malloc(sizeof (bool) * height);
    }

    for (i = 0; i < width; i++) {
        for (j = 0; j < height; j++){
            bool c = 0;
            *(board[i] + j) = c;
        }
    }

    return(board);
}

void printArray(bool** board) {
    for (i = 0;i < width; i++) {
        for (j = 0; j < height; j++){
            if(*(*(board + i) + j) == 0) {
                printf("   ");
            } else {
                printf(" o ");
            }
            //printf("%i ", *(*(board + i) + j));
        }
        printf("\n");
    }
}

void freeArray(bool** board){
    for (i = 0; i < width; i++) {
        free(board[i]);
        }
    free(board);
}

bool** step(bool** board) {
    bool** newBoard = emptyBoard();
    int neighbors;
    int k;
    for(i=0; i < width; i++) {
        for(j = 0; j < height; j++) {
            neighbors = 0;
            if(i > 0) {
                if (*(*(board + i - 1) + j) == 1) {//i-1, j if i > 0
                    neighbors++;
                } 

                if(j > 0) {//i-1, j if i > 0 and j > 0
                    if (*(*(board + i - 1) + j - 1) == 1) {
                    neighbors++;
                    } 
                }

                if (j < width - 1) {
                    if (*(*(board + i - 1) + j + 1) == 1) {//i-1, j+1 if j > 0 and j < width - 1
                        neighbors++;
                    } 
                }
            }

            if(j > 0) {
                if (*(*(board + i) + j - 1) == 1) {//i, j-1 if j > 0
                    neighbors++;
                }
                if (i < height - 1){ 
                    if (*(*(board + i + 1) + j - 1) == 1) {//i + 1, j -z if j > 0 and i < height - 1
                        neighbors++;
                    } 
                }
            }

            if(j < width - 1) {
                 if (*(*(board + i) + j + 1) == 1) {//i, j+1 if j < width -
                    neighbors++;
                }    
            }

            if(i < height - 1) {
                if (*(*(board + i + 1) + j) == 1) {
                    neighbors++;
                } 
                if(j < width - 1){
                    if (*(*(board + i + 1) + j + 1) == 1) {//if i < height - 1 and j < width - 1, i+1, j+1
                        neighbors++;
                    }
                }
            }

            if (*(*(board + i) + j) == 0) {
                if(neighbors == 3) {
                    *(*(newBoard + i) + j) = (bool) 1;
                } else {
                    *(*(newBoard + i) + j) = (bool) 0;
                }
            } else if (*(*(board + i) + j) == 1) {
                if(neighbors < 2) {
                    *(*(newBoard + i) + j) = (bool) 0;
                } else if (neighbors == 2 || neighbors == 3) {
                    *(*(newBoard + i) + j) = (bool) 1;
                } else if (neighbors > 3) {
                    *(*(newBoard + i) + j) = (bool) 0;
                } 
            } 
        }
    }

    freeArray(board);
    return(newBoard);
}

void wait(float s) {
    int now = clock();
    int then = clock() + (CLOCKS_PER_SEC * s);
    while(clock() != then) {

    }
}

int main() {
    bool** board = emptyBoard();
    printArray(board);
    printf("--------------\n");
    initialPosition(board, "0000000000000000000000000000000000000000000000000"
                           "0000000000000000000000000100000000000000000000000"
                            "0000000000000000000000010100000000000000000000000"
                            "0000000000000110000001100000000000011000000000000"
                            "0000000000001000100001100000000000011000000000000"
                            "0110000000010000010001100000000000000000000000000"
                            "0110000000010001011000010100000000000000000000000"
                            "0000000000010000010000000100000000000000000000000"
                            "0000000000001000100000000000000000000000000000000"
                            "0000000000000110000000000000000000000000000000000");
    printArray(board);

    while(true){
        //sleep(1);
        wait(0.25);
        printf("\e[1;1H\e[2J");
        board = step(board);
        printArray(board);
    }

    freeArray(board);
}

Answer 1

Here are some things that may help you improve your code.

Fix the bug

The code currently includes this line in initialPosition:

*(emptyBoard[i] + j) = (bool) (startPos[(i * width) + j] - '0');

Since each row is width cells wide, we should be multiplying by j rather than i.

*(emptyBoard[i] + j) = (bool) (startPos[j * width + i] - '0');

Eliminate unused variables

The variable k in step is declared code but never used. Similarly, now in wait is defined but unused. Since unused variables are a sign of poor code quality, you should seek to eliminate them. Your compiler is probably smart enough to warn you about such things if you know how to ask it to do so.

Eliminate global variables where practical

Having routines dependent on global variables makes it that much more difficult to understand the logic and introduces many opportunities for error. Eliminating global variables where practical is always a good idea. In this case, I would suggest you keep them as global but make them both const to clearly signal to the reader that these are fixed constants. However i and j should simply be declared within each loop. Specifically instead of this:

for(i=0; i < width; i++) {

Write this:

for(int i=0; i < width; i++) {

Use consistent formatting

The code as posted has inconsistent indentation (e.g. the loop in freeArray) and inconsistent use of whitespace (the spacing within each for loop is inconsistent) which makes it harder to read and understand. Pick a style and apply it consistently.

Try to write portable code

It's a subtle point, but the \e escape sequence is not actually defined in the ISO standard for C. For that reason, a safer alternative would be to use \x1b.

Simplify expressions

I've already mentioned this line in initialPosition:

*(emptyBoard[i] + j) = (bool) (startPos[(i * width) + j] - '0');

The left side could simply be emptyBoard[i][j] = which is much clearer. The right side could be simplified a bit as well. I'd write the line like this:

emptyBoard[i][j] = startPos[j * width + i] != '0';

Note also that I've changed it mathematically per the first point. However, see the suggestion below for an alternative scheme.

Prefer a single block to pointer-to-pointers schemes

The code would likely be much simpler and easier to read if, instead of the current pointer-to-pointers approach the whole board is simply allocated in a single structure. Then you can use the same sort of indexing as shown above with board[i + j * width]. I think that would be easier for most people to read and understand as contrasted with lines like this:

if(*(*(board + i) + j) == 0) {

For instance the emptyBoard() function could be reduced to a single line:

bool* emptyBoard() {
    return calloc((width + 2) * (height + 2), sizeof(bool));
}

Check the return value of malloc

If the program runs out of memory, a call to malloc can fail. The only indication for this is that the call will return a NULL pointer. You should check for this and avoid dereferencing a NULL pointer (which typically causes a program crash).

Simplify range checking by eliminating the need for it

The existing step code does a lot of checking to make sure that all of the checked neighbors are in range. That's much better than not checking and overrunning the bounds of the board, but there's a simpler way to accomplish the same effect. The way to do it is to allocate a slightly larger array with two additional rows and two additional columns to act as a frame around the real board. If you then iterate only over the real board, there is no need for further range checking.

Separate functions into small chunks

The step function does three things. It allocates a new array, computes the neighbor counts for each cell and then exchanges the old and new arrays. I'd suggest that computing the neighbor count for a particular cell would be better done as a separate function.

If you follow these suggestions, the step and its helper function are much simpler:

static int getNeighborCount(const bool *location) {
    static const ssize_t deltas[8] = {
        -2-1-width, -2-width, -2+1-width,
            -1,             +1,
        +2-1+width, +2+width, +2+1+width,
    };
    int neighbors = 0;
    for (int i=0; i < 8; ++i) {
        neighbors += *(location + deltas[i]);
    }
    return neighbors;
}

bool* step(bool* board) {
    bool* newBoard = emptyBoard();
    if (newBoard == NULL) {
        return NULL;
    }
    bool* dst = newBoard + 3 + width;
    bool* src = board + 3 + width; 
    for (int i = 0; i < width; i++) {
        for (int j = 0; j < height; j++) {
            int livingNeighbors = getNeighborCount(src);
            *dst = (livingNeighbors == 3) || (livingNeighbors == 2 && *src); 
            ++src;
            ++dst;
        }
        src += 2;
        dst += 2;
    }
    freeArray(board);
    return(newBoard);
}

Use library functions

The code includes this function:

void wait(float s) {
    int then = clock() + (CLOCKS_PER_SEC * s);
    while(clock() != then) {
    }
}

It's probably better to use nanosleep here. That function is a POSIX function, rather than a C standard library call, but it appears that you are running on a POSIX machine anyway, judging by the inclusion of unistd.h in the code.

Answer 2

When accessing array elements, don't use the clunky *(board + i) notation. Use board[i]. (You're already doing this in some places, and you should be consistent.)

Eliminate the use of global i and j variables as loop variables. Use local variables instead. This can help with optimization, and avoids problems where a function called while in a loop in another function can mess up the latter's looping.

There is no verification that the startPos string in initialPosition is long enough. You can read past the end of it. If the string is not long enough, you can either set the rest of the elements to 0 (false) and continue, or report an error. Rather than computing the index into startPos all the time, you can increment the pointer with *startPos++. This would also make it easier to check for reaching the end of the string.

You need to clarify to yourself if your board matrix is row major or column major. Your usage in most of the code has it as column major, but your printArray function will display it transposed, with the columns running horizontally. While this is not apparent with a square board, you can see the difference when width does not equal height.

For readability, in emptyBoard your initialization of the board elements should be board[i][j] = false;. You don't need to use the c local variable. And you should check the value returned by malloc for errors (it can return NULL). The two loops here can be combined into one, by initializing each new allocated board[i] element when it is allocated.

printArray can be simplified with puts(board[i][j] == 0 ? " " : " o ");. Or, since board[i][j] is a bool (which will have a value of 0 or 1), you can use an array reference to pick which string to output.

The step function can make use of a bool's 0 or 1 values by using addition instead of if statements. neighbors += board[i][j]; The assignments to the new board elements should use the predefined true and false macros rather than typecasting integer values. Then we can compress that big nested if chunk with one line:

newboard[i][j] = neighbors == 3 || (neighbors == 2 && board[i][j] == true);

The way to avoid having all those if checks when updating the board is to create board with a border around it. This border (top, left, bottom, and right) will be one extra row/column that is always 0. It is never written to. So during the board you can access adjacent elements without having to check for out-of-bounds array accesses. Appropriate changes to your loop indexing would need to be made (e.g., looping from 1 to width inclusive).

In wait, the typical way to compute the end time is as an offset from the already saved now, so you'd have int then = now + (CLOCKS_PER_SEC * s);. This avoids a second call to a library function that will probably return the same value, and avoid longer delays if the value returned has increased (possibly because the system is busy and some other process was using the CPU).

The indentation of the string passed to initialPosition is slightly off. This string could be potentially be stored in a static or global variable, or read from input (a file or from the command line).

Note that many console windows these days do not support the ANSI escape sequences. A comment to explain what they are doing would be helpful for future readers. I remember what the J escape sequence is, but not H.

Answer 3

Reallocation

I will recommend against repeatedly allocating and deleting boards. Allocate two up front, pass both into step(), returning void, and then swap them in main. First off, this will be faster, as you don't have to do the allocations and frees. Second, this will avoid potential memory fragmentation or issues involving sub-optimal implementations of malloc. Third, this will allow you to, if needed, completely eliminate malloc and free usage. (This might be needed if you want to move the implementation to a microcontroller, like Adafruit's.)

This might not be appropriate if you are dynamically sizing the board, but you aren't doing that. If you do dynamic sizing, you might want to make the board a structure including the width, height, and data pointer, and other things may get interesting.

I might suggest (inside step()) the names current and next instead of board and newBoard, but that's a matter of taste.

Accessors

Depending on your usage, you might want a macro or inline-able function to access a particular numbered cell in the board. Done right, this could greatly simplify adding dynamic sizing at a later time. For instance, with your original layout:

/* macro version */
#define CELL(board,x,y) (((x)>=0)&&((y)>=0)&&((x)<width)&&((y)<height)&&board[x][y])
/* inline-able version */
bool CELL(bool**board,int x,int y){return (x>=0)&&(y>=0)&&(x<width)&(y<height)&&board[x][y]; }
static bool dummycell;
bool*CELL_ptr(bool**board,int x,int y){
    if ((x>=0)&&(y>=0)&&(x<width)&(y<height)) {
        return &board[x][y];
    } else {
         dummycell = false;
         return &dummycell;
    }
}

You could make a set_CELL as well, or write *CELL_ptr(board,x,y) = newvalue;

Using @Edward's variant, the bounds checks could be dropped, and the array access becomes board[x + y*width]. If the board then becomes a structure, the accessors would then receive that structure and do the relevant work.

printArray

The function printArray() includes the line

if(*(*(board + i) + j) == 0) {

Do not compare bool values with int constants. (There is a classic bug of writing if (boolvalue == 1) and having boolvalue be 2.) Use the boolean operators, so this line could be:

if(!*(*(board + i) + j)) {

You might want to do the true case first instead of the false, which would make that line:

if(*(*(board + i) + j)) {

The current printing uses three character positions per cell. This means your 50x50 board requires 50 lines by 150 columns. I suggest using fewer characters per cell.

This function could also benefit from @Edward's technique with variable bool *src, even if only on a line by line basis.