Maze path searching DFS java

Question

I am working on a little program to solve a maze by DFS. But it seemed that the algorithm stops too early before it find it's goal. Could anyone maybe give me a hint what I'm doing wrong?

SO walls are 1's, 3 is the goal, and i mark the path with a 2.

code:

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Stack;

public class Maze {

    private final int size;
    private final int[][] maze;

    Maze(int[][] maze){
        this.size = maze.length;
        this.maze = maze;
    }

    private boolean inBounds(int number){
        return number >= 0 && number < this.size;
    }

    /*
     * This one has no information where the end point is so it uses DFS to find a path to the 
     * the end point. The end point must be marked by a 3.
     * 
     * procedure DFS-iterative(G,v):
     * let S be a stack
     * S.push(v)
     * while S is not empty
     *       v = S.pop()
     *       if v is not labeled as discovered:
     *          label v as discovered
     *          for all edges from v to w in G.adjacentEdges(v) do
     *              S.push(w)
     * 
     * 
     */
    public void solve(Node start){
        Stack<Node> stack = new Stack<Node>();
        HashSet<Node> visited = new HashSet<Node>();
        stack.push(start);
        while(!stack.isEmpty()){
            Node tmp = stack.pop();
            this.maze[tmp.getY()][tmp.getX()] = 2;
            if(!visited.contains(tmp)){
                visited.add(tmp);
                for(Node n : this.getAdjacentEdges(tmp))
                    stack.push(n);
            }

        }
    }


    private List<Node> getAdjacentEdges(Node tmp) {
        List<Node> neighbours = new ArrayList<Node>();
        if(this.inBounds(tmp.getX()+1)){
            if(this.maze[tmp.getY()][tmp.getX()+1] != 1){
                neighbours.add(new Node(tmp.getX()+1, tmp.getY()));
            }
        }
        if(this.inBounds(tmp.getX()-1)){
            if(this.maze[tmp.getY()][tmp.getX()-1] != 1){
                neighbours.add(new Node(tmp.getX()-1, tmp.getY()));
            }
        }
        if(this.inBounds(tmp.getY()+1)){
            if(this.maze[tmp.getY()+1][tmp.getX()] != 1){
                neighbours.add(new Node(tmp.getX(), tmp.getY()+1));
            }
        }
        if(this.inBounds(tmp.getY()-1)){
            if(this.maze[tmp.getY()-1][tmp.getX()] != 1){
                neighbours.add(new Node(tmp.getX(), tmp.getY()-1));
            }
        }
        return neighbours;
    }


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

            };
        Maze m = new Maze(maze);
        m.solve(new Node(1,1));
        for(int i = 0; i < maze.length; i++){
            for(int j = 0; j < maze[i].length; j++){
                System.out.print(" " + maze[i][j] + " ");
            }
            System.out.println();
        }
    }
}

The node class:

public class Node {
    private int x;
    private int y;


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


    int getX(){
        return this.x;
    }

    int getY(){
        return this.y;
    }

    @Override
    public int hashCode(){
        return this.getX()+this.getY()+31;
    }

    @Override
    public boolean equals(Object obj){
        if (obj == this) return true;
        if (obj == null || obj.getClass() != this.getClass()) return false; 
        Node tmp = (Node) obj; 
        return tmp.getX() == this.getX() && this.getY() == tmp.getY();
    }

    @Override 
    public String toString(){
        return "x: " + this.getX() + " y: " + this.getY();
    }
}

Edgar Rokjān Edgar Rokjān · Accepted Answer · 2015-11-21T20:53:05

There're a few bugs in your code. I slightly modified your code and now it works.

Some key observations:

1) Your inBounds method is applied incorrectly because dimensions of maze array aren't equal. That's why algorithm doesn't reach a number of grids in the maze. So I deleted inBounds method, modified Maze constructor to accept both dimensions sizes and added two methods: inBoundsY and inBoundsX to check each dimension separately.

