# Java breadth-first search for finding the shortest path on a 2D grid with obstacles

Please review my Breadth-first search algorithm implementation in Java for finding the shortest path on a 2D grid map with obstacles.

The findPath() method receives a map array of integers where 0 is an empty cell, and 1 is an obstacle, the function returns a list of coordinates which is the optimal path or null if such path does not exist.

This code is not a thread-safe, I have no intention of making it such.

 import java.util.LinkedList;
import java.awt.Point;

/**
* Created by Ilya Gazman on 10/17/2018.
*/
public class BFS {

private static final boolean DEBUG = false;

public Point[] findPath(int[][] map, Point position, Point destination) {
if (isOutOfMap(map, position)) {
return null;
}
if (isOutOfMap(map, destination)) {
return null;
}
if (isBlocked(map, position)) {
return null;
}
if (isBlocked(map, destination)) {
return null;
}

map[position.y][position.x] = -1;
int stepCount = 2;
while (!queue1.isEmpty()) {
if(queue1.size() >= map.length * map[0].length){
}
for (Point point : queue1) {
if (point.x == destination.x && point.y == destination.y) {
Point[] optimalPath = new Point[stepCount - 1];
computeSolution(map, point.x, point.y, stepCount - 1, optimalPath);
resetMap(map);
return optimalPath;
}
int finalStepCount = stepCount;
lookAround(map, point, (x, y) -> {
if (isBlocked(map, x, y)) {
return;
}
Point e = new Point(x, y);

map[e.y][e.x] = -finalStepCount;
});
}

if (DEBUG) {
printMap(map);
}

queue1 = queue2;
stepCount++;
}
resetMap(map);
return null;
}

private void resetMap(int[][] map) {
for (int y = 0; y < map.length; y++) {
for (int x = 0; x < map[0].length; x++) {
if (map[y][x] < 0) {
map[y][x] = 0;
}
}
}
}

private boolean isBlocked(int[][] map, Point p) {
return isBlocked(map, p.x, p.y);
}

private boolean isBlocked(int[][] map, int x, int y) {
int i = map[y][x];
return i < 0 || i == 1;
}

private void printMap(int[][] map) {
//noinspection ForLoopReplaceableByForEach
for (int i = 0, mapLength = map.length; i < mapLength; i++) {
int[] aMap = map[i];
for (int x = 0; x < map[0].length; x++) {
System.out.print(aMap[x] + "\t");
}
System.out.println();
}
System.out.println("****************************************");
}

private void computeSolution(int[][] map, int x, int y, int stepCount, Point[] optimalPath) {
if (isOutOfMap(map, x, y) || map[y][x] == 0) {
return;
}

if ( -stepCount != map[y][x]) {
return;
}

Point p = new Point(x, y);
optimalPath[stepCount - 1] = p;
lookAround(map, p, (x1, y1) -> computeSolution(map, x1, y1, stepCount - 1, optimalPath));
}

private void lookAround(int[][] map, Point p, Callback callback) {
callback.look(map, p.x + 1, p.y + 1);
callback.look(map, p.x - 1, p.y + 1);
callback.look(map, p.x - 1, p.y - 1);
callback.look(map, p.x + 1, p.y - 1);
callback.look(map, p.x + 1, p.y);
callback.look(map, p.x - 1, p.y);
callback.look(map, p.x, p.y + 1);
callback.look(map, p.x, p.y - 1);
}

private static boolean isOutOfMap(int[][] map, Point p) {
return isOutOfMap(map, p.x, p.y);
}

private static boolean isOutOfMap(int[][] map, int x, int y) {
if (x < 0 || y < 0) {
return true;
}
return map.length <= y || map[0].length <= x;
}

private interface Callback {
default void look(int[][] map, int x, int y) {
if (isOutOfMap(map, x, y)) {
return;
}
onLook(x, y);
}

void onLook(int x, int y);
}
}


Usage:

public static void main(String... args) {
int[][] myMap = {
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 1, 0, 1, 1, 1, 1},
{0, 0, 0, 1, 0, 1, 0, 0, 0},
{0, 0, 0, 0, 1, 0, 1, 1, 0},
{0, 0, 0, 0, 0, 1, 0, 0, 0},
};

Point[] path = new BFS().findPath(myMap, new Point(8, 0), new Point(8, 2));
for (Point point : path) {
System.out.println(point.x + ", " + point.y);
}
}


Output:

8, 0
7, 0
6, 0
5, 0
4, 1
4, 2
5, 3
6, 2
7, 2
8, 2

• Is this actually working? – Krzysztof Cichocki Oct 22 '18 at 14:55
• @KrzysztofCichocki Yeah, it runs in O(n) where n is the number of nodes. It's a special case of the classic O(v+e) since my e is equal to 8 it becomes redundant. – Ilya Gazman Oct 22 '18 at 15:00
• @IlyaGazman Can you add an example of its usage? i.e. an example of proper inputs and what is expected as output. – esote Oct 22 '18 at 17:44
• @esote Sure, here you go – Ilya Gazman Oct 22 '18 at 17:55

I'm unfamiliar with the algorithm. It looks neat, but I couldn't tell you if it's optimal or not. Most optimization comes from improving the way you go about the algorithm, so I'll suggest stuff for readability.

# Don't stutter

When you check isOutOfMap() for position and destination, there's no need to break them up into multiple if statements. Same goes for isBlocked().

