More Maze Programming: Adding Some Bias for Longer Paths

Okay, so I know that I said I might be done with Mazes for Programmers, But, I went one chapter further and picked up a couple of more algorithms: Hunt and Kill, and Recursive Backtracker.

As a reminder, you can pick up the code here: GItHub - jeremybytes/mazes-for-programmers.

The reason these are interesting is that they add a bit of bias. Last time, we saw an unbiased algorithm that is completely random. This was better than the very biased algorithms that we had seen previously, but it was also a bit slow since it relies on random walks to fill an entire grid.

This works great, but good mazes are more than random events. So by adding a bit of bias, we can make longer paths, twistier paths, and fewer dead-ends. This makes a maze more interesting to solve.

Hunt and Kill
The first slightly-biased algorithm is Hunt and Kill. This scans the cells from the top left corner. When it finds a cell that has "unvisited neighbors" (meaning there are no links to the cell), then it makes a random connection and moves to the next cell. When it can't go any further (such as when it loops into a dead end), it goes back to scanning to find a cell with unvisited neighbors so that it can start again.

Because this is not completely random, it is much faster than the Aldous-Broder algorithm that we saw last time. And it creates some longer passages. Here's a graphical version:

And here's a text version:

It's particularly easy to spot the longer passage here when we look at the path from the center to the lower right corner.

It also makes nice patterns for larger mazes:

I find myself getting lost in some of the images. The dark areas represent the spots furthest from the center. So the top image has lots of things "furthest" away. The bottom image has a few things "furthest" away.

Recursive Backtracker
The other slightly-biased algorithm is the Recursive Backtracker. Like Hunt and Kill, this creates longer passages with fewer dead ends. But it operates a bit differently. When it hits a dead end, it doesn't start scanning for a new starting point (like Hunt and Kill). Instead, it keeps track of all the cells that have been visited by using a stack. If it comes to a dead end, it pops cells off the stack until it finds one that has an unvisited neighbor (meaning, another path to be started). When all of the cells are popped off the stack, that means we've visited each cell and we're done.

Here's the graphical version of Recursive Backtracker on a small grid:

And here's the text version:

Again, we can see a pretty long, twisty path from the center to the corner. And this is just as interesting when we create larger mazes:

I kind of like these because you'll find these twisty paths of one color running through the middle of a section with a lighter or darker color.

Differences
In addition to the slightly different patterns that come out of these algorithms, there are a few performance differences. I've noticed that the Hunt and Kill takes a little bit longer to complete. The Recursive Backtracker is a little bit faster, but it consumes more memory since it's keeping track of every single cell on the stack. Each of these has pros and cons, and if you're interested, pick up your own copy of Mazes for Programmers (Amazon link).

What's Next
As you can see, I've switched up the colors a little for these samples. But this is done by changing values in the code. Now that I'm seeing the interesting patterns that are created by these, I'm going to explore adding some more interesting color elements as well.

I've always been intrigued by pseudo-randomly created pictures. I can see that I'm going to be running quite a few of these in the future.

As always, keep playing and keep exploring.

Happy Coding!