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.