用边界条件导航映射到1D的2D阵列

Question

我试图实现生活的游戏，重点在于效率，以及模式匹配的功能。模式是闪光灯，滑翔机，十字架等

我有一个世界的一维数组，以及宽度和高度。为了找到我想要计算Moore邻域的索引的邻居，然后检查它们是否为散列，如果它们增加了get_neighbours函数的返回变量。南北方似乎有效，但东方和西方不起作用。 NE，SE，SW，NW都基于先前的逻辑（即，在西部向北）。

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; 
} 

对于模式匹配，我试图使用与上面相同的逻辑来构建5x5子数组。这基本上使用“读头”。从所提供的位置向东行进，直到它移动了5个空间。然后，它返回到原始位置，向南移动正确的行数，然后再向东移动，直到我们收集了25个索引。

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; 

} 

至于它这样做，它建立在世界上的子阵列，那么我可以strcmp（）的这对字符串的模式。

int cpu_get_crosses() { 
    int crosses = 0; 

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

作为参考，7X5网格指数（含边界）：

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 

我很好奇，可以让我来计算摩尔附近的指数，同时保留的边界是什么逻辑条件，以便我可以正确计算邻居和子数组（因为这两者都使用相同的逻辑）。

编辑：如果任何googlers需要它的子数组函数。

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

你索引你在逐行方式排列：index(i, j) = j * grid_width + i为i=0..grid_width-1, j=0..grid_height-1。让我们把loc的index(i, j)结果和反向index得到i和j：

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

往东走加一i，一个往西走下降，两者模宽度：

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; 

备注：

1. (i + grid_width - 1) % grid_width等于mod(i - 1, grid_width)
2. x % M = (k * M + x) % M任何积分k，这让我们我们loc = j * grid_width + i替换i在任何表达式模grid_width，以避免在第一位置计算i）

通过一个模数的高度等于添加grid_width和增加j由total包装total是宽x高。使其更明确，这里的推导：

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;