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

Я создаю приложение на основе плитки на Python, используя pyglet/openGL, где мне нужно будет найти все смежные ячейки для данной ячейки. Я работаю в одном квадранте декартовой сетки. Каждая ячейка имеет значение 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

Это, вероятно, будет работать нормально, хотя вполне вероятно, что этот код должен будет запускать каждый кадр, а в большей сетке это может повлиять на производительность. Любые идеи для более упорядоченного и менее интенсивного подхода? Или, должен ли я просто рулон с этим подходом?

Спасибо заранее.

Ответ 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)]

В зависимости от того, что вы хотите делать с данными, вы можете не захотеть сделать результат dict, но, надеюсь, вы получите эту идею. Это должно быть намного быстрее, чем ваш код, потому что ваш код делает 8 проверок на каждую ячейку в grid.cells.

Ответ 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__ должен принимать кортеж с координатами и возвращать ячейку в этой позиции.

Ответ 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]]

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

Ответ 4

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

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

Ответ 5

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

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