Shortest path through a maze

Question

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();
 } 
 }
}

• Hungry Blue Dev: Did you write the hashCode() method yourself? Or did your IDE provide it for you? (Just curious)
• sc_ray: I did write it myself. Followed some of the directive from Effective Java. Did you see any issues with the implementation?
• Hungry Blue Dev: 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.

Answer 1

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.