java 编程逻辑：如何检查网格中的邻居？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/3775905/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Programming Logic: How to Check for Neighbors in a Grid?
提问by Devoted
I'm having a lot of trouble trying to think of a logical way to check for neighbors in a "grid"-based programming project for class.
我在试图想出一种逻辑方法来检查基于“网格”的类编程项目中的邻居时遇到了很多麻烦。
The main problem I'm having is thinking of a way to effectively check whether its on the sides so that I don't get an index out of bounds error.
我遇到的主要问题是想一种方法来有效地检查它是否在侧面，这样我就不会出现索引越界错误。
EDIT: I forgot to mention that I'm using a 2-dimensional array.
编辑：我忘了提到我使用的是二维数组。
回答by Jon Skeet
Here's a simple way of getting a neighbour position avoiding worrying about the sides:
这是获得邻居位置的简单方法，避免担心双方：
int leftX = (x - 1 + width) % width;
int rightX = (x + 1) % width;
int aboveY = (y - 1 + height) % height;
int belowY = (y + 1) % height;
It's possibly not the most efficient way of doing it, but it keeps each calculation to a single, simple expression. That's assuming you want wrap-around, of course. If you don't, you'll haveto do things conditionally:
这可能不是最有效的方法，但它使每个计算都保持在一个简单的表达式中。当然，这是假设您想要环绕。如果不这样做，你就必须有条件做的事情：
if (x > 0)
{
// Use x - 1
}
if (x < width - 1)
{
// Use x + 1
}
回答by djna
What's it a 2d array of? Perhaps some objects that have state such as "Occupied" and "Empty" or some such? In which case introdcuce a new state such as "Edge" and "Corner" and create the 2-D array 1 cell bigger in every direction. Then your neighbour checker can just use simple +/- logic and then the processing for the set of neighbours can choose to ignore any edges.
什么是二维数组？也许某些对象具有“占用”和“空”等状态？在这种情况下，引入一个新状态，例如“Edge”和“Corner”，并在每个方向上创建更大的二维阵列 1 单元。然后你的邻居检查器可以只使用简单的 +/- 逻辑，然后邻居集的处理可以选择忽略任何边缘。
回答by e2-e4
Basically you want to access the neighbor of a cell, while ensuring you are not out of the grid. You can try a simple algorithm:
基本上你想访问一个单元格的邻居，同时确保你没有脱离网格。您可以尝试一个简单的算法：
Provided that the center cell (where youare) is (x,y), and that you want to check the diagonals as well.
Your grid is [0,W[ on X, and [0,H[ on Y (basically W x H, starting from (0,0))
假设中心单元格（您所在的位置）是(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
}
}
This can be optimized on (i,j), e.g. istarts from 0 if xis 0.
这可以在 (i,j) 上进行优化，例如i，如果x是 0 ，则从 0 开始。
If you don't want the diagonals, you only have to check (x-1,y)(x+1,y)(x,y-1)and (x,y+1),
如果你不想要对角线，你只需要检查(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)
}
回答by Yanick Rochon
There's often (if not always) a sacrifice in term of speed vs. memory; I had to implement a Sudoku solver some time ago in Java, and it was faster to assign each cell a list of cell groups. So, instead of checking boundaries every time, I simply had to iterate over each group, then each cell within each groups. The check was made once to create the groups.
通常（如果不是总是）在速度与内存方面做出牺牲；前段时间我不得不用 Java 实现一个数独求解器，并且为每个单元分配一个单元组列表更快。因此，我不必每次都检查边界，而只需遍历每个组，然后遍历每个组中的每个单元格。进行一次检查以创建组。
Something like :
就像是 ：
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
}
}
}
}
}
then, for any given point : x, y
然后，对于任何给定的点：x, y
for (Point p : n[x][y].pList) {
// grid[p.x][p.y] is a neighbor of grid[x][y]
}
Well, my solution was a little more sophisticated, but the principle is the same. If your grid is a 2-dimension array of objects, the neighbors can actually be the object at grid[nx][ny]instead of points for direct object access.
嗯，我的解决方案稍微复杂一点，但原理是一样的。如果您的网格是一个二维对象数组，则邻居实际上可以是对象，grid[nx][ny]而不是直接访问对象的点。
You will eventually need to check for x>=0, y>=0, x<SIZE_W, and y<SIZE_H, but this solution does the check only onece, so it is in my opinion quite efficient when querying neighbors often for each grid cell. If you need to resize the grid often, then this solution would need to be adapted.
您最终将需要检查x>=0, y>=0, x<SIZE_W, 和y<SIZE_H，但此解决方案只检查一次，因此在我看来，在经常为每个网格单元查询邻居时非常有效。如果您需要经常调整网格大小，则需要调整此解决方案。
Another approach would be to pad your array in each direction with ignoredflag value (such as null, -1, etc.) and simply do a normal check ignoring such cells :
另一种方法是在每个方向上用ignored标志值（例如 null、-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
}
}
}
then for any given point : x,y
然后对于任何给定的点：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]
}
}
}
回答by clstrfsck
How about factoring out the bits you need? Something like an isOccupied(x,y)method that returns false for out-of-bounds values:
如何分解出你需要的位？类似于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
}
Then the count neighbours method will be pretty straightforward:
然后计数邻居方法将非常简单：
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;
}
回答by mbatchkarov
As already mentioned, the left neighbour of [x,y] is [x,y-1] and the right neighbour is [x,y+1], and so on. However, you should also check that y>=1, otherwise you will go out of bounds. Similarly, y must be less than the size of the array. You can do that with an if statement or alternatively (not recommended) you can handle the ArrayIndexOutOfBoundsException.
如前所述，[x,y] 的左邻居是 [x,y-1]，右邻居是 [x,y+1]，依此类推。但是，您还应该检查y> = 1，否则您将越界。同样，y 必须小于数组的大小。您可以使用 if 语句执行此操作，或者（不推荐）您可以处理 ArrayIndexOutOfBoundsException。
