我有一个二维数组,我转换为一维数组。在1d表示中,我怎样才能找到一个单元的所有8个邻居,并计算环绕?查找2D阵列的邻居时表示为一维数组
这样做的上下文是我有存储在存储器中作为存储器中的一维块的2D游戏板。我需要能够找到游戏板中所有8个相邻单元的内存位置。我遇到的问题是占板缠绕在边缘上(特别是如果该细胞是在2D阵列的角部)。
例如,如果该细胞是在右上角,上面的邻居是在右下角,等
我知道当我计算这个电路板尺寸。
编辑:这可能是有关一提的是,我在MIPS汇编这样做......
我有一个二维数组,我转换为一维数组。在1d表示中,我怎样才能找到一个单元的所有8个邻居,并计算环绕?查找2D阵列的邻居时表示为一维数组
这样做的上下文是我有存储在存储器中作为存储器中的一维块的2D游戏板。我需要能够找到游戏板中所有8个相邻单元的内存位置。我遇到的问题是占板缠绕在边缘上(特别是如果该细胞是在2D阵列的角部)。
例如,如果该细胞是在右上角,上面的邻居是在右下角,等
我知道当我计算这个电路板尺寸。
编辑:这可能是有关一提的是,我在MIPS汇编这样做......
你只需要能够映射到包含在数组中的位置的任意位置的功能。
您必须将问题分解分为两步:
包装可以用模运算很容易做到,像
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
}
然后你就会有这确实是一个包含在数组中的位置,您将n EED映射它做1D,这是更简单:
int flatten(pos p)
{
return p.x*WIDTH + p.y;
}
这样你就可以将它们组合起来:
int fpos = flatten(wrap({30,20}));
和你做。
这是Python代码,但逻辑,使用简单的一维平面列表,应该清楚足够:
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
为了测试/打印:
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)
结果:
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|
我给你那种伪代码,事实上,你正在做它在MIPS应该不会影响到算法都没有。你可以很容易地计算模(用'div/divu'),你可以很容易地进行基本的数学运算。如果这确实是家庭作业,我想你应该尝试做出一些努力,我已经向你解释了你需要的一切。 – Jack 2012-02-20 02:53:10