5
\$\begingroup\$

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) {
                neighbors.add(new Point(i-1, j-1));
            }
            if (i < rows && j < cols-1 && i >= 1 && j >= 0 && array[i][j] != 0) {
                neighbors.add(new Point(i-1, j+1));
            }
            if (i < rows-1 && j < cols && i >= 0 && j >= 1 && array[i][j] != 0) {
                neighbors.add(new Point(i+1, j-1));
            }
            if (i < rows-1 && j < cols-1 && i >= 0 && j >= 0 && array[i][j] != 0) {
                neighbors.add(new Point(i+1, j+1));
            }
        }

        if (i < rows && j < cols && i >= 1 && j >= 0 && array[i][j] != 0) {
            neighbors.add(new Point(i-1, j));
        }

        if (i < rows && j < cols && i >= 0 && j >= 1 && array[i][j] != 0) {
            neighbors.add(new Point(i, j-1));
        }
        if (i < rows && j < cols-1 && i >= 0 && j >= 0 && array[i][j] != 0) {
            neighbors.add(new Point(i, j+1));
        }

        if (i < rows-1 && j < cols && i >= 0 && j >= 0 && array[i][j] != 0) {
            neighbors.add(new Point(i+1, j));
        }

        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.

\$\endgroup\$

2 Answers 2

7
\$\begingroup\$

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).

Minesweeper 8 with no found mines around it

We all know what an 8 means, right? 8 mines around the number, plain and simple.

Minesweeper 8 with classic neighbors

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).

Minesweeper 8 with chess style neighbors

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) };
\$\endgroup\$
0
4
\$\begingroup\$

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[0];
        int ncol = j + offsetRowCol[1];
        if (nrow >= 0 && nrow < rows && ncol >= 0 && ncol < cols) {
            neighbours.add(new Point(nrow, ncol));
        }
    }

The code simply encodes the relative position of neighbors in the two constant arrays. You then scan the possible neighbors for valid points, and add them if they are valid.

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.