编程逻辑：如何检查网格中的邻居？

Question

我有很多的麻烦试图想在“网格”为基础的编程类项目检查邻居的逻辑方式。

我有是一种思维方式，有效地检查其是否在两侧，使我没有得到一个索引越界错误的主要问题。

编辑： 我忘了提及，我使用的2维阵列。

Answer 1

什么是它的一个二维数组？也许有些物体具有诸如“被占领”和“空”之类的状态？在这种情况下，引入诸如“边缘”和“角落”之类的新状态，并创建在每个方向上更大的2-D阵列1单元。那么你的邻居检查器就可以使用简单的+/-逻辑，然后处理这组邻居可以选择忽略任何边缘。

Answer 2

这里得到一个邻居位置，避免对双方令人担忧的一个简单的方法：

int leftX = (x - 1 + width) % width; 
int rightX = (x + 1) % width; 
int aboveY = (y - 1 + height) % height; 
int belowY = (y + 1) % height; 

它可能没有这样做的最有效的方式，但它使每个计算到一个单一的，简单的表达。假设你想要环绕，当然。如果不这样做，你会有有条件做的事情：

if (x > 0) 
{ 
    // Use x - 1 
} 
if (x < width - 1) 
{ 
    // Use x + 1 
} 

Answer 3

如前所述，[X，Y]的左邻为[X，Y-1]，右的邻居[x，y + 1]等等。但是，你也应该检查y> = 1，否则你会超出界限。同样，y必须小于数组的大小。你可以用if语句来做到这一点，或者（不推荐）你可以处理ArrayIndexOutOfBoundsException。

Answer 4

基本上你要访问一个小区的邻居，同时确保你是不是出了格的。你可以尝试一个简单的算法：

假设中心单元（其中你是）是(x,y)，并且你还想检查对角线。
你的电网是[0，W [X上，和[0，H [上Y（基本上W x H，从（0,0）开始）

for (i=-1 ; i<2 ; i++)  
    for (j=-1 ; j<2 ; j++) 
     if (i !=0 && j != 0) 
    { 
    rx = x + i; 
    ry = y + j; 

    if (rx >= 0 && ry >= 0 && rx < W && ry < H) 
    { 
     // I'm in 
    } 
    else 
    { 
     // I'm out 
    } 

    } 

这可以在被优化（I，J） ，例如从0开始i如果x为0

如果你不想对角线，你只需要检查(x-1,y)(x+1,y)(x,y-1)和(x,y+1)，

for (i=-1 ; i<2 ; i+=2) 
    { 
    // check (x+i, y) 
    // check (x, y+i) 
    } 

Answer 5

有常（如果不总是）在牺牲速度与记忆的关系;前段时间，我不得不在Java中实现一个Sudoku求解器，并且为每个单元格分配一个单元组列表会更快。因此，我不必每次都检查边界，而只需遍历每个组，然后遍历每个组中的每个单元。检查一次创建组。

喜欢的东西：

class Neighbors { 
    ArrayList<Point> pList = new ArrayList<Point>(); 
} 

...

int[][] grid = new int[10][10]; 
Neighbors[][] n = new Neighbors[10][10]; 

for (int x=0; x<10; x++) { 
    for (int y=0; y<10; y++) { 
     grid[x][y] = (y*10)+x; // 0..99 
     n[x][y] = new Neighbors(); 
     for (int nx=x-1; nx<=x+1; nx++) { 
     for (int ny=y-1; ny<=y+1; ny++) { 
      if (!(x==nx && y==ny) && nx>=0 && ny>=0 && nx<10 && ny<10) { 
       n[x][y].pList.add(new Point(nx,ny)); // add valid neighbor 
      } 
     } 
     } 
    } 
} 

那么，对于任何给定的点：X，Y

for (Point p : n[x][y].pList) { 
    // grid[p.x][p.y] is a neighbor of grid[x][y] 
} 

嗯，我的解决办法是有点更复杂，但原理是一样的。如果您的网格是对象的二维数组，则邻居实际上可以是grid[nx][ny]上的对象，而不是直接访问对象的点。

您最终将需要检查x>=0，y>=0，x<SIZE_W和y<SIZE_H，但是这种解决方案所做的检查只onece，所以对于每个网格单元经常查询的邻居时，在我看来是相当有效的。如果您需要经常调整网格大小，那么需要对此解决方案进行调整。

另一种方法是，以垫的阵列与ignored标志值中的每个方向（如空，-1，等），并简单地做一个正常检查忽略这样的细胞：

int pad_size = 1; // how many neighbors around x,y 
int size_w = 10+(pad_size*2); 
int size_h = 10+(pad_size*2); 
int[][] grid = new int[size_w][size_h]; 

for (int x=0; x<size_w; x++) { 
    for (int y=0; y<size_h; y++) { 
    if (x<pad_size || x>=size_w-pad_size || y<pad_size || y>=size_h-pad_size) { 
     grid[x][y] = -1; // ignore 
    } else { 
     grid[x][y] = ((y-pad_size)*10)+(x-pad-size); // 0..99 
    } 
    } 
} 

那么对于任意给定点：x，y

for (int nx=x-pad_size; nx<=x+pad_size; nx++) { 
    for (int ny=y-pad_size; ny<=y+pad_size; ny++) { 
    if (-1!=grid[nx][ny] && !(nx==x && ny==y)) { 
     // grid[p.x][p.y] is a neighbor of grid[x][y] 
    } 
    } 
} 

Answer 6

如何分解所需的位？类似的isOccupied(x,y)方法，对于出界外值返回false：

public boolean isOccupied(int x, int y) { 
    if (!inXRange(x) || !inYRange(y)) 
     return false; 
    return occupied[y][x]; // or [x][y] depending on row/col major preferences 
    } 

于是，计数邻居的方法将是非常简单的：

public int countNeighbours(int x, int y) { 
    int neighbours = 0; 
    for (int dx = -1; dx <= 1; ++dx) { 
     for (int dy = -1; dy <= 1; ++dy) { 
     if (((x != 0) || (y != 0)) && isOccupied(x, y)) 
      neighbours += 1; 
     } 
    } 
    return neighbours; 
    }