寻找网格中相邻单元格的Pythonic高效方法

Question

我正在用Python和pyglet/openGL开发一个基于瓷砖的应用程序，我需要找到一个给定单元格的所有相邻单元格。我在一个笛卡尔坐标系的象限中工作。每个单元格都有一个x和y值，表示它在网格中的位置（x_coord和y_coord）。这些值不是像素值，而是网格位置。我想找到一种高效的方法来获取相邻的单元格。最多有八个可能的相邻单元格，但由于网格的边界，可能只有三个相邻单元格。以下是一个简单但可能效率不高的伪代码示例：

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的方法？或者，我应该继续使用这个方法吗？

提前谢谢你。

Answer 1

好吧，这样做虽然对性能没有帮助，但你可以通过以下方式避免代码重复：

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

然后你就可以使用列表的索引来检查邻居关系。

Answer 2

你的代码速度会跟你的网格大小成正比，因为你在遍历所有的单元格，只是为了获取其中的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__ 应该接受一个包含坐标的元组，并返回那个位置的单元格。

Answer 3

我不太确定这些单元格里是否只有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次。