2) I'm sure, that the idea of marking every visited grid as it lies in the path is incorrect. I added new array called prev to store previous grid for every grid in the path. Then I changed your solve method and added fillPath method to fill all grids from the path by 2. Then we can simply print all maze and show relust.

New code looks like this:

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Stack;

public class Maze {

    private int[][] maze;
    // previous grids array
    private Node[][] prev;

    private int sizeX;
    private int sizeY;

    private Node lastNode;

    Maze(int[][] maze, int sizeY, int sizeX) {
        this.maze = maze;
        this.sizeY = sizeY;
        this.sizeX = sizeX;

        prev = new Node[sizeY][sizeX];
    }

    private boolean inBoundsX(int number){
        return number >= 0 && number < sizeX;
    }

    private boolean inBoundsY(int number){
        return number >= 0 && number < sizeY;
    }

    public void solve(Node start){
        Stack<Node> stack = new Stack<>();
        HashSet<Node> visited = new HashSet<>();

        stack.push(start);

        while(!stack.isEmpty()) {
            Node tmp = stack.pop();
            visited.add(tmp);

            if (maze[tmp.getY()][tmp.getX()] == 3) {
                lastNode = tmp;
                break;
            }

            for(Node node : this.getAdjacentEdges(tmp)) {
                if (!visited.contains(node)) {
                    stack.push(node);
                    prev[node.getY()][node.getX()] = tmp;
                }
            }
        }
    }

    public void fillPath() {
        if (lastNode == null) {
            System.out.println("No path in maze");
        } else {
            // assume, that start point and end point are different
            for (;;) {
                lastNode = prev[lastNode.getY()][lastNode.getX()];

                // There's no previous node for start point, so we can break
                if (lastNode == null) {
                    break;
                }

                maze[lastNode.getY()][lastNode.getX()] = 2;

            }
        }
    }

    private List<Node> getAdjacentEdges(Node tmp) {
        List<Node> neighbours = new ArrayList<Node>();
        if(this.inBoundsX(tmp.getX()+1)){
            if(this.maze[tmp.getY()][tmp.getX()+1] != 1){
                neighbours.add(new Node(tmp.getX()+1, tmp.getY()));
            }
        }
        if(this.inBoundsX(tmp.getX()-1)){
            if(this.maze[tmp.getY()][tmp.getX()-1] != 1){
                neighbours.add(new Node(tmp.getX()-1, tmp.getY()));
            }
        }
        if(this.inBoundsY(tmp.getY()+1)){
            if(this.maze[tmp.getY()+1][tmp.getX()] != 1){
                neighbours.add(new Node(tmp.getX(), tmp.getY()+1));
            }
        }
        if(this.inBoundsY(tmp.getY()-1)){
            if(this.maze[tmp.getY()-1][tmp.getX()] != 1){
                neighbours.add(new Node(tmp.getX(), tmp.getY()-1));
            }
        }
        return neighbours;
    }


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

                };

        // Create maze with certain dimensions
        Maze m = new Maze(maze, 10, 13);

        m.solve(new Node(1,1));

        m.fillPath();

        for(int i = 0; i < maze.length; i++){
            for(int j = 0; j < maze[i].length; j++){
                System.out.print(" " + maze[i][j] + " ");
            }
            System.out.println();
        }
    }
}

Result will be:

1  1  1  1  1  1  1  1  1  1  1  1  1 
1  2  1  0  1  0  1  2  2  2  2  2  1 
1  2  1  0  0  0  1  2  1  1  1  2  1 
1  2  0  0  1  1  1  2  0  0  0  2  1 
1  2  1  2  2  2  2  2  1  1  1  2  1 
1  2  1  2  1  1  1  0  1  0  0  2  1 
1  2  1  2  1  0  0  0  1  1  1  2  1 
1  2  1  2  1  1  1  0  1  0  1  2  1 
1  2  2  2  0  0  0  0  0  0  1  3  1 
1  1  1  1  1  1  1  1  1  1  1  1  1

Maze path searching DFS java

1 Answers