Питонический и эффективный способ поиска соседних ячеек в сетке

Question

Я строю приложение на основе плиток в Python, используя pyglet / openGL, в котором мне нужно найти все соседние ячейки для данной ячейки.Я работаю в одном квадранте декартовой сетки.Каждая ячейка имеет значения x и y, указывающие ее положение в сетке (x_coord и y_coord).Это не значения пикселей, а позиции сетки.Я ищу эффективный способ получить соседние клетки.В максимуме есть восемь возможных соседних ячеек, но из-за границ сетки их может быть всего 3. Псевдокод для простого, но, вероятно, неэффективного подхода выглядит примерно так:вероятно, будет работать нормально, хотя вполне вероятно, что этот код потребуется для запуска каждого кадра, а в более крупной сетке это может повлиять на производительность.Есть идеи для более обтекаемого и менее интенсивного подхода?Или мне просто катиться с таким подходом?

Заранее спасибо.

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.

Answer 2

Ваш код будет настолько медленным, насколько велика ваша сетка, потому что вы перебираете ячейки, чтобы получить 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 3

Что ж, это никак не повлияет на производительность, но вы можете избежать дублирования кода, сказав

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

Чтобы повлиять на производительность, ваши ячейки сетки должны знать, кто их соседи, либо через атрибут типа c.neighbors, либо через неявную структуру, например список списков, чтобы вы могли получить доступ по координатам.

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

Затем вы можете проверить соседство, используя индексы списка.

Answer 4

Это, вероятно, самый эффективный способ поиска соседей, если grid.cells реализован в виде набора (хотя в первом операторе if есть ошибка - вам нужно проверить равенство x_coord + 1, а не x_coord) .

Однако реализация grid.cells в виде списка списков позволит вам ссылаться на отдельные ячейки по номеру строки и столбца. Это также позволит вам измерить общее количество строк и столбцов. Затем get_adjacent_cells может работать, сначала проверяя, какие ребра граничат с текущей ячейкой, а затем ищите соседей во всех других направлениях и добавляя их в список результатов.

Answer 5

Это работает с массивами 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))

Answer 6

В сетке смежность означает, что вам нужен только один шаг любой координаты, чтобы достичь другой, если я не ошибаюсь или высокий.

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