As a reminder, you can get the code here: GitHub - jeremybytes/mazes-for-programmers. I added some comments to the "Program.cs" file so that you can do some experimentation with different algorithms, grids, and grid sizes.
Biased Algorithms
The two algorithms previously implemented were Sidewinder and Binary Tree. These both have biases, meaning there are certain patterns that repeat based on the algorithm. For example, the binary tree algorithm tends to create a diagonal across the maze. This is visible with a 15x15 maze:
But it's even more obvious when we have a larger maze (155 x 155):
Another thing is that this produces a straight path along the top (north) edge of the maze as well as the right (east) edge of the maze.
Non-Biased Algorithms
Mazes for Programmers presents 2 non-biased algorithms. I've implemented one of them: the Aldous-Broder algorithm. This was independently developed by David Aldous and Andrei Broder. It uses a random walk to create a non-biased algorithm.
One of the important points for a maze algorithm is that is should not create loops, and this algorithm does ensure that while still creating random paths. Basically, it creates random paths until they link up. If a loop is created, then that path is discarded.
Here's the Ruby code from the book:
And here's my implementation in C#:
This produces a random path. Here's a text representation showing the shortest path from the center to the lower-left corner:
And here's a graphical representation showing a heat map of distances from the center:
What's interesting is that if we run this multiple times, we won't see a pattern forming (such as the diagonal pattern formed with the Binary Tree). Here are several runs with a larger grid:
This starts to look pretty interesting. Unfortunately, because of the random nature of the algorithm, it gets much slower the larger the grid, and I don't think there's an easy way to parallelize the process.
As a side note, the other non-biased algorithm presented in the book, Wilson's algorithm, uses a random walk as well, and it suffers from a similar performance issue. The difference is that while Aldous-Broder has slowness at the end (while it tries to hook up the last few cells), Wilson's has slowness at the front (where it tries to hook up the first cell). I haven't done any performance analysis, and I think that's outside the scope of my interest right now.
Accidental Art
Here's a 255 x 255 grid. This took several minutes to produce on my machine. But because it uses random numbers, the time to produce it is non-deterministic.
This is really cool. I think it's time for me to repurpose this and start creating interesting visual patterns. I could probably set up some color transitions in addition to the shade transitions of the heat map. I'll be playing with this quite a bit in the near future.
Wrap Up
I don't know how much further I'll get in the Mazes for Programmers book. I think I may have gotten the information I need regarding the algorithms and how things work. This is a good jumping off point for me to explore on my own.
I'll be playing with the heat map quite a bit. It's easy to remove the maze lines and just have the colors (I did that accidentally last night). And adding some color transitions would be pretty cool.
I also need to go through the F# code that Steve Gilham put together. It looks like I'll need to decompose things a bit to make it work with various display output (it does text right now, but I'd want to add the graphical display) as well as to support the distance calculations that make the paths and heat maps possible. So I've got lots to play with.
I've also got lots of real work to do as well. But it's also good to play and explore from time to time. That's part of the learning process.
Happy Coding!
For the benefit of the audience, the gist you've linked is the first in a series of three maze gists that deal with the biassed algorithms from the posts back in the spring.
ReplyDeleteThe biassed nature of those algorithms meant that they were well suited to working a row at a time, the binary tree maze from top to bottom, the sidewinder bottom to top, with cells being linked up within the rows in a single pass, everything nice and immutable. Even the sidewinder which had some right-to-left sections is just a matter of creating the individual runs and then concatenating them.
The Aldous-Broder and Wilson algorithms are going to be more interesting to achieve without resorting to mutable data structures, as paths can cross.
To make things more interesting, I'm working on the Hunt-and-Kill and Recursive Backtracker algorithms today. Recursive Backtracker uses a stack in the Ruby code. Both are slightly biased and should be a lot faster than the non-biased ones.
DeleteFun, huh?
If the bias in the sidewinder algorithm comes from always scanning the next line in the East direction, would it be compensated for by reversing the direction of the scan on alternating lines?
ReplyDelete