Ytukyg

I am working on project containing cellular automat methods. What I am trying to figure is how to write function helping to find all the neighbours in a 2d array.
for example i ve got size x size 2d array [size = 4 here]

[x][n][ ][n]

[n][n][ ][n]

[ ][ ][ ][ ]

[n][n][ ][n]

Field marked as x [0,0 index] has neighbours marked as [n] -> 8 neighbours. What Im trying to do is to write a function which can find neighbours wo writting tousands of if statements

Does anybody have an idea how to do it ?
thanks

For the neighbours of element (i,j) in NxM matrix:

int above = (i-1) % N;

int below = (i+1) % N;

int left = (j-1) % M;

int right = (j+1) % M;



decltype(matrix[0][0]) *indices[8]; 

indices[0] = & matrix[above][left];

indices[1] = & matrix[above][j];

indices[2] = & matrix[above][right];

indices[3] = & matrix[i][left];

// Skip matrix[i][j]

indices[4] = & matrix[i][right];

indices[5] = & matrix[below][left];

indices[6] = & matrix[below][j];

indices[7] = & matrix[below][right];

Suppose you are in cell (i, j). Then, on an infinite grid, your neighbors should be [(i-1, j-1), (i-1,j), (i-1, j+1), (i, j-1), (i, j+1), (i+1, j-1), (i+1, j), (i+1, j+1)].

However, since the grid is finite some of the above values will get outside the bounds. But we know modular arithmetic: 4 % 3 = 1 and -1 % 3 = 2. So, if the grid is of size n, m you only need to apply %n, %m on the above list to get the proper list of neighbors: [((i-1) % n, (j-1) % m), ((i-1) % n,j), ((i-1) % n, (j+1) % m), (i, (j-1) % m), (i, (j+1) % m), ((i+1) % n, (j-1) % m), ((i+1) % n, j), ((i+1) % n, (j+1) % m)]

That works if your coordinates are between 0 and n and between 0 and m. If you start with 1 then you need to tweak the above by doing a -1 and a +1 somewhere.

For your case n=m=4 and (i, j) = (0, 0). The first list is [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]. Applying the modulus operations you get to [(3, 3), (3, 0), (3, 1), (0, 3), (0, 1), (1, 3), (1, 0), (1, 1)] which are exactly the squares marked [n] in your picture.

Add and subtract one from the coordinates, in all possible permutations. Results outside the boundaries wrap around (e.g. -1 becomes 3 and 4 becomes 0). Just a couple of simple loops needed basically.

Something like

// Find the closest neighbours (one step) from the coordinates [x,y]

// The max coordinates is max_x,max_y

// Note: Does not contain any error checking (for valid coordinates)

std::vector<std::pair<int, int>> getNeighbours(int x, int y, int max_x, int max_y)

{

    std::vector<std::pair<int, int>> neighbours;



    for (int dx = -1; dx <= 1; ++dx)

    {

        for (int dy = -1; dy <= 1; ++dy)

        {

            // Skip the coordinates [x,y]

            if (dx == 0 && dy == 0)

                continue;



            int nx = x + dx;

            int ny = y + dy;



            // If the new coordinates goes out of bounds, wrap them around

            if (nx < 0)

                nx = max_x;

            else if (nx > max_x)

                nx = 0;



            if (ny < 0)

                ny = max_y;

            else if (ny > max_y)

                ny = 0;



            // Add neighbouring coordinates to result

            neighbours.push_back(std::make_pair(nx, ny));

        }

    }



    return neighbours;

}

Example use for you:

auto n = getNeighbours(0, 0, 3, 3);

for (const auto& p : n)

    std::cout << '[' << p.first << ',' << p.second << "]n";

Prints out

[3,3]

[3,0]

[3,1]

[0,3]

[0,1]

[1,3]

[1,0]

[1,1]

which is the correct answer.