4 replies to this topic

[zerolink]

Good evening everyone
 
I've been working on this programming assignment for quite a bit and can't seem to get a certain recursive method to work.
Before posting the code (since theprogram is pretty long) here's all the info you might ask me for(thanks in advance!):
 
It is a program design to find and
highlight a solution to a maze.

A maze is composed of a grid of rooms
held in a 2D array.

Each room has at least one open door,
and several walls.

If a wall is in place, I can't continue
down that path.

The requirements are:

I must have a method that gives me an
array of doors (a sub class of the Maze class) that are highlighted
and show a path that is displayed when the program is run.

I have to use a boolean array to mark
my path to make sure I don't go in circles.

 

Each wall has an int designating it,
the North wall is 0, east is 1, etc.
 
So far, this is my code:

 

public class MazeSolution implements MazeSolver {

    boolean[][] marked;
    static int lastDoor = -1;
    ArrayList<Maze.Door> correctPath = new ArrayList<>();


    public ArrayList<Maze.Door> solveMaze(int startRow, int finishRow, int startCol, int finishCol, Maze maze) {
        marked = new boolean[maze.getRows()][maze.getColumns()];
        return solveMaze(startRow, finishRow, startCol, finishCol, maze, marked);
    } // end getPath

    public ArrayList<Maze.Door> solveMaze(int startRow, int finishRow, int startCol, int finishCol, Maze maze, boolean[][] marked) {
        int row = startRow;
        int column = startCol;
        boolean door = true;
        if (row == finishRow && column == finishCol) {
            correctPath.add(new Maze.Door(row, column, maze.NO_DIRECTION, Color.red));
            return correctPath;
        }
        for (int wall = 0; wall < 4; wall++) {
            boolean wallExists = maze.isClosed(row, column, wall);
            if (!wallExists) {
                if (wall == 0) {
                    if (!marked[row - 1][column]) {
                        lastDoor = wall;
                        door = wallExists;
                    }
                }
                if (wall == 1) {
                    if (!marked[row][column + 1]) {
                        lastDoor = wall;
                        door = wallExists;
                    }
                }
                if (wall == 2) {
                    if (!marked[row + 1][column]) {
                        lastDoor = wall;
                        door = wallExists;
                }
                if (wall == 3) {
                    if (!marked[row][column - 1]) {
                        lastDoor = wall;
                        door = wallExists;
                    }
                }
            }
        }
        
        System.out.println(lastDoor + "\t" + door + "\t");
        if (door) {
            System.out.println(lastDoor + "::" + door);
            marked[row][column] = true;
            int doorLocale = lastDoor;
            if (doorLocale == 0) {
                return solveMaze(row + 1, finishRow, column, finishCol, maze, marked);
            }
            if (doorLocale == 1) {
                return solveMaze(row, finishRow, column - 1, finishCol, maze, marked);
            }
            if (doorLocale == 2) {
                return solveMaze(row - 1, finishRow, column, finishCol, maze, marked);
            }
            if (doorLocale == 3) {
                return solveMaze(row, finishRow, column+1, finishCol, maze, marked);
            }
        }

          if (!door && lastDoor == 0) {
         marked[row][column] = true;
         correctPath.add(new Maze.Door(row, column, maze.NO_DIRECTION, Color.red));
         return solveMaze(row - 1, finishRow, column, finishCol, maze, marked);
         }
         if (!door && lastDoor == 1) {
         marked[row][column] = true;
         correctPath.add(new Maze.Door(row, column, maze.NO_DIRECTION, Color.red));
         return solveMaze(row, finishRow, column + 1, finishCol, maze, marked);
         }
         if (!door && lastDoor == 2) {
         marked[row][column] = true;
         correctPath.add(new Maze.Door(row, column, maze.NO_DIRECTION, Color.red));
         return solveMaze(row + 1, finishRow, column, finishCol, maze, marked);
         }
         if (!door && lastDoor == 3) {
         marked[startRow][startCol] = true;
         correctPath.add(new Maze.Door(startRow, startCol, maze.NO_DIRECTION, Color.red));
         return solveMaze(row, finishRow, column - 1, finishCol, maze, marked);
         } 
    }
        return null;
} 
}

 

Can someone help me figure out why my code isn't working? I've been stuck on this for days and can't see what's wrong.

Thank you!

 

Edited by zerolink, 05 March 2013 - 06:13 PM.

[dargueta]

What's your code doing that it shouldn't?

[zerolink]

