Maze Traversal Algorithm With Recursion

Question

I have a program that reads in a maze from a file and puts it into a 2D array and navigates its way though it using recursion and places a P everywhere its been and a V every where its been twice. Somewhere in my algorithm there is a problem that occurs that causes the maze to only have Vs. I've put in many println statements trying to debug the problem. I'm new to Java and I am probably missing something obvious but I cannot find out the problem for the life of me.

Maze code:

public static boolean goNorth(){
        boolean success;
        if(maze[currCol][currRow - 1] == CLEAR){
            currRow = currRow - 1;
            maze[currCol][currRow] = PATH;
            if (maze[currCol][currRow] == maze[finishCol][finishRow]){ 
            success = true;
            } else {
                success = goNorth();
                if(!success){
                success = goWest();
                    if(!success){
                    success = goEast();
                        if(!success){
                        maze[currCol][currRow] = VISITED;
                        currRow = currRow + 1;
                        }
                    }
                }
            }
        } else {
            success = false;
    }
    return success;
}

public static boolean goWest(){
        boolean success;
        if(maze[currCol - 1][currRow] == CLEAR){
            currCol = currCol - 1;
            maze[currCol][currRow] = PATH;
            if (maze[currCol][currRow] == FINISH){
            success = true;
            } else {
            success = goWest();
                if(!success){
                success = goSouth();
                    if(!success){
                    success = goNorth();
                        if(!success){
                            maze[currCol][currRow] = VISITED;
                        currCol = currCol + 1;
                        }
                        }
                    }
                }
            } else {
                success = false;
        }
        return success;
    }

public static boolean goEast(){
        boolean success;
        if(maze[currCol + 1][currRow] == CLEAR){
            currCol = currCol + 1;
            maze[currCol][currRow] = PATH;
            if (maze[currCol][currRow] == FINISH){
            success = true;
            } else {
            success = goEast();
                if(!success){
                success = goNorth();
                    if(!success){
                    success = goSouth();
                        if(!success){
                            maze[currCol][currRow] = VISITED;
                            currCol = currCol - 1;
                            }
                        }
                    }
                }
            } else {
                success = false;
        }
        return success;
    }

public static boolean goSouth(){
        boolean success;
        if(maze[currCol][currRow + 1] == CLEAR){
            currRow = currRow + 1;
            maze[currCol][currRow] = PATH;
            if (maze[currCol][currRow + 1] == FINISH){
            success = true;
            } else {
            success = goSouth();
                if(!success){
                success = goEast();
                    if(!success){
                    success = goWest();
                        if(!success){
                            maze[currCol][currRow] = VISITED;
                            currRow = currRow - 1;
                            }
                        }
                    }
                }
            } else {
                success = false;
        }
        return success;
    }

Desired output:

xxxxxxxxxxxxxxxxxxFx
xVVVVVxPPPPPPPxxxxPx
xVxxxxxPxxxxxPPPxxPx
xVxxxxxPxxxxxxxPxxPx
xVVVVVVPPPPPPxxPxxPx
xVxxxxxxxxxxPxxPPPPx
xxxxxxxxxxxxSxxxxxxx

Output I'm getting:

xxxxxxxxxxxxxxxxxxVx
xVVVVVxVVVVVVVxxxxVx
xVxxxxxVxxxxxVVVxxVx
xVxxxxxVxxxxxxxVxxVx
xVVVVVVVVVVVVxxVxxVx
xVxxxxxxxxxxVxxVVVVx
xxxxxxxxxxxxSxxxxxxx

Answer 1

I have read your solution carefully. The main problem of your code is your recursion is messy.

Take an example: if now is (5,5)(all grids except walls is CLEAR), and in your goNorth method. Then you will be into (4,5) and in a new goNorth method, this method will call goSouth sometimes later, but you will be into (5,5) again! Now the grid around (5,5) is not CLEAR. You can't go anywhere(goNorth and goSouth and so on will return false).

So, you see the problem. Try to think out a new correct recursion to solve this problem.

Answer 2

Your debugging strategy is not very good, and if you change your debugging strategy, you will be able to solve your problem. For example, your primary concern should be the state of the application the first time an incorrect path is chosen (the first time a V shows up where it should have been a P). You need to identify that point and pause the application, looking at the state of the important variables. That will tell you what went wrong.

My advice to you is to use the Eclipse IDE. Set a breakpoint next to the first important part of your code, which can be accomplished simply by double clicking on the left side of that line of code (or by right click and choosing breakpoint option). Then, once you have a breakpoint set, start the debugger in Eclipse. You can start the debugger pretty easily, it's the option next to the run option in the toolbar. Eclipse will automatically pause when it hits your breakpoint and you can step through the code. Eclipse will show you the value of each of your variables and you can use that info to figure out what went wrong.

I apologize if you wanted a solution on your problem and not advice on how to fix it, but you're obviously a beginner and I wouldn't be doing you any favors by doing your homework for you. Anyway, best of luck.

Article on debugging in Eclipse