在网格中寻找邻近单元的Pythonic和有效的方式 [英] Pythonic and efficient way of finding adjacent cells in grid

问题描述

我使用pyglet / openGL在Python中构建基于图块的应用程序，其中我需要找到给定单元格的所有相邻单元格。我正在笛卡尔网格的一个象限中工作。每个单元格都有一个x和y值，表示它在网格中的位置（x_coord和y_coord）。这些不是像素值，而是网格位置。我正在寻找一种有效的方式来获得邻近的细胞。在最大的情况下，有八个可能的相邻单元格，但由于网格的边界可能只有3个。对于简单但可能效率低下的方法，伪代码看起来像这样：

I am building a tile based app in Python using pyglet/openGL wherein I'll need to find the all of the adjacent cells for a given cell. I am working in one quadrant of a Cartesian grid. Each cell has an x and y value indicating it's position in the grid( x_coord and y_coord ). These are not pixel values, rather grid positions. I am looking for an efficient way to get the adjacent cells. At max there are eight possible adjacent cells, but because of the bounds of the grid there could be as few as 3. Pseudo-code for a simple yet probably inefficient approach looks something like this:

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密集型方法？或者，我应该使用这种方法吗？

This would probably work just fine, though it is likely that this code will need to run every frame and in a larger grid it may affect performance. Any ideas for a more streamlined and less cpu intensive approach? Or, should I just roll with this approach?

在此先感谢您。

Thanks in advance.

推荐答案

我不清楚在单元中是否有其他信息，而不仅仅是x和y坐标。无论如何，我认为需要改变数据结构才能使其更快。

It wasn't clear to me if there was other information in the cells than just the x and y coordinates. In any case, I think that a change of data structures is needed to make this faster.

我假定单元格中有额外的信息，并且使 grid.cells 作为字典，其中的键是坐标元组。如果单元格中只有坐标信息，也可以使用 grid.cells 作为一个集合。

I assumed that there is extra information in the cells and made grid.cells as a dictionary with the keys being tuples of the coordinates. A similar thing could be done withgrid.cells as a set if there is only the coordinate information in the 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次检查。

Depending on what you want to do with the data, you might not want to make result a dict, but hopefully you get the idea. This should be much faster than your code because your code is making 8 checks on every cell in grid.cells.

这篇关于在网格中寻找邻近单元的Pythonic和有效的方式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！