그리드에서 인접한 셀을 찾는 파이썬적이고 효율적인 방법

Question

저는 pyglet/openGL을 사용하여 파이썬에서 타일 기반의 응용 프로그램을 구축하고 있습니다. 여기에서 주어진 셀에 대해 인접한 셀을 모두 찾아야합니다. 나는 데카르트 격자의 한 사분면에서 일하고있다. 각 셀에는 그리드의 위치 (x_coord 및 y_coord)를 나타내는 x 및 y 값이 있습니다. 이것은 픽셀 값이 아니라 그리드 위치입니다. 나는 인접한 세포를 얻는 효율적인 방법을 찾고있다. 이것은 아마 것

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 

: 최대에, 그러나 때문에 그리드의 경계의 8 개의 가능한 인접 셀은 단순하지만 아마 비효율적 인 접근과 같은 몇 3. 같은 의사 코드가있을 수있다는 다음과 같이 보입니다 이 코드는 모든 프레임을 실행할 필요가 있고 큰 그리드에서는 성능에 영향을 줄 수 있지만 그래도 잘 작동합니다. 더욱 간소화되고 CPU 사용량이 적은 접근 방식에 대한 아이디어가 있습니까? 아니면 그냥이 방법을 사용해야합니까?

미리 감사드립니다. , c.neighbors 같은 속성을 통해서,

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)] 

당신이 데이터에 대해 수행 할 작업에 따라, 당신은 DICT 결과 만들고 싶어하지 않을 수 있습니다, 그러나 희망 당신은 아이디어를 얻을. grid.cells에있는 모든 셀에서 코드를 8 번 확인하므로 코드보다 훨씬 빠릅니다.

Answer 2

음,이 모든 성능을 도움이되지 않습니다,하지만 당신은

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

, 당신의 그리드 셀이 이웃이 누구인지 알아야 성능에 영향을 말함으로써 코드 중복을 피할 수 또는 목록 목록과 같은 암시 적 구조를 통해 좌표로 액세스 할 수 있습니다.

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

그런 다음 목록 인덱스를 사용하여 이웃 사랑을 확인할 수 있습니다.

Answer 3

grid.cells가 집합으로 구현 된 경우 가장 효율적으로 이웃을 찾는 방법입니다 (첫 번째 if 문에 실수가 있지만 x_coord가 아닌 x_coord + 1과 같은지 테스트해야 함).).

그러나 grid.cells를 목록 목록으로 구현하면 행과 열 번호로 개별 셀을 참조 할 수 있습니다. 또한 행과 열의 총 수를 측정 할 수 있습니다. 그런 다음 get_adjacent_cells는 현재 가장자리와 현재 셀의 경계를 확인한 다음 다른 모든 방향의 이웃을 찾아 결과 목록에 추가하여 작동합니다.

Answer 4

귀하의 코드는 그리드가 너무 느릴 것입니다. 셀 위로 반복하여 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 5

격자에서 인접성이란 내가 실수로 또는 높게 표시하지 않으면 어느 한 좌표 만 다른 좌표계에 도달해야한다는 것을 의미합니다.

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