Java solving a maze with recursion problem

Question

I have an assignment where I am supposed to be able to display the path of a maze from the entrance to the exit and I have gotten it to work to a degree but when the maze gets more complicated with dead ends and such the program goes into infinite recursion. If you could give me any help to point me in the right direction it would be much appreciated.

Mu current theory can be found in the Room class.

Here is the Room class where the references to each room connecting the maze are stored, kind of like a linked list linked in 6 directions, north, south, east, west, up, and down.

import java.util.ArrayList;

public class OurRoom
{
    private OurRoom exits[];
    private String name;
    private static ArrayList<OurRoom> list;

    public OurRoom()
    {
        this(null);
    }

    public OurRoom(String name)
    {
        this.name = name;
        this.list = new ArrayList<OurRoom>();
        exits = new OurRoom[Direction.values().length];
        for(OurRoom exit : exits)
        {
            exit = null;
        }
    }       


    public void connectTo(OurRoom theOtherRoom, Direction direction)
    {
        exits[direction.ordinal()] = theOtherRoom;
        theOtherRoom.exits[direction.getOpposite().ordinal()] = this;
    }

    public OurRoom getExit(Direction direction)
    {
        return exits[direction.ordinal()];
    }

    public boolean lookExit(Direction direction)
    {
        return exits[direction.ordinal()] != null;
    }

    public String getName() {
        return name;
    }

    public OurRoom solveRecursively(OurRoom exit) {
        list.add(this);
        if(this == exit) {
            return this;
        }else { 
            OurRoom temp = null;            
            if(lookExit(Direction.east)) {
                temp = exits[Direction.east.ordinal()].solveRecursively(exit);              
            }   
            else if(lookExit(Direction.up)) {
                temp = exits[Direction.up.ordinal()].solveRecursively(exit);
            }
            else if(lookExit(Direction.south)) {
                temp = exits[Direction.south.ordinal()].solveRecursively(exit);             
            }           
            else if(lookExit(Direction.down)) {
                temp = exits[Direction.down.ordinal()].solveRecursively(exit);
            }
            else if(lookExit(Direction.west)) {
                temp = exits[Direction.west.ordinal()].solveRecursively(exit);      
            }   
            else if(lookExit(Direction.north)) {
                temp = exits[Direction.north.ordinal()].solveRecursively(exit); 
            }
            return temp;
        }
    }

    public ArrayList<OurRoom> getList() {
        return list;
    }

}

Here is the Direction enum

public enum Direction
{
    north, south, east, west, up, down;

    public Direction getOpposite()
    {
        switch(this)
        {
            case north:
                return south;
            case south:
                return north;
            case east:
                return west;
            case west:
                return east;
            case up:
                return down;
            case down:
                return up;
            default:
                return this;
        }
    }
}

And here is an example of how the maze is built.

import java.util.ArrayList;
import java.util.Iterator;

public class OurMaze
{
    private OurRoom entrance, exit;

    public OurMaze()
    {
        this(1);
    }

    public OurMaze(int mazeNumber)
    {
        entrance = null;
        exit = null;
        switch(mazeNumber)
        {
        case 0:
            break;
        case 1:
            this.buildMaze1();
            break;             
        default:
        }
    }

    public OurRoom getEntrance()
    {
        return entrance;
    }

    public OurRoom getExit()
    {
        return exit;
    }

    public Iterator<OurRoom> findPathRecursively() {
        entrance.solveRecursively(exit);
        ArrayList<OurRoom> list = entrance.getList();       
        return list.iterator();
    }

    private void buildMaze1()
    {
        OurRoom room1, room2;

        room1 = new OurRoom("Room 1");
        room2 = new OurRoom("Room 2");
        room1.connectTo(room2, Direction.north);

        entrance = room1;
        exit = room2;
    }

    public static void main(String[] args) {
        OurMaze maze = new OurMaze(1);      
    }
}

Answer 1

I'd bet you need a tree of some kind to keep track of where you've been.

When recursion fails, it usually means that the person writing the method didn't expression the stopping condition properly. What's yours?

I think this was the first game I ever encountered on a computer. It was an IBM mainframe at the school where I got my undergraduate degree. The I/O was on a paper teletype. Many salt tears were wept at the account dollars that were flushed away playing this maze game. Great fun.

Answer 2

You just need to keep two-dimensional array with values indicating whether the cell was visited or not: you don't want to go through the same cell twice.

Apart from that, it's just breadth-first-search (depth-first-search is fine too, if you don't want shortest path).

Some links
http://en.wikipedia.org/wiki/Flood_fill
http://en.wikipedia.org/wiki/Breadth-first_search
http://en.wikipedia.org/wiki/Depth-first_search

Sample search routine.

    void dfs(int i, int j) {
        if cell(i, j) is outside of maze or blocked {
            return
        }
        if visited[i][j] {
            return
        }
        visited[i][j] = true;
        dfs(i + 1, j);
        dfs(i - 1, j);
        dfs(i, j + 1);
        dfs(i, j - 1);
    }

Path itself can be found if, like with visited, for each cell you keep cell from which you came to it. So, printing would look like this (just a pseudocode).

var end = exit_point;
while (end != start_point) {
   print end;
   end = came_from[end];
}

edit
The code above is for two-dimensional maze and I just noticed that you have three-dimensional version. But it's easy to introduce third coordinate in the example above.
Let me know if there're any difficulties.

Answer 3

When solving the maze, represent it as a 6-ary graph where each node is a room and each edge represents travel in one of the six directions. You can then apply some of the well known algorithms for finding shortest paths.

This page describes various solutions for finding paths through graphs that are structured as such. Your graph is easier than the ones that describe real-world maps, since the cost of traveling down any edge is equal to the cost of traveling down any other edge.

Be especially sure to look at Dijkstra's algorithm.

Answer 4

Others have described appropriate approaches to solving this problem, but I think it's worth pointing out exactly why your program won't scale to more complex mazes.

As duffymo hinted, the problem is that your algorithm doesn't do any backtracking correctly - when it takes a branch that turns out to be a dead end, and returns to a previous square, it doesn't remember this at all. And since it tries the exits in a fixed order, it will always retry that failed exit immediately.

Look at how the solveRecursively function is defined, and you'll see that from any given room, only one direction would ever be tried. If a room has an exit to the east, then it doesn't even matter if it has any other exits since the if-else block would never consider them.

So as it turns out, your solving logic will fail (i.e go into an infinite loop between two rooms) in any case where the correct solution isn't the "first" exit from each room in the order you've defined there.

(A quick fix would be to store a simple boolean flag against each room/direction. Set it before you call the recursive call, then if you end up back in that room again, you know that direction doesn't work out and can let the if block fall through to try one of the other exits. Refactoring this to use typical BFS logic, as Nikita suggests, would be better overall)