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

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.