Issue with my recursive maze traversal algorithm

问题:

The purpose of my code is to create a program that will read in a maze and store it into a 2D array and solve it. I got the program to read the maze and put it into the array but my recursive algorithm is not working and this is the third different time I have changed it trying to get it to work. So could you help me get this to work?

Edit:I found out the problem with my original algorithm in the sense I got it to solve the maze but I have ran into another problem. The program is not printing out the correct things. Also this is just for my curiosity. I have already found out how to get it to work another way.

Maze Code:

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

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

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

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

    }   

Maze Solver Code:

public class SolveMaze1
{
    public static void main (String[] args)
    {
        Maze1 maze = new Maze1();
        maze.readMaze();
        maze.printMaze();
        maze.goNorth();
        maze.printMaze();
    }
}

Desired outcome:

xxxxxxxxxxxxxxxxxxFx
x     x       xxxx x
x xxxxx xxxxx   xx x
x xxxxx xxxxxxx xx x
x            xx xx x
x xxxxxxxxxx xx    x
xxxxxxxxxxxxSxxxxxxx

xxxxxxxxxxxxxxxxxxFx
xVVVVVxPPPPPPPxxxxPx
xVxxxxxPxxxxxPPPxxPx
xVxxxxxPxxxxxxxPxxPx
xVVVVVVPPPPPPxxPxxPx
xVxxxxxxxxxxPxxPPPPx
xxxxxxxxxxxxSxxxxxxx

My Outcome:

    xxxxxxxxxxxxxxxxxxFx
    xVVVVVxVVVVVVVxxxxVx
    xVxxxxxVxxxxxVVVxxVx
    xVxxxxxVxxxxxxxVxxVx
    xVVVVVVVVVVVVxxVxxVx
    xVxxxxxxxxxxVxxVVVVx
    xxxxxxxxxxxxSxxxxxxx

回答1:

Determine what your base condition (case) is. In this case, your base case would probably be to determine if the present position (x, y) is greater than the ceiling, less than the floor, less than the left wall or greater than the right wall.

Next, you should probably determine if the present position (x, y) is the 'end of maze' character or treasure.

Then determine if the present position (x, y) is the 'start of maze' character.

At this point, I would have my algorithm draw a character in that position if all other conditions have been met. This character would represent that the position has been visited. Later on, you could choose to traverse the coordinates that you have collected and replace this character with a blank space if you choose.

The hard part is done. Now you call the method recursively, this time passing in the new coordinates, once for each direction you want your iterator/solver to go. Ex. if (checkPath(r, c-1) == true) // go west

At which point, you can now change the visited path of the maze to spaces. Ex. maze[r][c] = ' ';

This is the best I can do without giving you the entire answer.

回答2:

There's a lot of good advice in the comments; I'll just try and summarize them as best I can.

MePePeR's Advice: Use one method call

Transform your individual goXXXX() calls into a single go(dx, dy) call. If you are trying to tackle recursion (as your question suggests), you should probably be pretty familiar with writing your own methods first. Notice that each goXXXX() method is almost identical, except in each one you modify the currCol and currRow variables. If you pass in the amount of change as parameters (i.e., the change for currCol as dx and the change for currRow as dy), you can use the same method over and over, just giving it different values. A move east would be go(1, 0), a move south would be go(0, -1), etc.

If you aren't very comfortable with passing parameters, just give it a try, post the updated code and we can guide you through issues you encounter.

Hot Lick's advice: Use a debugger.

You've already taken the first step here with your printMaze method. If you aren't developing in an IDE (I didn't when I first started learning), debuggers can be a little hard to use. In that case, you'll need to simply use more System.out.println statements to get more information on the execution of your code. If you are using and IDE, start trying out the debugger. They're really easy to use once you start playing around with them. Once again, if you get stuck, talk to us and we can help guide you.

One last pointer: notice that your maze printout has this:

xVVx
PPVx
xPxx

Since you are only supposed to go north, south, east or west into a free space, how are you able to get a V in the upper right corner? It's an indication that your code is possibly either marking the wrong cell, or allowing a move that's illegal.