在网格中查找相邻单元格的Python高效方法

Question

我正在使用pyglet /
openGL在Python中构建基于图块的应用，其中我需要查找给定单元的所有相邻单元。我在笛卡尔网格的一个象限中工作。每个像元都有一个x和y值，指示其在网格中的位置（x_coord和y_coord）。这些不是像素值，而是网格位置。我正在寻找一种获取相邻细胞的有效方法。最多有八个可能的相邻像元，但由于网格的边界，可能只有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占用更少？还是我应该采用这种方法？

提前致谢。

Answer 1

对我来说，尚不清楚单元格中是否仅存在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)]

根据您要处理的数据的不同，您可能不希望将结果做成字典，但希望您能理解。这应该比您的代码快得多，因为您的代码会对中的每个单元格进行8次检查grid.cells。