Stack Overflow error when traversing through a maze

Question

I'm trying to traverse through a maze recursively and im getting a stack overflow error, i understand the problem but am unable to fix it. Would i need to create a separate array to hold all the values that have been visited in the array or is there other ways that would be more efficient that use less lines of code?

Any suggestions would be greatly appreciated.

Here is the input;

5 6       // Row,Col
1 1       // Start Pos
3 4       // End Pos 
1 1 1 1 1
1 0 0 0 1
1 0 1 0 1
1 0 1 0 1
1 0 1 0 1
1 1 1 1 1

Current code:

public class Solve {

    private static int [][] MazeArray;
    private static int Rows;
    private static int Cols;
    private static Point end = new Point();
    private static Point start = new Point();

    public static void ReadFileMakeMaze() {

        Scanner in = new Scanner(System.in);
        System.out.print("Select File: "); // Choose file
        String fileName = in.nextLine();
        fileName = fileName.trim();

        String Buffer = "";
        String[] Buffer2;
        String[] MazeBuffer;
        int Counter = 0;

        try {

            // Read input file
            BufferedReader ReadFileContents = new BufferedReader(new FileReader(fileName+".txt"));
            Buffer = ReadFileContents.readLine();
            MazeBuffer = Buffer.split(" ");

            // Creating MazeArray according to rows and columns from input file.
            Rows = Integer.parseInt(MazeBuffer[0]); 
            Cols = Integer.parseInt(MazeBuffer[1]);
            MazeArray = new int[Rows][Cols];

            // Retrieving start locations and adding them to an X and Y coordinate.
            String[] StartPoints = ReadFileContents.readLine().split(" ");
            start.x = Integer.parseInt(StartPoints[0]);
            start.y = Integer.parseInt(StartPoints[1]);

            // Retrieving end locations and adding them to an X and Y coordinate.
            String[] EndPoints = ReadFileContents.readLine().split(" ");
            end.x = Integer.parseInt(EndPoints[0]);
            end.y = Integer.parseInt(EndPoints[1]);

            while(ReadFileContents.ready()) {
                Buffer = ReadFileContents.readLine();
                Buffer2 = Buffer.split(" ");

                for(int i = 0; i < Buffer2.length; i++) {
                    MazeArray[Counter][i] = Integer.parseInt(Buffer2[i]); // Adding file Maze to MazeArray.
                }
                Counter ++;
                }
            }

            catch(Exception e){
                System.out.println(e); // No files found. 
            }

        System.out.println(SolveMaze(start.x, start.y));
    }


    public static boolean SolveMaze(int x,int y) {

        Print(); // Printing the maze

        if(ReachedEnd(x,y)) {
            MazeArray[x][y] = 5; // 5 represents the end
            System.out.println(Arrays.deepToString(MazeArray));
            return true;

        }else if(MazeArray[x][y] == 1 || MazeArray[x][y] == 8){
            return false;

        }else {

            MazeArray[x][y] = 8; // Marking the path with 8's           
            start.x = x;
            start.y = y;

            // Checking all directions
            if(MazeArray[x][y - 1] == 0 ) {
                System.out.println("Left");
                SolveMaze(x, y - 1);

            }else if(MazeArray[x + 1][y] == 0) {
                System.out.println("Down");
                SolveMaze(x + 1, y);

            }else if(MazeArray[x - 1][y] == 0 ) {
                System.out.println("Up");
                SolveMaze(x - 1, y);

            }else if(MazeArray[x][y + 1] == 0 ) {
                System.out.println("Right");
                SolveMaze(x, y + 1);

            }else {
                System.out.println("Debug");
                MazeArray[x][y] = 0;
                start.x = x;
                start.y = y;
            }
        }
        return false;
    }

    public static boolean DeadEnd(int x, int y) {
        return true; // Solution needed
    }

    public static boolean ReachedEnd(int x, int y) {

        if(x == end.x && y == end.y) { // Check if the end has been reached.  
            return true;
        }else {
            return false;
        }
    }

    public static void Print() {
        System.out.println(Arrays.deepToString(MazeArray));
    }

    public static void main(String[] args) {
        ReadFileMakeMaze();
    }
}

Answer 1

Firstly, like you mentioned in the question, creating a static Collection outside of SolveMaze which keeps a list of "visited" nodes would certainly help. If the node has being visited before then no need to check again.

Secondly, I believe there are a few mistakes within the above code. The table isn't generated correctly into the MazeArray[][], swap Rows and Cols around underneath "// Creating MazeArray according to rows and columns from input file."

The code also doesn't "find" a path, Arrays get defined as int[] array = new int[5] but to access it you have to use array[0] --> array[4] , what happens when I fix the maze is that you start on element 1,1 which is the '0' one row and column in from top left. Then you traverse down the list due to the ordering of the if else statements. After visiting each node you turn the nodes value to an 8. After 4 iterations the code is looking at the bottom 0 in the 2nd row, aka [4][1] above you is now and 8 and since 0's are the only elements you can move to, the node looks left, right and down and sees 1's, then turns and looks up and sees an 8. Thus finishing.

Thirdly, don't make checking up, down, left, right a set of "if else"'s, just a selection of "if's". This way the code will travel all paths. Then you can leave your 8's in and it will de facto not re-run the same node twice, rendering the 'visited' array unneeded. (Although as a general rule, mutating state when traversing through is unadvised)

Fourthly, I cannot get a stack overflow error from the above code so cannot answer the actual question.

On a side note - use tests and things like this become trivial, start small and build it up :) If unsure just checkout junit.