I am using what is known as a Depth First Search to solve a maze using my own Stack created class for an assignment. The reason I believe I am getting this error is because my program is never meeting the finishSpot condition. I have used the debugger and it looks like it is infinitely stuck at the Point before the finishSpot. My logic seems to be mostly correct except until the point where my maze solver tries to finish the maze, so i just need help meeting that last condition that is causing my program to crash.
This is a sample maze where 's' is start and 'f' is finish and '*' is wall.
*****
*s* *
* * *
* f*
*****
This is my Main which uses my LinkedStack class which I can post if needed.
//Creates a Stack and determines the start and endpoints.
public static void solveDFS( char [][] maze ){
LinkedStack stack = new LinkedStack();
Point currentSpot = findPoint( maze,'s' );
Point finishSpot = findPoint( maze, 'f' );
findPath( maze,currentSpot, finishSpot,stack );
}
//Finds a point by searching for a char.
private static Point findPoint( char [][] maze, char c ) {
for ( int i = 0; i < maze.length; i++ ) {
for ( int j = 0; j < maze[i].length; j++ ) {
if ( maze[i][j] == c ) {
return new Point(i, j);
}
}
}
return null;
}
//Search algorithm looks for all neighbor locations
private static boolean findPath( char [][] maze, Point currentSpot, Point finishSpot, LinkedStack stack ){
boolean hasSolution = false;
stack.push(currentSpot);
while( currentSpot != finishSpot && !stack.isEmpty() ){
// Checks Right
if( currentSpot.x < maze.length ){
if( maze[currentSpot.x + 1][currentSpot.y] == ' '){
stack.push(new Point( currentSpot.x + 1, currentSpot.y ));
}
}
// Checks Left
if( currentSpot.x > 0 ){
if( maze[currentSpot.x - 1][currentSpot.y] == ' '){
stack.push(new Point( currentSpot.x - 1, currentSpot.y ));
}
}
// Checks Up
if( currentSpot.y > 0 ){
if( maze[currentSpot.x][currentSpot.y - 1] == ' ' ){
stack.push(new Point( currentSpot.x, currentSpot.y - 1));
}
}
// Checks Down
if( currentSpot.y < maze[currentSpot.x].length ){
if( maze[currentSpot.x][currentSpot.y + 1] == ' '){
stack.push(new Point( currentSpot.x, currentSpot.y + 1));
}
}
// Checks Finish (My program never meets this condition help!)
if( currentSpot == finishSpot ){
printMaze(maze);
hasSolution = true;
}
currentSpot = stack.pop();
findPath( maze, currentSpot, finishSpot, stack );
}
return hasSolution;
}
