# Shortest path through a maze

I was trying to solve this problem in Java:

Given a 2-D array of black and white entries representing a maze with designated entrance and exit points, find the shortest path from entrance to exit, if one exists. The black entry represents a wall and the white entry represents an open space.

I tried to solve it using a variant of the Breadth-First-Search algorithm, where from a starting position, I examine all its possible adjacent positions. If the adjacent spot has not been visited(a Map containing the spaces that have been visited) or is not in the in-process queue, I add it to the in-process queue. If I encounter an adjacent spot that has been visited, I examine its 'weight', if the weight of the adjacent spot is less than one added to the current weight of the space in process, I update the weight of the visited node. I keep on doing this until I encounter the destination or all the nodes in the maze have been processed.

I have crafted my algorithm as follows, it will be great if I could get some feedback on refining it further.

import java.util.Set;
import java.util.List;
import java.util.Queue;
import java.util.Map;
import java.util.HashSet;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.HashMap;

public class ShortestMazePath{
class Node{
private final int x;
private final int y;
private final int weight;
private final Node previous;
Node(int x,int y,Node previous,int weight){
this.x = x;
this.y = y;
this.previous = previous;
this.weight = weight;
}
public int getX(){
return this.x;
}
public int getY(){
return this.y;
}
public int getWeight(){
return this.weight;
}
public Node getPrevious(){
return this.previous;
}
@Override public boolean equals(Object o){
if(o == null){
return false;
}
if(!(o instanceof Node)){
return false;
}
final Node n = (Node)o;
return ((n.x == x) && (n.y == y));
}
@Override public int hashCode(){
int result = 17;
result = 31*result+x;
result = 31*result+y;
return result;
}
@Override public String toString(){
return "Current X is "+this.x+" Current Y is "+this.y;
}
}

private boolean isValid(boolean[][] maze,int m,int n,Node node){
return (node.getX() >=0 && node.getX() < m) &&
(node.getY() >= 0 && node.getY() < n) &&
maze[node.getX()][node.getY()];

}

private Node updatedNode(Node currentNode,Node visitedNode){
if(currentNode.weight + 1 < visitedNode.weight){
return new Node(visitedNode.getX(),
visitedNode.getY(),
currentNode,
currentNode.weight + 1);
}else{
return visitedNode;
}
}

private Set<Node> getNeighbors(Node current,int m,int n,boolean[][] maze){
int currentX = current.getX();
int currentY = current.getY();
int currentWeight = current.getWeight();
Set<Node> validNeighbors = new HashSet<Node>();
List<Node> neighbors = new ArrayList<Node>(){{
add(new Node(currentX-1,currentY,current,currentWeight));
add(new Node(currentX+1,currentY,current,currentWeight));
add(new Node(currentX,currentY+1,current,currentWeight));
add(new Node(currentX,currentY-1,current,currentWeight));}};
for(Node node:neighbors){
if(isValid(maze,m,n,node)){
validNeighbors.add(node);
}
}
return validNeighbors;
}

private static boolean[][] createMaze(){
boolean[][] maze = {{true,true,true},
{true,true,false},
{true,true,false}};
return maze;
}

private void printQueue(Set<Node> q){
for(Node n:q){
System.out.println("Queue contains node"+ n);
}
}

private void printMap(Map<Node,Node> m){
for(Map.Entry<Node,Node> entry:m.entrySet()){
System.out.println("visited contains node "+entry.getKey());
}
}

public Node findPath(boolean[][] maze,int p,int q,Node start,Node end){
Queue<Node> inProcess = new LinkedList<Node>();
Map<Node,Node> visited = new HashMap<Node,Node>();
Set<Node> inProcessQueue = new HashSet<Node>();
inProcess.add(start);
inProcessQueue.add(start);
Node current = null;
while((current = inProcess.poll())!= null){
int currentNodeWeight = current.getWeight();
if(current.equals(end)){
return current;
}else{
Set<Node> neighbors = getNeighbors(current,p,q,maze);
for(Node n:neighbors){
if(!inProcessQueue.contains(n)){
if(visited.containsKey(n)){
Node visitedNode = visited.get(n);
visited.remove(n);
Node updatedNode = updatedNode(current,visitedNode);
visited.put(updatedNode,updatedNode);
}else{
inProcess.add(n);
inProcessQueue.add(n);
}
}
}
visited.put(current,current);
}
}
return null;
}

public static void main(String[] args){
boolean[][] maze = createMaze();
ShortestMazePath spm = new ShortestMazePath();
ShortestMazePath.Node startNode = spm.new Node(0,0,null,0);
ShortestMazePath.Node endNode = spm.new Node(2,1,null,0);
ShortestMazePath.Node pathNode = spm.findPath(maze,3,3,startNode,endNode);
while(pathNode != null){
System.out.println("Reached pathNode"+pathNode);
pathNode = pathNode.getPrevious();
}
}
}

• Did you write the hashCode() method yourself? Or did your IDE provide it for you? (Just curious) – Hungry Blue Dev Feb 18 '15 at 7:44
• I did write it myself. Followed some of the directive from Effective Java. Did you see any issues with the implementation? – sc_ray Feb 19 '15 at 3:21
• No, I don't see any issues... that's why! ;-) Most people have a hard time writing a decent hash function. See this for an example. – Hungry Blue Dev Feb 19 '15 at 7:17

## 1 Answer

1. It looks like there is a bug in this piece of code:

List<Node> neighbors = new ArrayList<Node>(){{
add(new Node(currentX-1,currentY,current,currentWeight));
add(new Node(currentX+1,currentY,current,currentWeight));
add(new Node(currentX,currentY+1,current,currentWeight));
add(new Node(currentX,currentY-1,current,currentWeight));}};


The weight of the neighbors should be currentWeight + 1, not currentWeight(because we need one more step to reach the neighbor from the current node). And I would call it distance, not weight.

2. The updatedNode method is redundant. Nodes are never updated in a breadth-first search. You can get rid of it.

3. Map<Node,Node> visited = new HashMap<Node,Node>(); A map that maps a node to itself doesn't make much sense. I would use a Set<Node> here. And I do not see the point of having a Set inProcess. The entire algorithm is implemented in a pretty strange way. Here is pseudo code of a standard BFS implementation:

discovered = an empty set
queue = an empty queue
startVetrex.dist = 0
queue.add(startVertex)
discovered.add(startVertex)
while not queue.isEmpty():
v = queue.poll()
for neighbor <- neighbors(v):
if not discovered.contains(neighbor):
neighbor.dist = v.dist + 1
neighbor.parent = v
discovered.add(neighbor)
queue.add(neighbor)


That's it. No need to update vertices or having several sets(visited, inQueue and so on).

4. Whitespaces: there should be whitespaces around binary operators, before and after curly brackets, after the for, while and if keywords, between method parameters. For instance,

private Set<Node> getNeighbors(Node current,int m,int n,boolean[][] maze){


should be

private Set<Node> getNeighbors(Node current, int m, int n, boolean[][] maze) {


and

while((current = inProcess.poll())!= null){


should be

while ((current = inProcess.poll()) != null) {

5. Blank lines: it is conventional to have a blank line between methods, constructors and so on. Here is a refined part of your Node class:

class Node {
private final int x;
private final int y;
private final int weight;
private final Node previous;

Node(int x, int y, Node previous, int weight) {
this.x = x;
this.y = y;
this.previous = previous;
this.weight = weight;
}

public int getX(){
return this.x;
}

public int getY(){
return this.y;
}

...
}

6. You should also write documentation comments for all public classes and methods.