在 2D 网格上找到一个节点 8 个邻居
Find a nodes 8 neighbors on a 2D grid
我需要找到二维数组中任何节点的基数和对角线邻居。采取下面的数组。我正在从数组中的 [1, 1] 中的 1 开始搜索。它应该 return 周围的 0。我可以找到邻居,如下面的一些代码所示,但它们太慢了。
[[0, 0, 0]
[0, 1, 0]
[0, 0, 0]]
我可以像这样暴力破解return所有8个周围节点的坐标。
def ReturnNeighbors(x, y):
numpy.array([(x-1, y), (x, y-1), (x+1, y), (x, y+1),
(x-1, y-1), (x+1, y+1), (x-1, y+1), (x+1, y-1)])
def ReturnNeighbors_4(x, y):
for i in xrange(x - 1, x + 2):
for j in xrange(y - 1, y + 2):
if (i, j) != (x, y):
yield (i, j)
或者通过计算到所有节点的距离并 returning 那些距离小于 2 的节点,但是这些和我发现的其他解决方案都很慢。我学习 numpy 的全部原因是为了速度。我想我需要使用 scipy convolve2d 或 cKDtree,但它们对我来说太复杂了。
我在切换到 numpy 之前处理这个问题的方式是我的数组充满了实际的节点对象作为值。每个对象将其 x 和 y 坐标存储在网格及其一组邻居中。像这样。我不能再使用这种方法,因为填充一个充满节点的巨大数组需要很长时间。即使在 100x100 的小地图中也有 10000 个节点对象!我计划以后不仅要有更大的地图,还要有多个地图在任何给定时间都处于活动状态。由于节点印记,我实际上 运行 内存不足,试图创建更大的地图。它适用于小地牢,但不适用于模拟多个地图的世界。
ExampleNode(object):
def __init__(self, x, y):
self.x = x
self.y = y
self.neighbors = set()
# The neighbors are found and added to the above set later.
node = Example(0, 0)
for neighbor in node.neighbors:
do thing with each neighbor
出于各种原因,我需要一个节点邻居。使用元胞自动机平滑地图、在战斗中在附近溅血、使用广度优先搜索进行寻路等等。这是我正在创建的流氓类游戏。蛮力方法适用于小型 60x60 地牢,但现在我正在扩大范围并生成世界地图。它只有 200x200,而且速度慢得令人恼火。
让我们假设输入数组名为 A
,它包含所有整数,我们只处理其中 1s
的元素,并尝试获取它们的邻居。这是一种方法 -
# Get offsets for row and column
R_offset,C_offset = np.meshgrid(np.arange(-1,2),np.arange(-1,2))
# Get row and column indices for places where elements are 1s
R_match,C_match = np.nonzero(A==1)
# Store number of matches as it would be frequently used
N = R_match.size
# Get offsetted row, col indices for all matches
R_idx = (R_match[:,None,None] + R_offset).reshape(N,-1)
C_idx = (C_match[:,None,None] + C_offset).reshape(N,-1)
# Based on boundary conditions set invalid ones to zeros
valid_mask = (R_idx>=0) & (C_idx>=0) & (R_idx<A.shape[0]) & (C_idx<A.shape[1])
valid_mask[:,4] = 0 # Set the pivot(self/center) ones to invalid
# Using valid mask, "cut off" elements from each group of 9 elems
cut_idx = valid_mask.sum(1).cumsum()
# Finally form groups
grps_R = np.split(R_idx[valid_mask],cut_idx)[:-1]
grps_C = np.split(C_idx[valid_mask],cut_idx)[:-1]
示例 运行 以及关于如何解释和使用输出的解释 -
In [256]: A
Out[256]:
array([[1, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 1, 0, 0],
[0, 0, 0, 0, 1]])
In [257]: grps_R
Out[257]: [array([1, 0, 1]), array([1, 2, 3, 1, 3, 1, 2, 3]), array([2, 3, 2])]
In [258]: grps_C
Out[258]: [array([0, 1, 1]), array([1, 1, 1, 2, 2, 3, 3, 3]), array([3, 3, 4])]
因此,我们根据 A
中的三个 1s
得到三个组。
第一个在左上角-
In [259]: np.column_stack((R_match[0],C_match[0])) # First point
Out[259]: array([[0, 0]])
In [260]: np.column_stack((grps_R[0],grps_C[0])) # Its three neighbors
Out[260]:
array([[1, 0],
[0, 1],
[1, 1]])
第二个在(2,2)
-
In [263]: np.column_stack((R_match[1],C_match[1])) # Second point
Out[263]: array([[2, 2]])
In [264]: np.column_stack((grps_R[1],grps_C[1])) # Its eight neighbors
Out[264]:
array([[1, 1],
[2, 1],
[3, 1],
[1, 2],
[3, 2],
[1, 3],
[2, 3],
[3, 3]])
第三个终于在(4,5)
-
In [265]: np.column_stack((R_match[2],C_match[2])) # Third point
Out[265]: array([[3, 4]])
In [266]: np.column_stack((grps_R[2],grps_C[2])) # Its three neighbors
Out[266]:
array([[2, 3],
[3, 3],
[2, 4]])
我需要找到二维数组中任何节点的基数和对角线邻居。采取下面的数组。我正在从数组中的 [1, 1] 中的 1 开始搜索。它应该 return 周围的 0。我可以找到邻居,如下面的一些代码所示,但它们太慢了。
[[0, 0, 0]
[0, 1, 0]
[0, 0, 0]]
我可以像这样暴力破解return所有8个周围节点的坐标。
def ReturnNeighbors(x, y):
numpy.array([(x-1, y), (x, y-1), (x+1, y), (x, y+1),
(x-1, y-1), (x+1, y+1), (x-1, y+1), (x+1, y-1)])
def ReturnNeighbors_4(x, y):
for i in xrange(x - 1, x + 2):
for j in xrange(y - 1, y + 2):
if (i, j) != (x, y):
yield (i, j)
或者通过计算到所有节点的距离并 returning 那些距离小于 2 的节点,但是这些和我发现的其他解决方案都很慢。我学习 numpy 的全部原因是为了速度。我想我需要使用 scipy convolve2d 或 cKDtree,但它们对我来说太复杂了。
我在切换到 numpy 之前处理这个问题的方式是我的数组充满了实际的节点对象作为值。每个对象将其 x 和 y 坐标存储在网格及其一组邻居中。像这样。我不能再使用这种方法,因为填充一个充满节点的巨大数组需要很长时间。即使在 100x100 的小地图中也有 10000 个节点对象!我计划以后不仅要有更大的地图,还要有多个地图在任何给定时间都处于活动状态。由于节点印记,我实际上 运行 内存不足,试图创建更大的地图。它适用于小地牢,但不适用于模拟多个地图的世界。
ExampleNode(object):
def __init__(self, x, y):
self.x = x
self.y = y
self.neighbors = set()
# The neighbors are found and added to the above set later.
node = Example(0, 0)
for neighbor in node.neighbors:
do thing with each neighbor
出于各种原因,我需要一个节点邻居。使用元胞自动机平滑地图、在战斗中在附近溅血、使用广度优先搜索进行寻路等等。这是我正在创建的流氓类游戏。蛮力方法适用于小型 60x60 地牢,但现在我正在扩大范围并生成世界地图。它只有 200x200,而且速度慢得令人恼火。
让我们假设输入数组名为 A
,它包含所有整数,我们只处理其中 1s
的元素,并尝试获取它们的邻居。这是一种方法 -
# Get offsets for row and column
R_offset,C_offset = np.meshgrid(np.arange(-1,2),np.arange(-1,2))
# Get row and column indices for places where elements are 1s
R_match,C_match = np.nonzero(A==1)
# Store number of matches as it would be frequently used
N = R_match.size
# Get offsetted row, col indices for all matches
R_idx = (R_match[:,None,None] + R_offset).reshape(N,-1)
C_idx = (C_match[:,None,None] + C_offset).reshape(N,-1)
# Based on boundary conditions set invalid ones to zeros
valid_mask = (R_idx>=0) & (C_idx>=0) & (R_idx<A.shape[0]) & (C_idx<A.shape[1])
valid_mask[:,4] = 0 # Set the pivot(self/center) ones to invalid
# Using valid mask, "cut off" elements from each group of 9 elems
cut_idx = valid_mask.sum(1).cumsum()
# Finally form groups
grps_R = np.split(R_idx[valid_mask],cut_idx)[:-1]
grps_C = np.split(C_idx[valid_mask],cut_idx)[:-1]
示例 运行 以及关于如何解释和使用输出的解释 -
In [256]: A
Out[256]:
array([[1, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 1, 0, 0],
[0, 0, 0, 0, 1]])
In [257]: grps_R
Out[257]: [array([1, 0, 1]), array([1, 2, 3, 1, 3, 1, 2, 3]), array([2, 3, 2])]
In [258]: grps_C
Out[258]: [array([0, 1, 1]), array([1, 1, 1, 2, 2, 3, 3, 3]), array([3, 3, 4])]
因此,我们根据 A
中的三个 1s
得到三个组。
第一个在左上角-
In [259]: np.column_stack((R_match[0],C_match[0])) # First point
Out[259]: array([[0, 0]])
In [260]: np.column_stack((grps_R[0],grps_C[0])) # Its three neighbors
Out[260]:
array([[1, 0],
[0, 1],
[1, 1]])
第二个在(2,2)
-
In [263]: np.column_stack((R_match[1],C_match[1])) # Second point
Out[263]: array([[2, 2]])
In [264]: np.column_stack((grps_R[1],grps_C[1])) # Its eight neighbors
Out[264]:
array([[1, 1],
[2, 1],
[3, 1],
[1, 2],
[3, 2],
[1, 3],
[2, 3],
[3, 3]])
第三个终于在(4,5)
-
In [265]: np.column_stack((R_match[2],C_match[2])) # Third point
Out[265]: array([[3, 4]])
In [266]: np.column_stack((grps_R[2],grps_C[2])) # Its three neighbors
Out[266]:
array([[2, 3],
[3, 3],
[2, 4]])