12

特定のセルに隣接するすべてのセルを見つける必要がある pyglet/openGL を使用して、Python でタイル ベースのアプリを構築しています。私はデカルト グリッドの 1 つの象限で作業しています。各セルには、グリッド内の位置を示す 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

これはおそらく問題なく動作しますが、このコードはすべてのフレームで実行する必要があり、より大きなグリッドではパフォーマンスに影響を与える可能性があります。より合理化され、CPU をあまり使用しないアプローチのアイデアはありますか? または、このアプローチでロールする必要がありますか?

前もって感謝します。

4

6 に答える 6

11

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。

于 2010-03-03T17:58:03.757 に答える
9

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__想定されており、 は座標を持つタプルを受け入れ、その位置のセルを返すと想定されています。

于 2010-03-03T17:27:44.443 に答える
2

まあ、これはパフォーマンスには何の役にも立ちませんが、次のように言うことでコードの重複を避けることができます

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

次に、リスト インデックスを使用して隣接性をチェックできます。

于 2010-03-03T17:23:54.017 に答える
1

grid.cells がセットとして実装されている場合、おそらくこれが最も効率的な隣接セルの検索方法です (ただし、最初の if ステートメントには誤りがあります。x_coord ではなく x_coord + 1 と等しいかどうかをテストする必要があります)。

ただし、grid.cells をリストのリストとして実装すると、個々のセルを行番号と列番号で参照できるようになります。また、行と列の合計数を測定することもできます。get_adjacent_cells は、最初に現在のセルに隣接するエッジを確認し、次に他のすべての方向の隣接セルを検索して結果リストに追加することで機能します。

于 2010-03-03T17:24:24.810 に答える