if (isOutOfMap(map, position.x, position.y)
|| isOutOfMap(map, destination.x, destination.y)
|| isBlocked(map, position.x, position.y)
|| isBlocked(map, destination.x, destination.y)) {
return null;
}


While we're at it, why have overloaded methods for isOutOfMap() and isBlocked()? The ultimate result is that you're avoiding directly accessing the Point's parameters x and y.

I would remove isOutofMap(int[][], Point) and isBlocked(int[][], Point) and opt for directly passing the Point's x and y coordinates.

# Use an Exception

Instead of throwing an Error, throw an Exception. You can't recover from an Error, it terminates program execution. Throw an Exception.

throw new IllegalStateException("Map overload");


If you use IllegalStateException you won't need to add throws. I'd opt for the most specific exception type you can find, or make one yourself.

# Use the right loops

You've got stepCount, while(!queue1.isEmpty()) and at the end stepCount++. That's a for loop. Rather than calling it stepCount (redundant), go with old faithful i. It's clear that you're counting with it.

# Decrease the complexity

findPath() is a pretty complex method. We should move some things to their own methods.

If we arrive at our destination, we can call the arrived() method:

private Point[] arrived(int[][] map, int size, Point p) {
Point[] optimalPath = new Point[size];

computeSolution(map, p.x, p.y, size, optimalPath);

resetMap(map);

return optimalPath;
}


I'm sure there are other places to clean up, but you get my point.

# Use final where it makes sense

While others may disagree, I prefer annotating things as final when they are, in fact, final. This lets me know if I accidentially try to modify the value, when it shouldn't really be modified.

# Use the right structures

You're using LinkedList but calling it a queue. While it's true that LinkedList implements the Queue interface, as it goes:

This class is likely to be faster than Stack when used as a stack and faster than LinkedList when used as a queue.

- ArrayDeque

So we'll trust them. Instead of using LinkedList, we can use an ArrayDeque.

# Code

Here's the code I ended up with. Hope this has helped.

import java.awt.Point;
import java.util.ArrayDeque;
import java.util.Queue;

/**
* Created by Ilya Gazman on 10/17/2018.
*/
public class BFS {

private static final boolean DEBUG = false;

public Point[] findPath(final int[][] map,
final Point position,
final Point destination) {
if (isOutOfMap(map, position.x, position.y)
|| isOutOfMap(map, destination.x, destination.y)
|| isBlocked(map, position.x, position.y)
|| isBlocked(map, destination.x, destination.y)) {
return null;
}

Queue<Point> queue1 = new ArrayDeque<>();
Queue<Point> queue2 = new ArrayDeque<>();

map[position.y][position.x] = -1;

for (int i = 2; !queue1.isEmpty(); i++) {
if (queue1.size() >= map.length * map[0].length) {
}

for (Point point : queue1) {
if (point.x == destination.x && point.y == destination.y) {
return arrived(map, i - 1, point);
}

final Queue<Point> finalQueue = queue2;
final int finalStepCount = i;

lookAround(map, point, (x, y) -> {
if (isBlocked(map, x, y)) {
return;
}

Point e = new Point(x, y);

map[e.y][e.x] = -finalStepCount;
});
}

if (DEBUG) {
printMap(map);
}

queue1 = queue2;
queue2 = new ArrayDeque<>();
}

resetMap(map);

return null;
}

private static boolean isOutOfMap(final int[][] map,
final int x,
final int y) {
return x < 0 || y < 0 || map.length <= y || map[0].length <= x;
}

private boolean isBlocked(final int[][] map, final int x, final int y) {
final int i = map[y][x];
return i < 0 || i == 1;
}

private Point[] arrived(final int[][] map, final int size, final Point p) {
final Point[] optimalPath = new Point[size];

computeSolution(map, p.x, p.y, size, optimalPath);

resetMap(map);

return optimalPath;
}

private void resetMap(final int[][] map) {
for (int y = 0; y < map.length; y++) {
for (int x = 0; x < map[0].length; x++) {
if (map[y][x] < 0) {
map[y][x] = 0;
}
}
}
}

private void printMap(final int[][] map) {
for (final int[] r : map) {
for (final int i : r) {
System.out.print(i + "\t");
}

System.out.println();
}

System.out.println("****************************************");
}

private void computeSolution(final int[][] map,
final int x,
final int y,
final int stepCount,
final Point[] optimalPath) {
if (isOutOfMap(map, x, y)
|| map[y][x] == 0
|| map[y][x] != -stepCount) {
return;
}

final Point p = new Point(x, y);

optimalPath[stepCount - 1] = p;

lookAround(map, p, (x1, y1) -> computeSolution(map, x1, y1, stepCount - 1, optimalPath));
}

private void lookAround(final int[][] map,
final Point p,
final Callback callback) {
callback.look(map, p.x + 1, p.y + 1);
callback.look(map, p.x - 1, p.y + 1);
callback.look(map, p.x - 1, p.y - 1);
callback.look(map, p.x + 1, p.y - 1);
callback.look(map, p.x + 1, p.y);
callback.look(map, p.x - 1, p.y);
callback.look(map, p.x, p.y + 1);
callback.look(map, p.x, p.y - 1);
}

private interface Callback {
default void look(final int[][] map, final int x, final int y) {
if (isOutOfMap(map, x, y)) {
return;
}
onLook(x, y);
}

void onLook(int x, int y);
}
}