Game of Life problem with board update function in C

Question

I need help with my Game of Life implementation in C. Other posts on Stackoverflow lead me to believe that my problem was to do with dangling pointers, but after modifying my program to use a global 2D array for the game grid instead of passing it to functions which return new 2D arrays, I realized that it was a problem with my update function.

I have tried hard-coding a number of simple patterns, including gliders and oscillators, and the grid doesn't update correctly. The patterns do update the same way every time the program is run, so I don't think it's a problem of uninitialized memory causing problems. I also know that there are no cells which contain values greater than 1. Therefore, the problem must lie in my mechanisms for updating the grid.

Can someone help me find the problem? I can't find anything wrong with my code and I believe I have programmed the rules correctly.

Here are my neighbors and update functions, along with the relevant variable and constant declarations.

#define MAX_Y 10 /* height */
#define MAX_X 30 /* width */

int grid[MAX_Y][MAX_X];

int neighbors(int x, int y) {
    int dx, dy, dstx, dsty;
    int n = 0;

    for (dy = -1; dy <= 1; ++dy) {
        for (dx = -1; dx <= 1; ++dx) {
            dsty = y + dy;
            dstx = x + dx;

            if (dsty >= 0 && dsty < MAX_Y && dstx >= 0 && dstx < MAX_X)
                n += !!grid[dsty][dstx]; /* use !! so that non-zero values eval to 1 */
        }
    }
    /* (n > 0) ? printf("Point (%d,%d) has %d neighbors!\n", x, y, n) : 0; */
    return n;
}

void update(void) {
    int new[MAX_Y][MAX_X];
    memset(new, 0, sizeof(int) * MAX_Y * MAX_X);
    int i, j, n;

    for (i = 0; i < MAX_Y; ++i) {
        for (j = 0; j < MAX_X; ++j) {
            n = neighbors(i, j);

            /* alive, 2 or 3 neighbors    -> alive!
             * dead, 3 neighbors          -> alive!
             * anything else              -> dead :(
             */

            if (grid[i][j] && (n == 2 || n == 3))
                new[i][j] = 1;
            else if (!grid[i][j] && n == 3)
                new[i][j] = 1;
            else
                new[i][j] = 0;
        }
    }

    memcpy(grid, new, sizeof grid);
}

Answer 1

You should adjust the neighbors() function to omit the cell itself.

Here is a modified version:

#define MAX_Y 10 /* height */
#define MAX_X 30 /* width */

unsigned char grid[MAX_Y][MAX_X];

int neighbors(int x, int y) {
    int n = -!!grid[y][x];
    for (int dy = -1; dy <= 1; ++dy) {
        for (int dx = -1; dx <= 1; ++dx) {
            int dsty = y + dy;
            int dstx = x + dx;
            if (dsty >= 0 && dsty < MAX_Y && dstx >= 0 && dstx < MAX_X && grid[dsty][dstx])
                n++;
        }
    }
    return n;
}

void update(void) {
    int new[MAX_Y][MAX_X] = { 0 };

    for (int y = 0; y < MAX_Y; ++y) {
        for (int x = 0; x < MAX_X; ++x) {
            int n = neighbors(y, x);

            /* alive, 2 or 3 neighbors    -> alive!
             * dead, 3 neighbors          -> alive!
             * anything else              -> dead :(
             */

            new[y][x] = (grid[y][x] && n == 2) || n == 3;
        }
    }
    memcpy(grid, new, sizeof grid);
}

The neighbors() function can be simplified with fewer tests:

int neighbors(int x, int y) {
    int n = -(grid[y][x] != 0);
    int x1 = x - (x > 0);
    int x2 = x + (x < MAX_X - 1);
    int y1 = y - (y > 0);
    int y2 = y + (y < MAX_Y - 1);
    for (y = y1; y <= y2; y++) {
        for (x = x1; x <= x2; x++) {
            n += grid[y][x] != 0;
        }
    }
    return n;
}