# Getting the neighbors of a Point in a 2D grid

Posted on

Problem

I am trying to find an algorithm to find all the defined neighbors of a 2D `Point` (efficiently would be nice, but does not make much of a difference).

Here is my existing code:

``````private static ArrayList<Point> getNeighborsOfPoint(int i, int j) {
ArrayList<Point> neighbors = new ArrayList<Point>();
if (CONSIDER_CORNERS) {
if (i < rows && j < cols && i >= 1 && j >= 1 && array[i][j] != 0) {
}
if (i < rows && j < cols-1 && i >= 1 && j >= 0 && array[i][j] != 0) {
}
if (i < rows-1 && j < cols && i >= 0 && j >= 1 && array[i][j] != 0) {
}
if (i < rows-1 && j < cols-1 && i >= 0 && j >= 0 && array[i][j] != 0) {
}
}

if (i < rows && j < cols && i >= 1 && j >= 0 && array[i][j] != 0) {
}

if (i < rows && j < cols && i >= 0 && j >= 1 && array[i][j] != 0) {
}
if (i < rows && j < cols-1 && i >= 0 && j >= 0 && array[i][j] != 0) {
}

if (i < rows-1 && j < cols && i >= 0 && j >= 0 && array[i][j] != 0) {
}

return neighbors;
}
``````

`CONSIDER_CORNERS` is a `boolean` that is settable by the user, and `Point` is just a simple class that has an `x` and `y` `int` value. `rows` and `cols` are the number of elements in each of the two dimensions.

What I’m looking for mainly is better readability.

Solution

# Improvements

• Use `x` and `y` names to avoid confusion about what is `i` and what is `j`
• I personally find it preferrable to put the `x` parameter first
• `rows` and `cols` should not be static variables, so neither should this method
• Use a double for-loop to loop over the neighbors
• Declare by interface and not implementation (use `List<Point>` when possible)
• Use some maths to check if you’re at a corner or not

# Code

``````private List<Point> getNeighborsOfPoint(int x, int y) {
List<Point> neighbors = new ArrayList<Point>();
for (int xx = -1; xx <= 1; xx++) {
for (int yy = -1; yy <= 1; yy++) {
if (xx == 0 && yy == 0) {
continue; // You are not neighbor to yourself
}
if (!CONSIDER_CORNERS && Math.abs(xx) + Math.abs(yy) > 1) {
continue;
}
if (isOnMap(x + xx, y + yy)) {
neighbors.add(new Point(x + xx, y + yy));
}
}
}
return neighbors;
}

public boolean isOnMap(int x, int y) {
return x >= 0 && y >= 0 && x < cols && y < rows;
}
``````

In this code, I have not added your `array[i][j] != 0` check, but that can easily be added into `isOnMap`, although you could then rename it to `isValidNeighbor` or something.

# Going the extra mile

Having this method, it is very easy to add support for some very crazy neighbor styles. This might not fit your game, but using crazy neighbor styles can transform a concept into an entirely different game.

For example, take Minesweeper Flags (where the objective is to find the mines and not avoid them). We all know what an 8 means, right? 8 mines around the number, plain and simple. Now, what if we transform the way we look for neighbors? To what I call “Chess style” (based on how a Knight moves in Chess). This “simple” change leads to a much greater challenge when playing, leading to all kinds of fun.

The change required for this is really simple, extract a `NEIGHBOR_SET` array:

``````private static final Point[] NEIGHBOR_SET = new Point[]{ new Point(-2, -1), new Point(-2, 1),
new Point(-1, -2), new Point(-1, 2), new Point(1, -2), new Point(1, 2), new Point(2, -1), new Point(2, 1) };

private List<Point> getNeighborsOfPoint(int x, int y) {
List<Point> neighbors = new ArrayList<Point>();
for (Point neighbor : NEIGHBOR_SET) {
if (isOnMap(x + neighbor.x, y + neighbor.y)) {
neighbors.add(new Point(x + neighbor.x, y + neighbor.y));
}
}
return neighbors;
}
``````

Using this method, the special case logic for handling corners and the self neighbor is no longer necessary.

Of course, using the ordinary neighbor set is also possible with this method:

``````private static final Point[] NEIGHBOR_SET = new Point[]{ new Point(-1, -1), new Point(-1, 0),
new Point(-1, 1), new Point(0, -1), new Point(0, 1), new Point(1, -1), new Point(1, 0), new Point(1, 1) };
``````

Code Repetition is a PITA, and your function has a lot of it.

There’s a simple data-driven way to do this, and it’s effective for your conditional on `CONSIDER_CORNERS` too. Consider the two data structures (with the inner array having `{row,col}` offsets:

``````private static final int[][] CORNERS_EXCLUDED = {
{-1, 0},
{ 0,-1},        {0, 1},
{ 1, 0}
};

private static final int[][] CORNERS_INCLUDED = {
{-1,-1},{-1, 0},{-1, 1}
{ 0,-1},        { 0, 1},
{ 1,-1},{ 1, 0},{ 1, 1}
};
``````

Now, with the above two arrays defined…. you can easily do:

``````    ArrayList<Point> neighbors = new ArrayList<Point>();
for (int[] offsetRowCol : (CONSIDER_CORNERS ? CORNERS_INCLUDED : CORNERS_EXCLUDED)) {
int nrow = i + offsetRowCol;
int ncol = j + offsetRowCol;
if (nrow >= 0 && nrow < rows && ncol >= 0 && ncol < cols) {