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

Pythonic and efficient way of finding adjacent cells in grid

提问by JeremyFromEarth

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:

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

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?

这可能会正常工作，尽管此代码可能需要运行每一帧，并且在更大的网格中它可能会影响性能。关于更精简和更少 CPU 密集型方法的任何想法？或者，我应该采用这种方法吗？

Thanks in advance.

提前致谢。

采纳答案by Justin Peel

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.

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

I assumed that there is extra information in the cells and made grid.cellsas a dictionary with the keys being tuples of the coordinates. A similar thing could be done withgrid.cellsas a set if there is only the coordinate information in the cells.

我假设单元格中有额外的信息，并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)]

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.

根据您想对数据做什么，您可能不希望将结果设为 dict，但希望您能理解。这应该比您的代码快得多，因为您的代码对grid.cells.

回答by fortran

Your code is going to be as slow as large is your grid, because you're iterating over the cells just to get 8 of them (of which you already know their coordinates).

您的代码将与您的网格一样慢，因为您迭代单元格只是为了获得其中的 8 个（您已经知道它们的坐标）。

If you can do random access by their indices, I suggest something like the following:

如果您可以通过他们的索引进行随机访问，我建议如下：

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_xand max_yare supposed to be the size of the grid, and the grid.__getitem__is supposed to accept a tuple with the coordinates and return the cell in that position.

max_xandmax_y应该是网格的大小，并且grid.__getitem__应该接受一个带有坐标的元组并返回该位置的单元格。

回答by jcdyer

Well, this won't help performance any, but you can avoid code duplication by saying

好吧，这对性能没有任何帮助，但是您可以通过说来避免代码重复

if abs(c.x_coord - x_coord) == 1 or abs(c.y_coord - y_coord) == 1:
    result.append(c)

To affect performance, your grid cells should know who their neighbors are, either through an attribute like c.neighbors, or through an implicit structure, like a list of lists, so you can access by coordinate.

为了影响性能，你的网格单元应该知道他们的邻居是谁，要么通过像 的属性c.neighbors，要么通过隐式结构，比如列表，这样你就可以通过坐标访问。

grid = [[a,b,c],
        [d,e,f],
        [g,h,i]]

Then you can check for neighborliness using the list indices.

然后您可以使用列表索引检查邻居。

回答by Tommy Herbert

This is probably the most efficient way to look for neighbours if grid.cells is implemented as a set (though there's a mistake in the first if-statement - you need to test for equality to x_coord + 1 rather than to x_coord).

如果将 grid.cells 实现为一个集合，这可能是寻找邻居的最有效方法（尽管第一个 if 语句中存在错误 - 您需要测试是否与 x_coord + 1 而不是 x_coord 相等）。

However, implementing grid.cells as a list of lists would allow you to refer to individual cells by row and column number. It would also allow you to measure the total number of rows and columns. get_adjacent_cells could then work by first checking which edges border the current cell, and then looking up the neighbours in all other directions and appending them to the result list.

但是，将 grid.cells 实现为列表列表将允许您按行号和列号引用单个单元格。它还允许您测量行和列的总数。然后 get_adjacent_cells 可以通过首先检查哪些边与当前单元格相邻，然后在所有其他方向查找邻居并将它们附加到结果列表中来工作。

回答by user3783689

In a grid, adjacency means you need only one step of either coordinate to reach the other if I'm not mistakenly or high.

在网格中，邻接意味着如果我没有错误或高，你只需要一个坐标的一步就可以到达另一个坐标。

 if abs(c.x_coord -_coord +c.y_coord-y_coord) == 1
     print "they are adjacent!"

回答by egafni

This works with numpy arrays

这适用于 numpy 数组

def get_adjacent_cells(arr, selected_idxs):
    """
    >>> arr = np.ones((3,))
    >>> get_adjacent_cells(arr, {(1,)})
    {(0,), (1,), (2,)}
    >>> arr = np.ones((3,2))
    >>> get_adjacent_cells(arr, {(1,1)})
    {(0, 1), (1, 0), (1, 1), (2, 1)}
    >>> arr = np.ones((3,2,3))
    >>> {(0, 1, 0), (1, 0, 0), (1, 1, 0), (1, 1, 1), (2, 1, 0)}
    >>> arr = np.ones((3,2,3))
    >>> get_adjacent_cells(arr, {(1,1,0), (0,1,0)})
    {(0, 0, 0), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 1, 0), (1, 1, 1), (2, 1, 0)}
    """
    w = np.asarray(list(selected_idxs))
    new_idxs = []
    for col in range(w.shape[1]):
        w_ = w.copy()
        w_[:,col] += 1
        new_idxs.extend(list(w_))
        w_ = w.copy()
        w_[:,col] -= 1
        new_idxs.extend(list(w_))

    new_idxs = np.array(new_idxs)

    # remove out of bounds coordinates
    for col, dim_size in enumerate(arr.shape):
        new_idxs = new_idxs[(new_idxs[:, col] >= 0) & (new_idxs[:, col] < dim_size)]

    return selected_idxs.union(map(tuple, new_idxs))