Навигация по двумерному массиву, сопоставленному с 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;
}

Для справки: сетка 7х5 с индексами (с границами):

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

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

РЕДАКТИРОВАТЬ: функция 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 это ширина х высота. Делая это более явным, вот вывод:

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;