Conways game - accessing out of bound data

Question

This is my Conway's Game of Life C code.

Function newgen checks neighboring cells, all eight of them, even if cell is on the edge of the matrix. How can I change it in a way that won't results in accessing out of bound data, and undefined behavior?

Also I have this error:

1   IntelliSense: a value of type "void *" cannot be assigned to an entity of type "int *"  

The code is:

void copy() {
  int i, j;
  for (i = j = 0; i < HEIGHT; i++) {
    for (; j < WIDTH; j++) {
      gb2[i][j] = gb[i][j];
    }
  }
}

void init() {
  int i, j;
  for (i = 0; i < HEIGHT; i++) {
    gb [i] = malloc(sizeof(int)*WIDTH);
    gb2[i] = malloc(sizeof(int)*WIDTH);
  }
  for (i = 0 ; i < HEIGHT; i++) {
    for (j = 0 ; j < WIDTH; j++) {
      gb [i][j] = 0;
    }
  }
  gb[0][0] = 1;
  gb[0][1] = 1;
  gb[1][0] = 1;
  gb[1][1] = 1;
  copy();
}

... int main() { int i; init(); newgen(); printg(); for (i = 0; i < HEIGHT; i++) { free(gb[i]); free(gb2[i]); } }

Answer 1

I have not tested the code below (and it is incomplete anyway) but you should loop over all the elements in your array and update the neighbour count. You can use a couple of loops that run over all the neighbouring cells and performs bounds checking as it goes.

You should also reset the neighbouring cell count when you start processing each cell.

void newgen()
{
    for (int i = 0; i < HEIGHT; i++)
    {
        for (int j = 0; j < WIDTH; j++)
        {
            int n = 0;

            for (int test_y = i - 1; test_y <= (i + 1); ++test_y)
            {
                for (int test_x = j - 1; test_x <= (j + 1); ++test_x)
                {
                    if ((test_x != test_y) &&
                        (test_x >= 0) && (test_x < WIDTH) &&
                        (test_y >= 0) && (test_y < HEIGHT))
                    {
                        if (gb[test_y][test_x])
                        {
                            n++;
                        }
                    }
                }
            }

            /* Process the n value here */
        }
    }
}

You could probably just have used static arrays instead of allocating along one dimension, or allocate along both dimensions. Currently it's a mixture of static and dynamic sizes which isn't a problem it just seems inconsistent.

Your Intellisense error sounds like Intellisense only handles C++ code, not C code, but that is only a guess. You can configure the compiler (I'm assuming MSVC here) to compile as C or C++ but perhaps Intellisense either does not have that option or it is configured separately.

Answer 2

In newgen() you loop from 1 to HEIGHT - 2 for the rows, which avoids out of bounds access, but for the columns you loop from 0 to WIDTH - 2, so you have out of bounds access in every line that accesses j - 1, when you are in the first column. i.e.,

for (j = 0; j < WIDTH-1; j++) {
   if (gb[i][j+1]) n++;
   if (gb[i+1][j]) n++;
   if (gb[i+1][j+1]) n++;
   if (gb[i-1][j-1]) n++; // <- Here,
   if (gb[i][j-1]) n++;   // <- here,
   if (gb[i-1][j]) n++;
   if (gb[i+1][j-1]) n++; // <- ...and here.
   if (gb[i-1][j+1]) n++; 

Begin with j equal to 1, not 0, when you begin the loop over columns:

for (j = 1; j < WIDTH-1; j++) { 

Answer 3

The IntelliSense warning is because you are using Visual C++ and the warning would be appropriate in C++. (It's not so “intelli” when you are using C.) You can avoid the warning by casting the return value of malloc to (int *), although casting the return of malloc is not recommended in C.

As for avoiding out of bounds access: do not access out of bounds. Some possible solutions include:

• Create a function to return the live/dead value of a singe cell, and check the bounds there, returning 0 if it's out of bounds. (Or you can wrap around the grid to the other side; this is nice if you want to animate, e.g., a glider on a small grid.)

• Don't include the first or last row or column in your loop, instead treat those as special cases and don't access beyond the boundaries.

• Allocate two extra rows and columns, initialize them to zero, and then don't iterate over the last row or column (i.e., treat your active grid as [1..w][1..h] but allocate w+2 columns and h+2 rows). Then you don't need a special case for the edges, but use a small amount of extra memory.