Hi,
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.
okay:
here it is :
assuming neighbor as follows :
suppose this is the data we have
a b c d e
f g h i j
k l m n o
p q r s t
now if you try to look for the neighbors of
a: b ,f
b: a, g, c
m: l, h, n ,r
Now lets build the logic:
for any char retrieve its position [x,y]
check if [m-1],[m+1],[n-1],[n+1] which of these position are valid
and apply them in combination
for example of a:
[x,y] would be [0,0] so we don'e have [-1] for x and y so the possible values for x and y we have 0 1 now lets apply them in combination :
[0,0] which is a it self so ignore it
[0,1] that is b [1,0] that is f //Optionally if you want to consider g as neighbor of a you can
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.
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 have to do things conditionally:
if (x > 0)
{
// Use x - 1
}
if (x < width - 1)
{
// Use x + 1
}
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.
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 you are) 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))
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. i starts from 0 if x is 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),
for (i=-1 ; i<2 ; i+=2)
{
// check (x+i, y)
// check (x, y+i)
}
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.
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
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.
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.
Another approach would be to pad your array in each direction with ignored flag value (such as null, -1, etc.) and simply do a normal check ignoring such cells :
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
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]
}
}
}
How about factoring out the bits you need? Something like an isOccupied(x,y) method that returns false for out-of-bounds values:
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;
}