Wrapping around a grid with modulo

Question

I am trying to write a program that implements Conway's Game of Life on a grid of 20x60 cells. The grid should wrap around so that the left side is connected to the right side and the top is connected to the bottom.

Thus, any cell with position (0, col), will have a neighbour at (maxRow, col). Any cell with position (row, 0) will have a neighbour at (row, maxCol).

The following function is supposed to count the number of neighbouring cells. It works for coordinates not on the edges, but not for ones that are. For instance, if there are points at (0, 10), (0, 11), (0, 12), and (0, 10) is passed into the function, it will return a high number as neighbour count instead of 1. I know that the mod operator % would be helpful, but I don't understand how to use it.

{
    int i, j;
    int count = 0;
    for (i = row - 1; i <= row + 1; i++)
       for (j = col - 1; j <= col + 1; j++) 
           count += grid[i][j]; }

    if (row==maxrow-1 || row==0)
         count = count+ grid [(row-(maxrow-1))*-1][col-1]+grid[(row-(maxrow-1))*-1][col]+grid[(row-(maxrow-1))*-1][col+1];

    if (col==0 || col==maxcol-1)
         count=count +grid[row-1][(col-(maxcol-1))*-1]+grid[row][(col-(maxcol-1))*-1]+grid[row+1][(col-(maxcol-1))*-1];



    count -= grid[row][col];
    return count;
    } 

Answer 1

Before offering a solution, let me make some observations.

• Adding up some grid values and later subtracting other grid values is not a good idea. You should calculate the correct grid coordinates to begin with.

• When you write count += grid[i][j];, you are using array indices that may be invalid. For example, i = row - 1 when row is zero yields an i value of -1.

• Your code implies that maxrow is the number of rows because you're writing maxrow-1, but the name maxrow suggests a maximum row index. This is confusing. It would be better to call the number of rows numRows, and then the greatest row index is numRows - 1. Likewise, it would be better to replace maxcol with numCols.

Now to the heart of the matter. The value row - 1 can be equal to -1, and row + 1 can be equal to numRows. Both of these are invalid row indices. Similarly, col - 1 and col + 1 can result in the invalid column indices -1 and numCols. One way to solve the problem is to test for these particular values and replace them with wraparound indices:

int count = 0;
for (int i = row - 1; i <= row + 1; i++) {
  int R = i;
  if (R == -1) {
    R = numRows - 1;
  } else if (R == numRows) {
    R = 0;
  }
  for (int j = col - 1; j <= col + 1; j++) {
    if (i == row && j == col) {
      continue;  // Skip grid[row][col].
    }
    int C = j;
    if (C == -1) {
      C = numCols - 1;
    } else if (C == numCols) {
      C = 0;
    }
    count += grid[R][C];
  }
}

That's a high-performance way to solve the problem because testing and assignment are faster operations than modulo, but it's also a lot of code. We can write more concise code with the help of the modulo operator.

We would like to write i % numRows, except C++ evaluates this as -1 when i is -1. That's because the modulo operation is ambiguous for negative values and C++ has chosen an interpretation that doesn't guarantee non-negative results.

To fix this problem, we add numRows to i before taking the modulo numRows. This ensures that we're always taking the modulo of a positive number. Now we can count the number of live cells among the eight neighbors of grid[row][col] as follows.

int count = 0;
for (int i = row - 1; i <= row + 1; i++) {
  for (int j = col - 1; j <= col + 1; j++) {
    if (i == row && j == col) { 
      continue;  // Skip grid[row][col].
    }
    count += grid[(i + numRows) % numRows][(j + numCols) % numCols];
  }
}