How does this maze algorithm return the shortest path correctly?

user_17944655 0
Viewed 132

I came across this maze solver algorithm:

public class Maze {

    public static void main(String[] args) {
        char[][] maze = {
                {'.', '.', '.', '0', '0', '0', '0', '0', '0', '0'},
                {'0', '0', '.', '.', '.', '0', '.', '.', '.', '0'},
                {'0', '0', '.', '0', '.', '0', '.', '0', '.', '0'},
                {'.', '.', '.', '0', '.', '0', '.', '0', '.', '0'},
                {'.', '0', '0', '0', '.', '.', '.', '0', '.', '0'},
                {'.', '.', '.', '.', '0', '0', '0', '.', '.', '0'},
                {'.', '0', '0', '.', '.', '.', '0', '.', '.', '0'},
                {'.', '.', '.', '0', '0', '.', '0', '0', '.', '.'},
                {'0', '0', '.', '0', '0', '.', '.', '.', '0', '0'},
                {'0', '0', '0', '0', '0', '0', '0', '.', '.', '.'},
        };

        print(maze);

        if(traverse(maze, 0, 0)) {
            System.out.println("SOLVED maze");
        } else {
            System.out.println("could NOT SOLVE maze");
        }

        print(maze);
    }

    private static void print(char[][] maze) {
        System.out.println("-----------------------");
        for(int x = 0; x < 10; x++) {
            System.out.print("| ");
            for(int y = 0; y < 10; y++) {
                System.out.print(maze[x][y] + " ");
            }
            System.out.println("|");
        }
        System.out.println("-----------------------");
    }

    public static boolean isValidSpot(char[][] maze, int r, int c) {
        if(r >= 0 && r < 10 && c >= 0 && c < 10) {
            return maze[r][c] == '.';
        }
        return false;
    }

    public static boolean traverse(char[][] maze, int r, int c) {
        if(isValidSpot(maze, r, c)) {
            //it is a valid spot
            if(r == 9 && c == 9) {
                return true;
            }

            maze[r][c] = '*';

            //up
            boolean returnValue = traverse(maze, r - 1, c);


            //right
            if(!returnValue) {
                returnValue = traverse(maze, r, c + 1);
            }

            //down
            if(!returnValue) {
                returnValue = traverse(maze, r + 1, c);
            }

            //left
            if(!returnValue) {
                returnValue = traverse(maze, r, c - 1);
            }

            if(returnValue) {
                System.out.println(r + ", " + c);
                maze[r][c] = ' ';
            }
            return returnValue;
        }

        return false;
    }
}

but I can't work out the recursion in my mind. Even if the algorithm hits dead ends while searching for the exit spot and it marks the paths it passed through as invalid to pass through, it somehow returns to the last checkpoint, all while not printing the dead end paths. Which is the part that baffles me the most. How are dead end paths not printed in this algorithm?

I tried printing the maze at every step but still couldn't work out how invalid paths are not printed.

maze recursion algorithm java
2 Answers

The function implements Depth First Search, also knows as DFS to find the path. You can read more on DFS and BFS here. What happens is basically as follow:

  1. Checking if a current coordinate is the end coordinate, if it is returns True

  2. Else, check if you can reach the end by advancing up

    2.1 if you can reach the end by advancing up, print this coordinate and return True

  3. Else, check if you can reach the end by advancing right

    3.1 if you can reach the end by advancing up, print this coordinate and return True

  4. Else, check if you can reach the end by advancing down

    4.1 if you can reach the end by advancing up, print this coordinate and return True

  5. Else, check if you can reach the end by advancing left

    5.1 if you can reach the end by advancing up, print this coordinate and return True

  6. Else, return False, meaning that from this coordinate you can not reach the end.

Instead of keeping a list of states to be visited, the information is being stored in the recursion.

A similar problem with DFS search of a path in a maze can be found here, implemented in Python and might be easier to understand the concept since it is not implemented with recursion but with a list.

Please note that the algorithm that is written does not find the shortest path, but it finds a path. To find the shortest path, you should use BFS since it covers all the paths with x steps before checking paths with x+1 steps.

user_183304360

A Depth First Search is not optimal for finding the shortest path. A Breadth First Search ensures that you are at the shortest path whenever you find a solution (path).

A BFS needs to mark the locations already searched (like '*' in the code), the current path length. And hold a list of locations just reached: the border.

In the next step from the border look at new neighbors, which will form the new border. Should a neighbor be the target ((r == 9 && c == 9) here).

The border is initially the start: {(0, 0)}. The number of border points initially grows, and decreases again as dead-ends are dropped. A fixed size array is complicated, hence a Set or List is more appropriate.

A real recursive BFS is easier, but you might iterate over the borders, and reconstruct the shortest path by leaving "bread crumbs."

For a location a record class is easiest. Since Java 16.

record Location (int row, int column) {
    List<Location> getNeighbors() {
        List<Location> nbs = new ArrayList<>();            
        if (row > 0) {
            nbs.add(new Location(row - 1, column));
        }
        if (row < 10-1) {
            nbs.add(new Location(row + 1, column));
        }
        if (column > 0) {
            nbs.add(new Location(row, column - 1));
        }
        if (column < 10-1) {
            nbs.add(new Location(row, column + 1));
        }
        return nbs;
    }

}

For the border a Set is more suitable as from two old border locations one can reach the same new border location.

Set<Location> border = new HashSet<>();
border.add(new Location(0, 0));
int pathLength = 0;

void moveToNextBorder(Set<Location> border) {
    char breadCrumb = 'a' + pathLength;
    ++pathLength;
    Set<Location> result = new HashSet<>();
    for (Location oldLoc: border) {
        maze[oldLoc.row][oldLoc.column] = breadCrumb;
    }
    for (Location oldLoc: border) {
        for (Location loc: oldLoc.getNeighbors()) {
            if (maze[loc.row][loc.column] == '.') {
                result.add(loc); // Could already have been added.
            }
        }
    }
    border.clear();
    border.addAll(result);
}

To see whether the new border reaches the target:

moveToNextBorder(border);
if (border.contains(new Location(9, 9))) {
    // Take a shortest path, using breadCrumbs downto 'a'.
    Location[] shortestPath = new Location[pathLength];
    ...
}
user_9848230
Related