![recursive backtracking maze generator algorithm python recursive backtracking maze generator algorithm python](https://miro.medium.com/max/2000/1*jAYl6iLdLTPbqnAwixff6g.png)
If you’re not using IE, you can step through the algorithm yourself using this nifty Javascript demo. I’m going to be moving much faster now, chugging along to the end of the algorithm.Īnd we’re done! The result is a perfect maze. So the recursion bottoms out, and we rewind back up the stack. Now, we’ve got two new subfields to recurse into, but hark! We can’t divide them any further without passing our target resolution (our grid is only 5×5, remember). The field in the top-right is a square, so we can randomly choose between a horizontal or a vertical bisection. Let’s do one more quick iteration on the top-right field, now, and see how the recursion bottoms out when you hit your target resolution. (From here on out, I’m going to merge the “add wall” and “erase passage” steps into a single step: you’ve been warned!) So, let’s cut this field in half horizontally this time, and then add a passage through it: (Similarly, when bisecting a field that is wider than it is tall, you should prefer a vertical wall.) It’ll prevent really glaring biases in the finished product, and generally makes for more interesting mazes. However, for best results, if you’re bisecting a field that is taller than it is wide (like we are now), it’s best to bisect horizontally. Now, theoretically, we could bisect that either vertically or horizontally. Let’s go with the field on the right, first. Now, we repeat these steps on each of the two subfields that we created by adding that wall. Then, we randomly add a gap in the wall, so that we preserve the connectability of the graph:Īnd that finishes the first iteration. I’ll just close my eyes and point…here…so we’ll add a wall at x=3: (If there is too much hand-waving, call me on it in the comments! I’ll be more than happy to expand wherever things get too obtuse.)įirst, we’ll bisect it vertically, because I’m just that kind of a guy. We’re going to start with a larger grid this time, 5×5, just to show how the algorithm quickly converges. Let’s walk through an example to get an idea of how this works in practice. Each repetition of the algorithm simply increases the level of detail. You’ll find that at every step, you still have a valid maze. Continue, recursively, until the maze reaches the desired resolution.Repeat step #2 with the areas on either side of the wall.Bisect the field with a wall, either horizontally or vertically.This algorithm is particularly fascinating because of its fractal nature: you could theoretically continue the process indefinitely at progressively finer and finer levels of detail. The “recursive division” algorithm is one that must be implemented as a wall adder.
![recursive backtracking maze generator algorithm python recursive backtracking maze generator algorithm python](https://raw.githubusercontent.com/github/explore/0298b84058274525b41d0eed081bbeca316f7877/topics/maze/maze.png)
Some algorithms can be implemented a different way (and indeed, some must be implemented this way): as “wall adders”, where the process begins with a large empty space, and adds walls until a maze results. All of the maze algorithms I’ve covered so far ( recursive backtracking, Eller’s, Kruskal’s, and Prim’s) were implemented as “passage carvers”: they started with a solid grid and hollowed the passages out of it.