Mazes for Programmers

The Recursive Backtracker Algorithm

The Recursive Backtracker algorithm works very much like Hunt-and-Kill, relying on a constrained random walk to weave its rivery way across our grid. The difference is in how it recovers from dead ends; instead of hunting for another viable cell, it backtracks, retracing its steps until it finds a cell that has an unvisited neighbor.

Let’s walk through it and see how that works in practice. We’ll use a stack to keep track of the cells we’ve visited. A stack is simply a list of items, but with strict rules about how items are added to or removed from it. Adding something to the top of a stack is called pushing, and removing the topmost item is called popping. A stack can only be manipulated via these push ...