# Shortest path in maze

Please help review my code.

public class Maze {
// question: give a maze. Find shortest path from left top corner to right bottom corner.
// 1 is wall. cannot go thru.
int minFoundLen = Integer.MAX_VALUE;
int m = 0;
int n = 0;
public void findPath(int[][] mazePlan){
if(mazePlan.length == 0) return;

m = mazePlan.length;
n = mazePlan.length;
int[][] path = new int[m][n];

helper(mazePlan, 0, 0, 0,path);
System.out.println("shortest path is " + minFoundLen);
}

private void helper(int[][] maze, int x, int y, int pathLen,int[][] path){
if(x < 0 || y < 0 || x >= m || y >= n){
return;
}
if(path[x][y]!=0){
return;
}
if(maze[x][y] != 0){
return;
}
if(x == m-1 && y == n-1){
minFoundLen = Math.min(minFoundLen, pathLen);
return;
}
path[x][y] = 1;
helper(maze, x+1,y,pathLen+1,path);
helper(maze, x-1,y,pathLen+1,path);
helper(maze, x,y+1,pathLen+1,path);
helper(maze, x,y-1,pathLen+1,path);
path[x][y] = 0;

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

Maze maze = new Maze();
maze.findPath(mazePlan);
}
}

• This looks like a weird, informal implementation of Dijkstra’s Algorithm. Is that what you were trying to achieve? – Zack May 6 '16 at 5:09

## 1 Answer

1 Algorithm

This is not Dijkstra's algorithm and that is not breadth-first search either. It's an unweighted brute-force shortest path algorithm. Basically, you generate all possible paths from the source node (top-left cell) to the target node (bottom-right) cell.

On my machine (2.5 GHz) the following maze takes about 300 milliseconds to solve:

int[][] mazePlan = {
{0,1,0,0,0,0,0,0},
{0,0,0,1,0,0,0,0},
{0,0,0,0,0,0,0,0},
{1,1,1,0,0,0,0,0},
{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0},
};


2 Coding

You should rename the fields minFoundLen, n and m to something like shortestPathLengthSoFar mazeHeight and mazeWidth, respectively. Also, you do not have to initialize m and n to zero; Java initializes integer fields to zero by default.

Taking into consideration what you do with int[][] path, I suggest you rename it to boolean[][] visited.

System.out.println("shortest path is " + minFoundLen);


It's not funky to print the result of an algorithm to standard output; instead, return the actual result, and let the caller of the algorithm do whatever he/she wants.

You can always store maze and visited in the fields of your object; that way, helper asks only three arguments instead of five.

if(path[x][y]!=0){
return;
}

1. There should be one space before and after a binary operator.
2. There should be one space before and after a parenthesized expression.

So, combining the two above points you should rather write:

if (path[x][y] != 0) {
return;
}


You should also separate "logical blocks" by a single empty line; like this:

    if (maze[x][y] != 0) {
return;
}

if (x == m - 1 && y == n - 1) {
minFoundLen = Math.min(minFoundLen, pathLen);
return;
}

path[x][y] = 1;

helper(maze, x + 1, y, pathLen + 1, path);
helper(maze, x - 1, y, pathLen + 1, path);
helper(maze, x, y + 1, pathLen + 1, path);
helper(maze, x, y - 1, pathLen + 1, path);

path[x][y] = 0;


And don't forget that you should have a space after any comma.

3 Alternative impelmentation

I have gathered all the points and used breadth-first search for solving the maze. That it how it might look:

Maze.java:

import java.awt.Point;
import java.util.List;
import java.util.Objects;

public class Maze {

private static final boolean CELL_OCCUPIED = true;

private final boolean[][] maze;

public Maze(final boolean[][] maze) {
Objects.requireNonNull(maze, "The input maze is null.");

final int numberOfRows = maze.length;

if (numberOfRows == 0) {
throw new IllegalArgumentException("The input maze is empty.");
}

int numberOfColumns = 0;

for (int row = 0; row < maze.length; ++row) {
numberOfColumns = Math.max(numberOfColumns, maze[row].length);
}

this.maze = new boolean[numberOfRows][numberOfColumns];

for (int row = 0; row < numberOfRows; ++row) {
for (int column = 0;
column < Math.min(numberOfColumns, maze[row].length);
column++) {
this.maze[row][column] = maze[row][column];
}
}
}

public int getWidth() {
return maze.length;
}

public int getHeight() {
return maze.length;
}

public boolean cellIsFree(final Point p) {
return cellIsFree(p.x, p.y);
}

public boolean cellIsWithinMaze(final Point p) {
return p.x >= 0 && p.x < getWidth() && p.y >= 0 && p.y < getHeight();
}

public boolean cellIsTraversible(final Point p) {
return cellIsWithinMaze(p) && cellIsFree(p);
}

public boolean cellIsFree(final int x, final int y) {
checkXCoordinate(x);
checkYCoordinate(y);
return maze[y][x] != CELL_OCCUPIED;
}

public String withPath(final List<Point> path) {
final char[][] matrix = new char[getHeight()][getWidth()];

for (int i = 0; i < matrix.length; ++i) {
for (int j = 0; j < matrix.length; ++j) {
matrix[i][j] = maze[i][j] ? 'x' : '.';
}
}

for (final Point p : path) {
matrix[p.y][p.x] = 'o';
}

final StringBuilder sb = new StringBuilder();

sb.append(new String(matrix));

for (int i = 1; i < matrix.length; ++i) {
sb.append('\n');
sb.append(new String(matrix[i]));
}

return sb.toString();
}

private void checkXCoordinate(final int x) {
if (x < 0) {
throw new IndexOutOfBoundsException(
"The x-coordinate is negative: " + x + ".");
}

if (x >= maze.length) {
throw new IndexOutOfBoundsException(
"The x-coordinate is too large (" + x +
"). The amount of columns in this maze is " +
maze.length + ".");
}
}

private void checkYCoordinate(final int y) {
if (y < 0) {
throw new IndexOutOfBoundsException(
"The y-coordinate is negative: " + y + ".");
}

if (y >= maze.length) {
throw new IndexOutOfBoundsException(
"The y-coordinate is too large (" + y +
"). The amount of rows in this maze is " +
maze.length + ".");
}
}
}