What it should be doing is backtracking when it hits a dead end. But instead it just calls it quits. The only advice my teacher gave me is to get-rid of the for loop and that I don't need acknowledge tracking. Someone told me I should make sure it returns null when it reaches a dead end because it will go backwards through the stack until it can find another path to take, but in my code returning null just terminates the entire program (as it should).

[dargueta]

I think the problem might be where you've placed your return null. I reworked your code a bit to make it more readable and alter the logic a tad:

 

 

if (door)
{
    System.out.println(lastDoor + "::" + door);
    marked[row][column] = true;
 
    switch (lastDoor)
    {
        case 0:
            return solveMaze(row + 1, finishRow, column, finishCol, maze, marked);
            
        case 1:
            return solveMaze(row, finishRow, column - 1, finishCol, maze, marked);
            
        case 2:
            return solveMaze(row - 1, finishRow, column, finishCol, maze, marked);
        case 3:
            return solveMaze(row, finishRow, column+1, finishCol, maze, marked);
 
        default:
            return null;
    }
}
else
{
    switch(lastDoor)
    {
        case 0:
            marked[row][column] = true;
            correctPath.add(new Maze.Door(row, column, maze.NO_DIRECTION, Color.red));
            return solveMaze(row - 1, finishRow, column, finishCol, maze, marked);
             
        case 1:
            marked[row][column] = true;
            correctPath.add(new Maze.Door(row, column, maze.NO_DIRECTION, Color.red));
            return solveMaze(row, finishRow, column + 1, finishCol, maze, marked);
        case 2:
            marked[row][column] = true;
            correctPath.add(new Maze.Door(row, column, maze.NO_DIRECTION, Color.red));
            return solveMaze(row + 1, finishRow, column, finishCol, maze, marked);
            
        case 3:
            marked[startRow][startCol] = true;
            correctPath.add(new Maze.Door(startRow, startCol, maze.NO_DIRECTION, Color.red));
            return solveMaze(row, finishRow, column - 1, finishCol, maze, marked);
            
        default:
            return null;
    } 
}

Edited by dargueta, 06 March 2013 - 01:12 PM.

[zerolink]

Well, after emailing my professor and listening to his advice (which consisted mainly of him telling me I'm not thinking recursively and to look at an unrelated program he did) I rewrote my code to the following:

public class MazeSolution implements MazeSolver {

    boolean[][] marked;
    ArrayList<Maze.Door> correctPath = new ArrayList<>();

    public ArrayList<Maze.Door> solveMaze(int startRow, int finishRow, int startCol, int finishCol, Maze maze) {
        marked = new boolean[maze.getRows()][maze.getColumns()];
        return solveMaze(startRow, finishRow, startCol, finishCol, maze, marked);
    }

    public ArrayList<Maze.Door> solveMaze(int startRow, int finishRow, int startCol, int finishCol, Maze maze, boolean[][] marked) {
        int row = startRow;
        int column = startCol;

        if (row == finishRow && column == finishCol) {
            correctPath.add(new Maze.Door(row, column, maze.NO_DIRECTION, Color.red));
            return correctPath;
        }
        if (marked[row][column]) {
            return null;
        }
        marked[row][column] = true;
        if (!maze.isClosed(row, column, Maze.NORTH)) {
            if (solveMaze(row - 1, finishRow, column, finishCol, maze, marked) != null) {
                System.out.println(Maze.NORTH);
                correctPath.add(new Maze.Door(row, column, maze.NO_DIRECTION, Color.red));
            }
        }
        if (!maze.isClosed(row, column, Maze.EAST)) {
            if (solveMaze(row, finishRow, column + 1, finishCol, maze, marked) != null) {
                System.out.println(Maze.EAST);
                correctPath.add(new Maze.Door(row, column, maze.NO_DIRECTION, Color.red));
            }
        }
        if (!maze.isClosed(row, column, Maze.SOUTH)) {
            if (solveMaze(row + 1, finishRow, column, finishCol, maze, marked) != null) {
                System.out.println(Maze.SOUTH);
                correctPath.add(new Maze.Door(row, column, maze.NO_DIRECTION, Color.red));
            }
        }
        if (!maze.isClosed(row, column, Maze.WEST)) {
            if (solveMaze(row, finishRow, column - 1, finishCol, maze, marked) != null) {
                System.out.println(Maze.WEST);
                correctPath.add(new Maze.Door(row, column, maze.NO_DIRECTION, Color.red));
            }
        }
        return null;
    }
    // end getPath
} // end MazeSolution

It's still not working right, but it's a step in the right direction. The problem now is making it continue down the correct path and try another path when null is returned.