Pythonic и эффективный способ найти смежные ячейки в сетке
Я создаю основанное на мозаике приложение в Python с помощью pyglet/openGL, где я должен буду найти все смежные ячейки для данной ячейки. Я работаю в одном квадранте Декартовой сетки. Каждая ячейка имеет значение X и Y, указывающее, что это - положение в сетке (x_coord и y_coord). Это не пиксельные значения, скорее положения сетки. Я ищу эффективный способ получить смежные ячейки. В макс. существует восемь возможных смежных ячеек, но из-за границ сетки могло быть только 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
Это, вероятно, работало бы просто великолепно, хотя вероятно, что этот код должен будет выполнить каждый кадр, и в большей сетке это может влиять на производительность. Какие-либо идеи для более оптимизированного и меньшего количества CPU интенсивный подход? Или, я должен просто прокрутиться с этим подходом?
Заранее спасибо.
4 ответа
Мне было непонятно, была ли в ячейках другая информация, кроме координат 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 .
Ваш код будет настолько медленным, насколько велика ваша сетка, потому что вы итерируете по ячейкам, чтобы получить 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__ должен принимать кортеж с координатами и возвращать ячейку в этой позиции.
Что ж, это не поможет производительности, но вы можете избежать дублирования кода, сказав
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]]
Затем вы можете проверить соседство, используя индексы списка.
Это, вероятно, наиболее эффективный способ поиска соседей, если grid.cells реализован как набор (хотя есть ошибка в первом операторе if - вам нужно проверить на равенство x_coord + 1, а не x_coord).
Однако реализация grid.cells как списка списков позволит вам ссылаться на отдельные ячейки по номеру строки и столбца. Это также позволит вам измерить общее количество строк и столбцов. Затем get_adjacent_cells может работать, сначала проверяя, какие края граничат с текущей ячейкой, а затем просматривая соседей во всех других направлениях и добавляя их в список результатов.