在网格中查找相邻单元格的 Pythonic 和有效方法
问题描述
我正在使用 pyglet/openGL 在 Python 中构建一个基于磁贴的应用程序，其中我需要找到给定单元格的所有相邻单元格.我在笛卡尔网格的一个象限中工作.每个单元格都有一个 x 和 y 值，表示它在网格中的位置( x_coord 和 y_coord ).这些不是像素值，而是网格位置.我正在寻找一种有效的方法来获取相邻的单元格.最多有 8 个可能的相邻单元格，但由于网格的边界，可能只有 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?
提前致谢.
解决方案
我不清楚单元格中是否除了 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)]
根据您想对数据执行的操作，您可能不希望将 result 设为 dict，但希望您能理解.这应该比您的代码快得多，因为您的代码对 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.
相关文章