Escaping the prison - finding the shortest way

Question

I have given an assignment where I have to escape a labyrinth. The goal is to find the shortest way. I have done some research and there seem to be two strategies to solve the problem: the Depth-first search and Breadth-first search, where the first starts at the root (Starting point in maze) and explores as far as possible along each branch before backtracking and the second begins at a root node and inspects all the neighboring nodes. Then for each of those neighbor nodes in turn, it inspects their neighbor nodes which were unvisited, and so on.

I have implemented both algorithms (non-recursive implementations) that will go on until they find the end:

/**
 * A non-recursive implementation of DFS
 * @param maze
 */
void solveUsingDepthFirst(IMaze maze) {
    Stack<IMazePosition> candidates = new Stack<IMazePosition>();
    //insert start position
    candidates.push(maze.getStartPosition());

    IMazePosition currentPosition;
    IMazePosition nextPosition;
    while (!candidates.empty()) {
        currentPosition = candidates.pop();

        if (maze.isMazeSolved(currentPosition)) break;

        //mark the current position
        maze.markPosition(currentPosition, maze.getPathMark());
      // maze.printMaze();
        // Check for possible ways to go
        nextPosition = currentPosition.north();
        if (maze.canMove(nextPosition)) candidates.push(nextPosition);
        nextPosition = currentPosition.east();
        if (maze.canMove(nextPosition)) candidates.push(nextPosition);
        nextPosition = currentPosition.south();
        if (maze.canMove(nextPosition)) candidates.push(nextPosition);
        nextPosition = currentPosition.west();
        if (maze.canMove(nextPosition)) candidates.push(nextPosition);
    }

    System.out.println(!candidates.empty() ? "Done" : "Sorry, could not do it");
    maze.printMaze();
}

/**
 * A non-recursive implementation of BFS
 * @param maze
 */
void solveUsingBreadthFirst(IMaze maze) {
    LinkedList<IMazePosition> candidates = new LinkedList<IMazePosition>();
    //insert start position
    candidates.add(maze.getStartPosition());

    IMazePosition currentPosition;
    IMazePosition nextPosition;
    while (!candidates.isEmpty()) {
        currentPosition = candidates.removeFirst();

        if (maze.isMazeSolved(currentPosition)) break;

        //markPosition the current position
        maze.markPosition(currentPosition, maze.getPathMark());
     //   maze.printMaze();

        // Check for possible ways to go
        nextPosition = currentPosition.north();
        if (maze.canMove(nextPosition)) candidates.add(nextPosition);
        nextPosition = currentPosition.east();
        if (maze.canMove(nextPosition)) candidates.add(nextPosition);
        nextPosition = currentPosition.south();
        if (maze.canMove(nextPosition)) candidates.add(nextPosition);
        nextPosition = currentPosition.west();
        if (maze.canMove(nextPosition)) candidates.add(nextPosition);
    }

    System.out.println(!candidates.isEmpty() ? "Done" : "Sorry, could not do it");
    maze.printMaze();
}

The map (or the maze) is represented as char[][]. The MazePosition is a representation of coordinates:

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

Now with that code, I have all the possible paths from start to end that I was able to find until I found the end for the first time - is it fair to assume that the shortest path is amongst them? Given that I have the possible paths, how would I go with finding the shortest? And, is the code for path generation any good at all? Can I optimize any of the routines I already have.

Also, as far as I know, there are no "holes" in the maze, which means I can always stick to the wall.

Answer 1

Reviewing Code:

Names

When naming classes in hierarchies, share the naming conventions used in the standard libraries. Therefore, your top level interface should be Maze, not IMaze. Likewise, IMazePosition.

Repetition

You are repeating yourself both small and large here.

Small: notice that you repeat yourself for each of the cardinal directions (north, south, east, west). That code is screaming for a loop:

for(MazePosition nextPosition : crntPosition.getNeighbors()) {
    if (maze.canMove(nextPosition)) candidates.add(nextPosition);
}

Large: notice that solveUsingDepthFirst and solveUsingBreadthFirst are the same except that they order the points differently. This suggests that you have overlooked an abstraction: a SearchOrder.

public interface SearchOrder {
    boolean isEmpty();
    MazePosition next();
    void add(MazePosition candidate);
}

public class DepthFirstSearchOrder implements SearchOrder {
   Stack<MazePosition> stack = new Stack<MazePosition> ();

   // implement the interface accessing this.stack 
}

public class BreadthFirstSearchOrder implements SearchOrder {
   // notice that candidates is a List<>, because the interface
   // really doesn't care about the implementation.
   List<MazePosition> candidates = new LinkedList<MazePosition> ();

   // implement the interface using this.candidates
}

void solveUsingBreadthFirst(Maze maze) {
    solve(maze, new BreadthFirstSearchOrder());
}

void solve(Maze maze, SearchOrder order) {
    // ...
}

Missing Requirements

It looks like you aren't keeping track of the moves you have made; your existing example seems to tell you if a solution exists, but it doesn't actually report what the solution is. This may or may not be a flaw - depending on the requirements.

Also, it's not fair to assume that your shortest solution in among them. Imagine a maze that is a big ring, with the exit right next to the start - your depth first search can go the wrong way around the ring, giving you the longest solution instead of the shortest. (The first result found in a breadth first search will be the shortest).

What you are missing is the ability to measure how far you have traveled when you reach the exit. So you need something to count the number of moves you have made, so that you can tell if the current path you are taking has improved on your best so far.

If you had such a thing, you could (by generalizing it further) abandon search branches when they are guaranteed to be worse than the solution you have already found....