4
\$\begingroup\$

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();
        }       
    }
}
\$\endgroup\$
  • \$\begingroup\$ Did you write the hashCode() method yourself? Or did your IDE provide it for you? (Just curious) \$\endgroup\$ – Hungry Blue Dev Feb 18 '15 at 7:44
  • 1
    \$\begingroup\$ I did write it myself. Followed some of the directive from Effective Java. Did you see any issues with the implementation? \$\endgroup\$ – sc_ray Feb 19 '15 at 3:21
  • \$\begingroup\$ 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. \$\endgroup\$ – Hungry Blue Dev Feb 19 '15 at 7:17
2
\$\begingroup\$
  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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.