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.

Metatarsal

Does it has to be a recursive algorithm? One of the important aspects of Dijkstra's algorithm is shared memory, something that is harder to implement in the context of recursion. – Heel

No it doesn't have to be, just the simple algorithm I initially implemented at first to solve it. – Metatarsal

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.

Ultimatum

Thanks, I will work on reworking the algorithm and post back when I finish :) – Metatarsal

Answer 2

Here's the BFS-search solution I came up with. It marks the starting point as "1", then marks each adjacent one that it can travel to as "2", and each adjacent one to the 2's that can be traveled to as "3" and so on.

Then it starts at the end, and goes backwards using the decrementing "level" values which results in the shortest path.

private LinkedList<Point> findShortestPath(Point startLocation) {
    // This double array keeps track of the "level" of each node.
    // The level increments, starting at the startLocation to represent the path
    int[][] levelArray = new int[mazeArray.length][mazeArray[0].length];

    // Assign every free space as 0, every wall as -1
    for (int i=0; i < mazeArray.length; i++)
        for (int j=0; j< mazeArray[0].length; j++) {
            if (mazeArray[i][j] == Maze.SPACE_CHAR || mazeArray[i][j] == Maze.END_CHAR)
                levelArray[i][j] = 0;
            else
                levelArray[i][j] = -1;
        }

    // Keep track of the traversal in a queue
    LinkedList<Point> queue = new LinkedList<Point>();
    queue.add(startLocation);

    // Mark starting point as 1
    levelArray[startLocation.x][startLocation.y] = 1;

    // Mark every adjacent open node with a numerical level value
    while (!queue.isEmpty()) {
        Point point = queue.poll();
        // Reached the end
        if (point.equals(maze.getEndCoords()))
            break;

        int level = levelArray[point.x][point.y];
        ArrayList<Point> possibleMoves = new ArrayList<Point>();
        // Move Up
        possibleMoves.add(new Point(point.x, point.y + 1));
        // Move Left
        possibleMoves.add(new Point(point.x - 1, point.y));
        // Down Move
        possibleMoves.add(new Point(point.x, point.y - 1));
        // Move Right
        possibleMoves.add(new Point(point.x + 1, point.y));

        for (Point potentialMove: possibleMoves) {
            if (spaceIsValid(potentialMove)) {
                // Able to move here if it is labeled as 0
                if (levelArray[potentialMove.x][potentialMove.y] == 0) {
                    queue.add(potentialMove);
                    // Set this adjacent node as level + 1
                    levelArray[potentialMove.x][potentialMove.y] = level + 1;
                }
            }
        }
    }
    // Couldn't find solution
    if (levelArray[maze.getEndCoords().x][maze.getEndCoords().y] == 0)
        return null;

    LinkedList<Point> shortestPath = new LinkedList<Point>();
    Point pointToAdd = maze.getEndCoords();

    while (!pointToAdd.equals(startLocation)) {
        shortestPath.push(pointToAdd);
        int level = levelArray[pointToAdd.x][pointToAdd.y];
        ArrayList<Point> possibleMoves = new ArrayList<Point>();
        // Move Right
        possibleMoves.add(new Point(pointToAdd.x + 1, pointToAdd.y));
        // Down Move
        possibleMoves.add(new Point(pointToAdd.x, pointToAdd.y - 1));
        // Move Left
        possibleMoves.add(new Point(pointToAdd.x - 1, pointToAdd.y));
        // Move Up
        possibleMoves.add(new Point(pointToAdd.x, pointToAdd.y + 1));

        for (Point potentialMove: possibleMoves)  {
            if (spaceIsValid(potentialMove)) {
                // The shortest level will always be level - 1, from this current node.
                // Longer paths will have higher levels.
                if (levelArray[potentialMove.x][potentialMove.y] == level - 1) {
                    pointToAdd = potentialMove;
                    break;
                }
            }
        }
    }

    return shortestPath;
}

The spaceIsValid() is simply ensuring that the space is not out of bounds.

Metatarsal