Backtracking maze algorithm doesn't seem to be going all the way back

Question

Basically, I have this: First, a bunch of code generates a maze that is non-traversable. It randomly sets walls in certain spaces of a 2D array based on a few parameters. Then I have a backtracking algorithm go through it to knock out walls until the whole thing is traversable. The thing is, the program doesn't seem to be going all the way back in the stack.

It's pretty standard backtracking code. The algorithm starts at a random location, then proceeds thus in pseudocode:

move(x, y){
if you can go up and haven't been there already:
move (x, y - 1)
if you can go right and haven't been there already:
move (x + 1, y)
...
}

And so on for the other directions. Every time you move, two separate 2D arrays of booleans (one temporary, one permanent) are set at the coordinates to show that you've been in a certain element. Once it can't go any further, it checks the permanent 2D array to see if it has been everywhere. If not, it randomly picks a wall that borders between a visited and non visited space (according to the temporary array) and removes it. This whole thing is invoked in a while loop, so once it's traversed a chunk of the maze, the temporary 2D array is reset while the other is kept and it traverses again at another random location until the permanent 2D array shows that the whole maze has been traversed. The check in the move method is compared against the temporary 2D array, not the permanent one.

This almost works, but I kept finding a few unreachable areas in the final generated maze. Otherwise it's doing a wonderful job of generating a maze just the way I want it to. The thing is, I'm finding that the reason for this is that it's not going all the way back in the stack.

If I change it to check the temporary 2D array for completion instead of the permanent one (thus making it do one full traversal in a single run to mark it complete instead of doing a full run across multiple iterations), it will go on and on and on. I have to set a counter to break it. The result is a "maze" with far, far too many walls removed. Checking the route the algorithm takes, I find that it has not been properly backtracking and has not gone back in the stack nearly far enough in the stack and often just gets stuck on a single element for dozens of recursions before declaring itself finished for no reason at all and removing a wall that had zero need to be removed.

I've tried running the earlier one twice, but it keeps knocking out walls that don't need to be knocked out and making the maze too sparse. I have no idea why the heck this is happening.

Johan Wikström Johan Wikström · Accepted Answer · 2011-04-11T12:07:51

I've had a similar problem when trying to make a method for creating a labyrinth. The important thing when making mazes is to try to NOT create isolated "islands" of connected rooms in the maze. Here's my solution in pseudocode

Room r=randomRoom();

while(r!=null){
    recursivelyDigNewDoors(r);
    r=null;
    for(i=0;i<rooms.count;i++){
        if(rooms[i].doors.length == 0 && rooms[i].hasNeighborWithDoor() ){ 
        //if there is a room with no doors and that has a neighbor with doors
        Create a door between the doorless room and the one 
        connected to the rest of your maze
        r=rooms[i];
        }
   }
}

where recursivelyDigNewDoors is a lot like your move() function

In reality, you might like to

describe a "door" as a lack of a wall
and a room without doors as a room with four walls

But the general principle is:

Start your recursive algorithm somewhere
When the algorithm stops: find a place where there's 1 unvisited square and 1 visited.
Link those two together and continue from the previously unvisited square
When no two squares fulfill (2) you're done and all squares are connected

Backtracking maze algorithm doesn't seem to be going all the way back

1 Answers