1d配列として表現されたときの2次元配列の近傍を見つける

Question

2次元配列を1次元配列に変換しました。 1d表現では、ラップアラウンドを考慮して、どのようにしてセルの8つの近傍を見つけることができますか？

これは私が2dのゲームボードを1dのメモリのチャンクとしてメモリに格納していることです。私は、ゲームボード内の8つの隣接セルすべてのメモリ位置を見つけることができる必要があります。私が抱えている問題は、（特にセルが2次元アレイの角にある場合は）エッジ上のボードラップアラウンドを考慮に入れることです。例えば

セルは右上隅にある場合は、一番上の隣人は、私がこれを計算していたとき、私はボードのサイズを知っているなど

、右下隅にあります。

EDIT：私がMIPSアセンブリでこれをやっていることを言及する適切かもしれません...

Answer 1

あなただけの配列内に含まれる位置に任意の位置をマップすることができる機能を必要としています。

次の2つの手順で問題を分解する必要があります。

ラッピングは、モジュロ演算子で簡単に

struct pos { int x,y }; 

pos wrap(pos p) 
{ 
    pos p2 = p; 

    if (p.x >= WIDTH) 
    p.x %= WIDTH; 
    else if (p.x < 0) 
    p.x += WIDTH; 

    if (p.y >= HEIGHT) 
    ... same thing 
} 

ような何かを行うことができます〜1dの2D COORDSをマッピング

を包む

• 次に、配列の中に確かに含まれるポジションがあります。それは1Dを行うマッピングするEEDは、それがさらに簡単です：

  int flatten(pos p) 
  { 
      return p.x*WIDTH + p.y; 
  } 
  

  ので、あなたがそれらを組み合わせることができます。

  int fpos = flatten(wrap({30,20})); 
  

  と設定が完了しているが。

Answer 2

これは、Pythonのコードですが、簡単な1Dフラットリストを用いた論理は、十分に明確にする必要があります。

def neighbors(i, w, h, mode=8): 
    """Return a list of neighbors. 

    Works as like a 2d graph of 'w' width and 'h' height with boundaries. 

    Args: 
     i(int): 1d index 
     w(int): width of the graph. 
     h(int): height of the graph. 
     mode(int): 8 for eight directions (includes diagonals); else for 
      4 directions (top, down, left, right). 

    Returns: 
     list 
    """ 
    size = w * h 
    neighbors = [] 
    if i - w >= 0: 
     neighbors.append(i - w) # north 
    if i % w != 0: 
     neighbors.append(i - 1) # west 

    if (i + 1) % w != 0: 
     neighbors.append(i + 1) # east 

    if i + w < size: 
     neighbors.append(i + w) # south 

    if mode == 8: 
     if ((i - w - 1) >= 0) and (i % w != 0): 
      neighbors.append(i - w - 1) # northwest 

     if ((i - w + 1) >= 0) and ((i + 1) % w != 0): 
      neighbors.append(i - w + 1) # northeast 

     if ((i + w - 1) < size) and (i % w != 0): 
      neighbors.append(i + w - 1) # southwest 

     if ((i + w + 1) < size) and ((i + 1) % w != 0): 
      neighbors.append(i + w + 1) # southeast 
    return neighbors 

それを印刷/テストするには：

if __name__ == '__main__': 
    W = 3 # width 
    H = 3 # height 

    def show(start, neighbors): 
     """Simple display of an 2d table. 

     Args: 
      start(int): initial position (shown as 'S') 
      neighbors(list): list of positions (draw as their values) 
     """ 
     for y in range(H): 
      print("|", end="") 
      for x in range(W): 
       i = y * W + x 
       if i == start: 
        c = " S|" 
       elif i in neighbors: 
        c = "%3d|" % i 
       else: 
        c = " .|" 

       print(c, end="") 
      print() 

    for i in range(W * H): 
     print() 
     n = neighbors(i, W, H) 
     print("neighbors(%d) of '%d':" % (len(n), i), n) 
     show(i, n) 

結果：

neighbors(3) of '0': [1, 3, 4] 
| S| 1| .| 
| 3| 4| .| 
| .| .| .| 

neighbors(5) of '1': [0, 2, 4, 3, 5] 
| 0| S| 2| 
| 3| 4| 5| 
| .| .| .| 

neighbors(3) of '2': [1, 5, 4] 
| .| 1| S| 
| .| 4| 5| 
| .| .| .| 

neighbors(5) of '3': [0, 4, 6, 1, 7] 
| 0| 1| .| 
| S| 4| .| 
| 6| 7| .| 

neighbors(8) of '4': [1, 3, 5, 7, 0, 2, 6, 8] 
| 0| 1| 2| 
| 3| S| 5| 
| 6| 7| 8| 

neighbors(5) of '5': [2, 4, 8, 1, 7] 
| .| 1| 2| 
| .| 4| S| 
| .| 7| 8| 

neighbors(3) of '6': [3, 7, 4] 
| .| .| .| 
| 3| 4| .| 
| S| 7| .| 

neighbors(5) of '7': [4, 6, 8, 3, 5] 
| .| .| .| 
| 3| 4| 5| 
| 6| S| 8| 

neighbors(3) of '8': [5, 7, 4] 
| .| .| .| 
| .| 4| 5| 
| .| 7| S|