Find Shortest Path in a Maze with Recursive Algorithm

Question

I made a little recursive algorithm to find a solution to a maze in the following format

###S###
##___##
##_#_##
#__#_##
#E___##

Where a '#' represents a wall, and '_' represents an open space (free to move through). 'S' represents the start location, 'E' represents the end location.

My algorithm works fine, but I'm wondering how to modify it to work for the shortest path.

/**
 * findPath()
 * 
 * @param location - Point to search
 * @return true when maze solution is found, false otherwise
 */
private boolean findPath(Point location) {
    // We have reached the end point, and solved the maze
    if (location.equals(maze.getEndCoords())) {
        System.out.println("Found path length: " + pathLength);
        maze.setMazeArray(mazeArray);
        return true;
    }

    ArrayList<Point> possibleMoves = new ArrayList<Point>();
    // Move Right
    possibleMoves.add(new Point(location.x + 1, location.y));
    // Down Move
    possibleMoves.add(new Point(location.x, location.y - 1));
    // Move Left
    possibleMoves.add(new Point(location.x - 1, location.y));
    // Move Up
    possibleMoves.add(new Point(location.x, location.y + 1));

    for (Point potentialMove : possibleMoves) {
        if (spaceIsFree(potentialMove)) {
            // Move to the free space
            mazeArray[potentialMove.x][potentialMove.y] = currentPathChar;
            // Increment path characters as alphabet
            if (currentPathChar == 'z')
                currentPathChar = 'a';
            else
                currentPathChar++;
            // Increment path length
            pathLength++;

            // Find the next path to traverse
            if (findPath(potentialMove)) {
                return true;
            }

            // Backtrack, this route doesn't lead to the end
            mazeArray[potentialMove.x][potentialMove.y] = Maze.SPACE_CHAR;
            if (currentPathChar == 'a')
                currentPathChar = 'z';
            else
                currentPathChar--;
            // Decrease path length
            pathLength--;
        }
    }

    // Previous space needs to make another move
    // We will also return false if the maze cannot be solved.
    return false;
}

In the first block is where I find the path and break it out. The char[][] array with the path written on it is set as well, which is later printed out as the result.

It works well, but I'm wondering what would be the best way to modify it to not break out after it finds the first successful path, but keep going until it finds the shortest possible path.

I tried doing something like this, modifying the findPath() method and adding a shortestPath and hasFoundPath variable. The first indicating length of the shortest path found so far, and the hasFoundPath variable indicating whether or not we have found any path.

    // We have reached the end point, and solved the maze
    if (location.equals(maze.getEndCoords())) {
        System.out.println("Found path length: " + pathLength);
        // Is this path shorter than the previous?
        if (hasFoundPath && pathLength < shortestPathLength) {
            maze.setMazeArray(mazeArray);
            shortestPathLength = pathLength;
        } else if (!hasFoundPath) {
            hasFoundPath = true;
            maze.setMazeArray(mazeArray);
            shortestPathLength = pathLength;            
        }
        //return true;
    }

But I haven't been able to get it to set the mazeArray to the correct values of any shortest path it may find.

Any guidance would be appreciated :) Thanks

spaceIsFree() method simply makes sure the up/left/down/right coordinates are valid before moving to them. So it makes sure the char is an '_' or 'E' and it isn't out of bounds.

Answer 1

Your code appears to perform a depth-first search (DFS). To find the shortest path you will want to switch to a breadth-first search (BFS). It's not something you can do by adding a few variables to your existing code. It will require rewriting your algorithm.

One way to convert a DFS into a BFS is to get rid of the recursion and switch to using an explicit stack to keep track of which nodes you've visited so far. Each iteration of your search loop, you (1) pop a node off the stack; (2) check if that node is the solution; and (3) push each of its children onto the stack. In pseudo code, that looks like:

Depth-first search

stack.push(startNode)

while not stack.isEmpty:
    node = stack.pop()

    if node is solution:
        return
    else:
        stack.pushAll(node.children)

If you then switch the stack to a queue this will implicitly become a BFS, and a BFS will naturally find the shortest path(s).

Breadth-first serarch

queue.add(startNode)

while not queue.isEmpty:
    node = queue.remove()

    if node is solution:
        return
    else:
        queue.addAll(node.children)

A couple of additional notes:

1. The above algorithms are suitable for trees: mazes that don't have loops. If your mazes have loops then you'll need to make sure you don't revisit nodes you've already seen. In that case, you'll need to add logic to keep track of all the already visited nodes and avoid adding them onto the stack/queue a second time.

2. As written, these algorithms will find the target node but they don't remember the path that got them there. Adding that is an exercise for the reader.