Pythonic和有效的方法在网格中找到相邻的单元格

Question

我正在使用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密集方法的想法？或者,我应该采用这种方法吗？

提前致谢.

Answer 1

你的代码将与你的网格一样慢,因为你只是在单元格上迭代得到其中的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 2

我不清楚细胞中是否有其他信息,而不仅仅是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.