我正在使用pyglet / openGL在Python中构建基于tile的应用程序，其中我需要找到给定单元格的所有相邻单元格。我在笛卡尔网格的一个象限中工作。每个单元格都有一个x和y值，表示它在网格中的位置（x_coord和y_coord）。这些不是像素值，而是网格位置。我正在寻找一种有效的方法来获得相邻的细胞。在max，有八个可能的相邻单元格，但由于网格的边界，可能只有3个。伪代码对于一个简单但可能效率低下的方法看起来像这样：
def get_adjacent_cells( self, cell ):
result = []
x_coord = cell.x_coord
y_coord = cell.y_coord
for c in grid.cells:
if c.x_coord == x_coord and c.y_coord == y_coord: # right
result.append( c )
if c.x_coord == x_coord - 1 and c.y_coord == y_coord + 1: # lower right
result.append( c )
if c.x_coord == x_coord - 1 and c.y_coord == y_coord: # below
result.append( c )
if c.x_coord == x_coord - 1 and c.y_coord == y_coord - 1: lower left
result.append( c )
if c.x_coord == x_coord and c.y_coord == y_coord - 1: right
result.append( c )
// -- similar conditional for remaining cells
这可能会很好，虽然这个代码可能需要每帧运行，而在更大的网格中它可能会影响性能。是否有更简化和更少cpu密集方法的想法？或者，我应该采用这种方法吗？
提前致谢。
我不清楚细胞中是否有其他信息，而不仅仅是x和y坐标。无论如何，我认为需要更改数据结构才能加快速度。
我假设单元格中有额外的信息，并将grid.cells作为字典，其中键是坐标的元组。如果单元格中只有坐标信息，则可以使用grid.cells作为集合进行类似的操作。
def get_adjacent_cells( self, x_coord, y_coord ):
result = {}
for x,y in [(x_coord+i,y_coord+j) for i in (-1,0,1) for j in (-1,0,1) if i != 0 or j != 0]:
if (x,y) in grid.cells:
result[(x,y)] = grid.cells[(x,y)]
根据您对数据的处理方式，您可能不希望将结果作为字典，但希望您能够理解。这应该比你的代码快得多，因为你的代码在grid.cells的每个单元格上进行8次检查。
你的代码将与你的网格一样慢，因为你只是在单元格上迭代得到其中的8个（你已经知道它们的坐标）。
如果您可以通过索引进行随机访问，我建议如下：
adjacency = [(i,j) for i in (-1,0,1) for j in (-1,0,1) if not (i == j == 0)] #the adjacency matrix
def get_adjacent_cells( self, cell ):
x_coord = cell.x_coord
y_coord = cell.y_coord
for dx, dy in adjacency:
if 0 <= (x_coord + dx) < max_x and 0 <= y_coord + dy < max_y: #boundaries check
#yielding is usually faster than constructing a list and returning it if you're just using it once
yield grid[x_coord + dx, y_coord + dy]
max_x和max_y应该是网格的大小，而grid.__getitem__应该接受带坐标的元组并返回该位置的单元格。
好吧，这对任何性能都无济于事，但你可以通过说避免代码重复
if abs(c.x_coord - x_coord) == 1 or abs(c.y_coord - y_coord) == 1:
result.append(c)
为了影响性能，您的网格单元应该知道他们的邻居是谁，通过c.neighbors这样的属性，或者通过隐式结构，如列表列表，这样您就可以通过坐标访问。
grid = [[a,b,c],
[d,e,f],
[g,h,i]]
然后，您可以使用列表索引检查邻居。
如果grid.cells作为一个集合实现，这可能是查找邻居的最有效方法（尽管第一个if语句中存在错误 - 您需要测试与x_coord + 1而不是x_coord的相等性）。
但是，将grid.cells实现为列表列表将允许您按行和列号引用单个单元格。它还允许您测量行和列的总数。 get_adjacent_cells然后可以通过首先检查哪些边缘与当前单元格边界，然后在所有其他方向上查找邻居并将它们附加到结果列表来工作。
在网格中，邻接意味着如果我没有错误或高，你只需要一个坐标的一个步骤到达另一个。
if abs(c.x_coord -_coord +c.y_coord-y_coord) == 1
print "they are adjacent!"
这适用于numpy数组
def get_adjacent_cells(arr, selected_idxs):
"""
>>> arr = np.ones((3,))
>>> get_adjacent_cells(arr, {(1,)})
{(0,), (1,), (2,)}
>>> arr = np.ones((3,2))
>>> get_adjacent_cells(arr, {(1,1)})
{(0, 1), (1, 0), (1, 1), (2, 1)}
>>> arr = np.ones((3,2,3))
>>> {(0, 1, 0), (1, 0, 0), (1, 1, 0), (1, 1, 1), (2, 1, 0)}
>>> arr = np.ones((3,2,3))
>>> get_adjacent_cells(arr, {(1,1,0), (0,1,0)})
{(0, 0, 0), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 1, 0), (1, 1, 1), (2, 1, 0)}
"""
w = np.asarray(list(selected_idxs))
new_idxs = []
for col in range(w.shape[1]):
w_ = w.copy()
w_[:,col] += 1
new_idxs.extend(list(w_))
w_ = w.copy()
w_[:,col] -= 1
new_idxs.extend(list(w_))
new_idxs = np.array(new_idxs)
# remove out of bounds coordinates
for col, dim_size in enumerate(arr.shape):
new_idxs = new_idxs[(new_idxs[:, col] >= 0) & (new_idxs[:, col] < dim_size)]
return selected_idxs.union(map(tuple, new_idxs))