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;
}
LinkedList<Point> queue1 = new LinkedList<>();
LinkedList<Point> queue2 = new LinkedList<>();
queue1.add(position);
map[position.y][position.x] = -1;
int stepCount = 2;
while (!queue1.isEmpty()) {
if(queue1.size() >= map.length * map[0].length){
throw new Error("Map overload");
}
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;
}
LinkedList<Point> finalQueue = queue2;
int finalStepCount = stepCount;
lookAround(map, point, (x, y) -> {
if (isBlocked(map, x, y)) {
return;
}
Point e = new Point(x, y);
finalQueue.add(e);
map[e.y][e.x] = -finalStepCount;
});
}
if (DEBUG) {
printMap(map);
}
queue1 = queue2;
queue2 = new LinkedList<>();
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
1 Answer 1
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
Stackwhen used as a stack and faster thanLinkedListwhen used as a queue.
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<>();
queue1.add(position);
map[position.y][position.x] = -1;
for (int i = 2; !queue1.isEmpty(); i++) {
if (queue1.size() >= map.length * map[0].length) {
throw new IllegalStateException("Map overload");
}
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);
finalQueue.add(e);
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);
}
}
Explore related questions
See similar questions with these tags.
O(n)wherenis the number of nodes. It's a special case of the classicO(v+e)since myeis equal to 8 it becomes redundant. \$\endgroup\$