MazePathFinder.java:

package review;

import java.awt.Point;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Queue;

public class MazePathFinder {

private Maze maze;
private Point source;
private Point target;
private boolean[][] visited;
private Map<Point, Point> parents;

public MazePathFinder() {}

private MazePathFinder(final Maze maze,
final Point source,
final Point target) {
Objects.requireNonNull(maze, "The input maze is null.");
Objects.requireNonNull(source, "The source node is null.");
Objects.requireNonNull(target, "The target node is null.");

this.maze = maze;
this.source = source;
this.target = target;

checkSourceNode();
checkTargetNode();

this.visited = new boolean[maze.getHeight()][maze.getWidth()];
this.parents = new HashMap<>();
this.parents.put(source, null);
}

public List<Point> findPath(final Maze maze,
final Point source,
final Point target) {
return new MazePathFinder(maze, source, target).compute();
}

private List<Point> compute() {
final Queue<Point> queue = new ArrayDeque<>();
final Map<Point, Integer> distances = new HashMap<>();

queue.add(source);
distances.put(source, 0);

while (!queue.isEmpty()) {
// Removes the head of the queue.
final Point current = queue.remove();

if (current.equals(target)) {
return constructPath();
}

for (final Point child : generateChildren(current)) {
if (!parents.containsKey(child)) {
parents.put(child, current);
// Appends 'child' to the end of this queue.
queue.add(child);
}
}
}

// null means that the target node is not reachable
// from the source node.
return null;
}

private List<Point> constructPath() {
Point current = target;
final List<Point> path = new ArrayList<>();

while (current != null) {
path.add(current);
current = parents.get(current);
}

Collections.<Point>reverse(path);
return path;
}

private Iterable<Point> generateChildren(final Point current) {
final Point north = new Point(current.x, current.y - 1);
final Point south = new Point(current.x, current.y + 1);
final Point west = new Point(current.x - 1, current.y);
final Point east = new Point(current.x + 1, current.y);

final List<Point> childList = new ArrayList<>(4);

if (maze.cellIsTraversible(north)) {
childList.add(north);
}

if (maze.cellIsTraversible(south)) {
childList.add(south);
}

if (maze.cellIsTraversible(west)) {
childList.add(west);
}

if (maze.cellIsTraversible(east)) {
childList.add(east);
}

return childList;
}

private void checkSourceNode() {
checkNode(source,
"The source node (" + source + ") is outside the maze. " +
"The width of the maze is " + maze.getWidth() + " and " +
"the height of the maze is " + maze.getHeight() + ".");

if (!maze.cellIsFree(source.x, source.y)) {
throw new IllegalArgumentException(
"The source node (" + source + ") is at a occupied cell.");
}
}

private void checkTargetNode() {
checkNode(target,
"The target node (" + target + ") is outside the maze. " +
"The width of the maze is " + maze.getWidth() + " and " +
"the height of the maze is " + maze.getHeight() + ".");

if (!maze.cellIsFree(target.x, target.y)) {
throw new IllegalArgumentException(
"The target node (" + target + ") is at a occupied cell.");
}
}

private void checkNode(final Point node, final String errorMessage) {
if (node.x < 0
|| node.x >= maze.getWidth()
|| node.y < 0
|| node.y >= maze.getHeight()) {
throw new IllegalArgumentException(errorMessage);
}
}

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

boolean[][] maze2 = new boolean[mazePlan.length][mazePlan.length];

for (int i = 0; i < maze2.length; ++i) {
for (int j = 0; j < maze2[i].length; ++j) {
maze2[i][j] = mazePlan[i][j] > 0;
}
}

final Maze maze = new Maze(maze2);
final Point source = new Point(); // Same as new Point(0, 0):
final Point target = new Point(7, 5);

long startTime = System.nanoTime();
final List<Point> path = new MazePathFinder().findPath(maze,
source,
target);
long endTime  = System.nanoTime();

System.out.printf("BFS maze finder in %d milliseconds.\n",
(endTime - startTime) / 1_000_000L);

System.out.println("Shortest path length: " + (path.size() - 1));
System.out.println(maze.withPath(path));
}
}


Hope that helps.