当表示为1d数组时，查找2d数组的邻居

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?

我有一个2d数组，我转换为1d数组。在1d表示中，如何找到单元格的所有8个邻居，从而解决环绕？

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).

这样的背景是我有一个2D游戏板，我将其作为1d内存存储在内存中。我需要能够找到游戏板中所有8个相邻单元的存储位置。我遇到的问题是考虑边缘上的电路板环绕（特别是如果单元格位于2d数组的角落）。

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...

编辑：可能有必要提到我在MIPS组装中这样做...

2 个解决方案

#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
将2d coords映射到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:

那么你将拥有一个肯定包含在数组中的位置，你需要将它映射到1d，这更容易：

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.

你完成了

#2

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

这是python代码，但使用简单的1d平面列表的逻辑应该足够清楚：

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|

#1