Navigating a 2D array mapped to 1D with boundary conditions

Question

I'm attempting to implement the game of life with a focus on efficiency, as well functionality for pattern matching. Where patterns are blinkers, gliders, crosses, etc.

I've got a 1D array for the world, as well as a width and height. In order to find the neighbours I want to calculate the indices of the Moore neighbourhood, then check if these are hashes, if they are this increases the return variable for the get_neighbours function. North and south appears to work, but east and west do not. NE, SE, SW, NW are all based upon the previous logic (i.e. go north on west).

int get_neighbours(int loc) {
    int neighbours = 0;

    int n = mod(loc - grid_width, total);
    int e = mod(loc + 1, grid_width) + grid_width;
    int s = mod(loc + grid_width, total);
    int w = mod(loc - 1, grid_width) + grid_width;
    int nw = mod(w - grid_width, total);
    int ne = mod(e - grid_width, total);
    int se = mod(e + grid_width, total);
    int sw = mod(w + grid_width, total);

    //Northwest
    if (grid[nw] == '#') {
        neighbours++;
    }
    //North
    if (grid[n] == '#') {
        neighbours++;
    }
    //Northeast
    if (grid[ne] == '#') {
        neighbours++;
    }
    //East
    if (grid[e] == '#') {
        neighbours++;
    }
    //Southeast
    if (grid[se] == '#') {
        neighbours++;
    }
    //South
    if (grid[s] == '#') {
        neighbours++;
    }
    //Southwest
    if (grid[sw] == '#') {
        neighbours++;
    }
    //West
    if (grid[w] == '#') {
        neighbours++;
    }
    return neighbours;
}

int mod(int a, int b) {
    int ret = a % b;
    if (b < 0) {
        return mod(-a, -b);
    }
    else if (ret < 0) {
        ret += b;
    }
    return ret;
}

For the pattern matching, I attempted to use the same logic as above in order to build a 5x5 subarray. This essentially uses a "read head." Which steps through the world from the provided location east, until it has moved 5 spaces. Then, it returns to the original position and moves south the correct number of rows, before moving East again, until we have collected 25 indices.

char *get_subarray(int loc) {
    char *subarray;
    subarray = malloc(sizeof(char) * 25);

    int i = 0;
    int ptr = loc;

    while (i < 25) {
        subarray[i] = grid[ptr];
        if ((i + 1) % 5 == 0) {
            //return the read head to the original location, then travel south through the grid once for each of the times we have traversed a row
            ptr = loc;
            for (int k = 0; k <= (i / 5); k++) {
                ptr = mod(ptr + grid_width, total);
            }
        } else {
            ptr = mod(ptr + 1, grid_width) + grid_width;
        }
        i++;
    }
    subarray[i] = '\0';
    return subarray;

}

As it does so, it builds the subarray from the world, then I can strcmp() this against the string for a pattern.

int cpu_get_crosses() {
    int crosses = 0;

    for (int i = 0; i < total; i++) {
        if (strcmp(get_subarray(i), "       #   # #   #       ") == 0) {
            crosses++;
        }
    }
    return crosses;
}

For reference, a 7x5 grid with indices (with boundaries):

34|28 29 30 31 32 33 34|28
--|--------------------|--
6 |0  1  2  3  4  5  6 |0
13|7  8  9  10 11 12 13|7 
20|14 15 16 17 18 19 20|14
27|21 22 23 24 25 26 27|21
34|28 29 30 31 32 33 34|28
--|--------------------|--
6 |0  1  2  3  4  5  6 |0

I'm curious as to what logic would allow me to calculate the indices for the Moore neighbourhood whilst preserving the boundary conditions, so that I can calculate neighbours and the subarray correctly (as these both would use the same logic).

EDIT: Subarray function if any googlers want it.

char *get_subarray(int loc) {
    char *subarray;
    subarray = malloc(sizeof(char) * 25); //5x5 (=25) subarray

    int i = 0;
    int row = loc / grid_width;
    int ptr = loc;

    while (i < 25) {
        subarray[i] = grid[ptr];
        if ((i + 1) % 5 == 0) {
            //return the read head to the original location, then travel south through the grid once for each of the times we have traversed a row
            ptr = loc;
            for (int k = 0; k <= (i / 5); k++) {
                ptr = mod(ptr + grid_width, total);
            }
            row = ptr / grid_width;
        } else {
            ptr = mod(ptr + 1, grid_width) + row * grid_width;
        }
        i++;
    }
    subarray[i] = '\0';
    return subarray;
}

Answer 1

You're indexing your array in a row-wise fashion: index(i, j) = j * grid_width + i for i=0..grid_width-1, j=0..grid_height-1. Let's call loc the result of index(i, j) and reverse index to get i and j:

int i = loc % grid_width;
int j = loc / grid_width;

To go east increase i by one, to go west decrease by one, both modulo the width:

int e = j * grid_width + (i + 1) % grid_width
      = j * grid_width + ((j * grid_width + i) + 1) % grid_width
      = j * grid_width + (loc + 1) % grid_width;
int w = j * grid_width + (i + grid_width - 1) % grid_width
      = j * grid_width + ((j * grid_width + i) + grid_width - 1) % grid_width
      = j * grid_width + (loc + grid_width - 1) % grid_width;

Note:

1. (i + grid_width - 1) % grid_width is equal to mod(i - 1, grid_width)
2. x % M = (k * M + x) % M for any integral k, this let's us replace i in any expression modulo grid_width with loc = j * grid_width + i to avoid computing i in the first place ;)

Increasing j by one modulo the height is equal to adding grid_width and wrapping by total since total is width x height. Making it more explicit, here's the derivation:

int j1 = (j + 1) % grid_height;
int s = j1 * grid_width + i
      = ((j + 1) % grid_height) * grid_width + i
      = ((j + 1) * grid_width) % (grid_height * grid_width) + i
      = ((j + 1) * grid_width) % total + i
      = (j * grid_width + grid_width + i) % total
      = ((j * grid_width + i) + grid_width) % total
      = (loc + grid_width) % total;
// analogue for j0 = (j + grid_height - 1) % grid_height;
int n = (loc + total - grid_width) % total;