Finding neighbors of 2d array when represented as 1d array

Question

I have a 2d array that I converted to a 1d array. In the 1d representation, how can I find all 8 neighbors of a cell, accounting for wrap-around?

The context of this is that I have a 2d game board that I store in memory as a 1d chunk of memory. I need to be able to find the memory locations of all 8 neighboring cells in the game board. The problem I am having is accounting for the board wrap-around on the edges (especially if the cell is in the corner of the 2d array).

For example, if the cell is in the upper right corner, the top neighbor is at the bottom right corner, etc.

I know the board size when I am calculating this.

EDIT: It might be pertinent to mention that I am doing this in MIPS assembly...

Answer 1

You just need a function that can map an arbitrary position to a position that is contained within the array.

You must decompose the problem in two steps:

• wrapping
• mapping 2d coords to 1d

Wrapping can be done easily with modulo operator, something like

struct pos { int x,y };

pos wrap(pos p)
{
  pos p2 = p;

  if (p.x >= WIDTH)
    p.x %= WIDTH;
  else if (p.x < 0)
    p.x += WIDTH;

  if (p.y >= HEIGHT)
    ... same thing
}

Then you'll have a position that is surely contained inside the array, you need to map it do 1d, that's even easier:

int flatten(pos p)
{
   return p.x*WIDTH + p.y;
}

so you can combine them:

int fpos = flatten(wrap({30,20}));

and you are done.

Answer 2

This is python code, but the logic, using a simple 1d flat list, should be clear enough:

def neighbors(i, w, h, mode=8):
    """Return a list of neighbors.

    Works as like a 2d graph of 'w' width and 'h' height with boundaries.

    Args:
        i(int): 1d index
        w(int): width of the graph.
        h(int): height of the graph.
        mode(int): 8 for eight directions (includes diagonals); else for
            4 directions (top, down, left, right).

    Returns:
        list
    """
    size = w * h
    neighbors = []
    if i - w >= 0:
        neighbors.append(i - w)  # north
    if i % w != 0:
        neighbors.append(i - 1)  # west

    if (i + 1) % w != 0:
        neighbors.append(i + 1)  # east

    if i + w < size:
        neighbors.append(i + w)  # south

    if mode == 8:
        if ((i - w - 1) >= 0) and (i % w != 0):
            neighbors.append(i - w - 1)  # northwest

        if ((i - w + 1) >= 0) and ((i + 1) % w != 0):
            neighbors.append(i - w + 1)  # northeast

        if ((i + w - 1) < size) and (i % w != 0):
            neighbors.append(i + w - 1)  # southwest

        if ((i + w + 1) < size) and ((i + 1) % w != 0):
            neighbors.append(i + w + 1)  # southeast
    return neighbors

To test/print it:

if __name__ == '__main__':
    W = 3  # width
    H = 3  # height

    def show(start, neighbors):
        """Simple display of an 2d table.

        Args:
            start(int): initial position (shown as 'S')
            neighbors(list): list of positions (draw as their values)
        """
        for y in range(H):
            print("|", end="")
            for x in range(W):
                i = y * W + x
                if i == start:
                    c = "  S|"
                elif i in neighbors:
                    c = "%3d|" % i
                else:
                    c = "  .|"

                print(c, end="")
            print()

    for i in range(W * H):
        print()
        n = neighbors(i, W, H)
        print("neighbors(%d) of '%d':" % (len(n), i), n)
        show(i, n)

Results:

neighbors(3) of '0': [1, 3, 4]
|  S|  1|  .|
|  3|  4|  .|
|  .|  .|  .|

neighbors(5) of '1': [0, 2, 4, 3, 5]
|  0|  S|  2|
|  3|  4|  5|
|  .|  .|  .|

neighbors(3) of '2': [1, 5, 4]
|  .|  1|  S|
|  .|  4|  5|
|  .|  .|  .|

neighbors(5) of '3': [0, 4, 6, 1, 7]
|  0|  1|  .|
|  S|  4|  .|
|  6|  7|  .|

neighbors(8) of '4': [1, 3, 5, 7, 0, 2, 6, 8]
|  0|  1|  2|
|  3|  S|  5|
|  6|  7|  8|

neighbors(5) of '5': [2, 4, 8, 1, 7]
|  .|  1|  2|
|  .|  4|  S|
|  .|  7|  8|

neighbors(3) of '6': [3, 7, 4]
|  .|  .|  .|
|  3|  4|  .|
|  S|  7|  .|

neighbors(5) of '7': [4, 6, 8, 3, 5]
|  .|  .|  .|
|  3|  4|  5|
|  6|  S|  8|

neighbors(3) of '8': [5, 7, 4]
|  .|  .|  .|
|  .|  4|  5|
|  .|  7|  S|