Навигация по 2D-массиву, сопоставленному с 1D с граничными условиями

Question

Я пытаюсь реализовать жизненную игру с акцентом на эффективность, а также функциональность для сопоставления шаблонов. Где модели - мигалки, планеры, кресты и т. Д.

У меня есть 1D массив для мира, а также ширина и высота. Чтобы найти соседей, я хочу рассчитать индексы окрестности Мура, а затем проверить, являются ли эти хеши, если они это увеличивают возвращаемую переменную для функции 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 

Я любопытно, что логика позволили бы мне вычислить индексы для окрестностей Мура, сохраняя границу условий, так что я могу правильно вычислить соседние и подмассивы (так как они оба будут использовать одну и ту же логику).

EDIT: Функция Subarray, если это требуется.

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, это пусть это Заменит i в любом выражении по модулю grid_width с loc = j * grid_width + i, чтобы избежать вычислений i в первую очередь;)

Увеличения j одной по модулю высота равна добавлению grid_width и обертывание 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;