Maze solver issue (Getting stack overflow error)

Question

So we are given a maze with walls(W) open path(O) a start pt (S) and a finish pt (F).

I am trying to write an algorithm that takes the maze file and then turns it into a 2D array of points to make a grid.

Once I have the grid, I want to start on the 'S' character in the maze and try to find whether or not it is possible to traverse through the O's to get to the F. (Return a boolean true/false)

I know that this maze is solvable, so why am I getting a StackOverFlowError..?

Here is the Maze1.txt file:

WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW
WSOOOOOOOOOOOOOOWOOOOOOOOOOOOOOOOOWOOOOOOOOOOOOOOOWOOOOOOW
WWOOOOOOOOOOOOOWWWWWWWWWWWWWOOOOOOOOOOWWWWWWWWWWWWWOOOOOOW
WWWWWWOOOOOOOOOOOOWWWWWWWOOOOOOOOOOOOWWWWWWWWWWWWWWWWOOOOW
WOOOOOOWWWWWWWWWWWWWWOOOOOOOOOOOWWWWWWWWOOOOOOOOOOOOOOOWWW
WOOOOWWWWWWWOOOOOOWWWWOOOOOOWWWWWWWWWWWOOOOWWWWWWWWWOWWWWW
WOOOWWWWWWWWWWWWOOWWWWWWWWWWWWOOOOOOOOOOOOWWWWWWWWWOOOOOWW
WOOWWWWWWWWWWWWWOOWWWWWWWWWWWWWWWWWOOOOOOOWWWWWWWWWWWWOOOW
WOWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWOOOOOOOWWWWWWWWWWWOOW
WOWWWWWWWWWWWWWOOOOOOOOOOOOOOOOOOOOOOOOOOOOWWWWWWWWWWWWOOW
WOOOOOOOOOOOOOOOOWWWWOOOOOOOOWWWWWWWOOOOOOWWWWWWWWWWWWWOFW
WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW

Here is my code(new attempt):

import java.io.File;
import java.io.FileNotFoundException;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Stack;
import java.awt.Point;


public class MazeExplorer {
    static Point startPoint = new Point();
    static Point finishPoint = new Point();
    final static int mazeHeight = 12;
    final static int mazeWidth = 58;
    static char[][] mazePoints = new char[mazeHeight][mazeWidth];
    Stack<Point> pointsNotTraversed = new Stack<Point>();
    Point pt = new Point();
    static HashSet<Point> previousLocations = new HashSet<Point>();
    static Stack<Point> nextPoints = new Stack<Point>();


    public static void main(String[] args) throws FileNotFoundException{

        System.out.println("Please enter the file name of your Maze");
        Scanner console = new Scanner(System.in);
        File f = new File(console.nextLine());
        Scanner sc = new Scanner(f);

        if(!sc.hasNextLine()){
            System.out.println("Sorry, please enter a file name with the extension, that contains a maze!");
        }

        System.out.println("So, you want to know if your maze is solvable.....?");


        for (int row = 0; row < mazeHeight && sc.hasNext(); row++) {
            final String mazeRow = sc.next(); //Get the next row from the scanner.
            mazePoints[row] = mazeRow.toCharArray(); //Convert the row into a char[].
        }

            //identify the finish point
        for(int i = 0; i < mazeHeight; i++){
            for(int j = 0; j<mazeWidth; j++){
                if(mazePoints[i][j] == 'F'){
                    finishPoint = new Point(i, j);

                }

            }
        }

        // Identify the start point
       for(int i = 0; i< mazeHeight; i++){
           for(int j = 0; j < mazeWidth; j++){
               if(mazePoints[i][j] == 'S'){
                 startPoint = new Point(i , j);

               }
           }
       }

       isTraversable(startPoint);

    }

        public static  boolean isTraversable(Point current){

            boolean isSolvable = false;

            do {
                mazePoints[current.x][current.y] = ' ';

                if (mazePoints[current.y - 1][current.x] == 'O'){ //up dir
                   nextPoints.push(new Point(current.y - 1, current.x));
                    mazePoints[current.y - 1][current.x] = ' ';  //'X' marks where you've already been


                }
                if(mazePoints[current.y + 1][current.x] == 'O'){ // below direction
                    nextPoints.push(new Point(current.y + 1, current.x));
                    mazePoints[current.y + 1][current.x] = ' ';


                }
                if(mazePoints[current.y][current.x + 1] == 'O'){ // to the right
                    nextPoints.push(new Point(current.y, current.x + 1));
                    mazePoints[current.y][current.x + 1] = ' ';


                }
                if(mazePoints[current.y][current.x - 1] == 'O'){ // to the left
                    nextPoints.push(new Point(current.y, current.x - 1));
                    mazePoints[current.y][current.x - 1] = ' ';


                }
                if(mazePoints[current.y][current.x] == 'F'){
                    isSolvable = true;
                    System.out.println("MAZE IS SOLVABLE, YAHOOOOOO!!!!!!");
                }

                current = nextPoints.peek();
                nextPoints.pop();
                isTraversable(current);


            } while(!current.equals('F') && !nextPoints.isEmpty()); 


            return isSolvable;

            }

}

Answer 1

You're getting the stack overflow error for the following reason:

public static  boolean isTraversable(Point current){
        boolean isSolvable = false;
        Stack<Point> dumbPoints = new Stack<>(); // visited
        dumbPoints.push(current); // pt is now visited
        previousLocations.add(startPoint); // starts with the 'S' point
        while(!dumbPoints.isEmpty()){
            Point test = dumbPoints.pop();
            if(previousLocations.contains(test)){
                continue; // This gets called, and while loop skips to next iteration
            }
          /* None of this code matters right now, it never gets looked at */

        } // End of while loop

        isTraversable(current);
        return isSolvable;
        }

You send startPoint into the isTraversable() method. Inside the method its referred to as current. You then push current AKA startPoint into the stack and then add startPoint to the previousLocations set.

The while loop runs because dumbPoints is not empty (you put current AKA startPoint in there).

Inside the while loop you make a new point test and set it equal to the top item in the stack (which is current, AKA startPoint).

You check to see if(previousLocations.contains(test)) is true, and it is. You added startPoint to the previousLocations set 3 lines up. Since it does contain startPoint it continues on to the next iteration of the while loop.

The next time into the while loop the stack is empty because you popped out the only item that was in it (test). So this time the while loop does not get executed.

We then skip down to the very next line after the while loop:

isTraversable(current);

Which starts everything I just stated all over again. This runs forever until your computer runs out of memory. Hence your error.

Suggestion I would suggest trying a different approach. You asked a question about this problem yesterday I believe and someone else suggested pushing all neighboring points into the stack. I think this is a good idea. Instead of pushing the current item into the stack you can push all neighboring O's into the stack and then recursively call the isTraversable method on those points. This would continue until a true or false is returned and you'll have your answer.

This is probably one of the cleaner approaches that you could use that isn't all that far off from the code you have already created.