The PG Test Software Project - Software/Blog

Building a DFS Maze Generator
Using The Recursive Backtracking Algorithm!

    This is my continuing project to build software games, board games, mazes, and the like.

    The technology I am using is HTML5/Canvas and JavaScript, important tools for anyone working on the Web.

    This particular application is perhaps more geared towards developers and computer scientists than general users but if you really like mazes you might enjoy watching how a maze gets automatically generated, right before your very eyes! And if you like you can delve into the algorithms either by reading here, looking at the code, or looking online.

    To create a project that is more than trivial, yet simple enough to understand, I have chosen a 15x15 size matrix for maze creation.

    Ok, so just what is the Recursive Backtracking Algorithm? Quite a mouthful you might say, particularly if you have never studied Computer Science. But actually it is relatively simple to understand and something we probably all have done in our lives.

    Consider talking a walk in the forest, along a trail, and you are looking for some destination at the end of that trail but you are not sure of the path you need to take. As you walk along, every time you come to a junction, where there is at least one and perhaps a few choices to make, you remember that point, then you chose one of the paths and follow it until it either reaches the goal or ends up as a dead end. If it reaches the goal, than great! You have won. If it is a dead end, you go back (backtrack) to the last point where you had to make a choice about which path to chose. Then when you get back to that junction point you mark off the path you took which was a dead end (so you don't go over it again), and you try another path.

    That's it! Well almost. That is the backtracking part. The recursive part is how you get back to that path, in a computer. Computers have what is called a stack, like a stack of plates. So after you make your choice of a path you put each new step you make on that stack of steps, in this case. Then, if you hit a dead end, you just "pop" each step off that stack and go back (backtrack) to where you made a choice of paths. Then you mark the failed path and strike out in a new direction!

    Of course, what I described is how you would search using paths that already existed. Here we are creating a path that does not yet exist in our grid. The logic however is pretty much the same, kind of like turning your socks inside out and wearing them. Here again, in the forest, you create a path, until you finally run out of paths to make. At that point, one of the paths will be correct.

    That is the high level view. For those interested in the high level view of the coding and data structures you can follow from here.

    First we need a few data structures. A grid of cells, in this case a matrix, 15x15, of unconnected cells. My representation is a matrix, in this case of 225 cells, with each cell represented by an array size 4, where the value can be either 0 or 1. So [1, 1, 1, 1], starts with the left wall of the cell, the top wall of the cell, the right wall of the cell, and the bottom of the cell. If the value is 1, then there is no link in that direction, if the value is 0, then there is a link (or path) in that direction. So for cell [1], the second cell in the matrix, row 0, column 1, a value of [0, 1, 0, 1] would mean the left wall isn't there, the top wall is there, the right wall isn't there, and the bottom wall is there. Of course the values for the adjacent cells must match up.

    Next, we need a stack that contains all the cells not yet visited. We need a stack of cells that have been visited. For debugging purposes, I have included a separate, static stack of cells, that have been visited.

    When we begin the program we must load the stack of not visited cells with all the cells in the matrix, or in this case 225 cells. We initialize the stack of visited cells to null.

    Now we are set to begin. We must chose one of the cells as the start point, the current cell. I typically use the cell in the top left corner of the matrix, [0,0].

while there are more cells that have not been visited
-->find all neighbors (adjacent) cells that have not been connected to the current cell
-->if unlinked neighbor(s) are found
---->choose one randomly
---->connect this cell to the current cell
---->remove the current cell from the not visited stack (if it has not already been removed)
---->push the current cell onto the visited stack (this stack is used to backtrack)
---->make the cell we just connected, the current cell
->else (no unlinked neighbors found)
---->if the visited stack is not empty
-------->pop this stack, make that cell the current cell
---->else (the visited stack is empty)
-------->choose a cell (randomly) from the not visited stack
-------->make this the current cell
---->end if (visited stack not empty)
-->end if (unlinked neighbor found)
end while (more cells not visitied)

    Please note, this is a general high level view. The basic algorithm is the same but you can used different types of data structures to implement the details. The important thing, from a CS point of view, is this is a variation of depth first search, using a recursive stack, and random choices when confronted with more than one path. In essence we are turning DFS inside out, using a DFS to carve out a set of paths that at some point, will connect to the end of the maze, or the goal.

    This algorithm will create a maze for you with a guaranteed path, but typically you will want to fine tune the matrix to make the game a bit more interesting. The path from start to finish, usually takes many twists and turns, but there may not be all that many junctions that you face along the way. So you will have to use the arrow keys and go left, right, up, down, etc, many times, but you will not face all that many points where you have to ask, "which path should I choose?".

    There are other interesting questions here, like are you guaranteed to create a path (you are, at least after running this 100s of times, I have always created one), for example, and how would you prove it? Also, are there other ways to create a maze automatically, and yes there are.

    This is just to whet the appetite and get you started!

    I always appreciate any comments and suggestions.

Comments and suggestions are always welcome.
Best regards, Phil Gennuso