- Mazes For Programmers part 1, introduction
- Mazes For Programmers part 2, some basics
- Mazes For Programmers part 3, graphical UI
- Mazes For Programmers part 4, implementing the first two algorithms
- Mazes For Programmers part 5, Dijkstra’s algorithm
- Mazes For Programmers part 6, paths through the mazes
- Mazes For Programmers part 7, the Aldous-Broder algorithm, and when random is not very random
- Mazes For Programmers part 8, a random walk with Wilson’s algorithm
- Mazes For Programmers part 9, some statistics, and combining the Aldous-Broder and Wilson’s algorithms
- Mazes For Programmers part 10, improving the Aldous-Broder algorithm to remove short dead-ends
- Mazes For Programmers part 11, Ruby vs C# speed tests
- Source code on GitHub
One of the idea he had for modifying the Aldous-Broder algorithm was to force it to pick an unvisited neighbour, if one exists. I think the idea was to cut down on the number of very short dead ends that the basic algorithm produces. If you look at the following sample, you can see that there are a lot of places in the maze where there are many short walls, making it pretty obvious which way to go…
The plain algorithm picks a random cell from the current cell’s neighbours…
Cell next = current.Neighbours.Rand(r);
It was pretty easy to change this so that it would always pick an unvisited cell if there were any…
Cell next = current.Neighbours.Any(c => c.Links.Count == 0) ? current.Neighbours.Where(c => c.Links.Count == 0).Rand(r) : current.Neighbours.Rand(r);
With a little thought, I could probably change the
Where clause to include both cases, but it didn’t seem worth it at the time.
Anyway, this simple change produced a marked difference in the quality of the mazes. Apart from having significantly less short walls, the longest paths were much longer, making the maze more challenging…
The difference becomes significantly more noticeable on larger mazes.
He also suggested weighting the decision, so instead of going from one extreme of picking the next cell completely at random to the other extreme of never picking a visited cell if possible, it could be done so that it would force an unvisited cell based on a random number. For example, the
Where clause could be changed as follows…
Cell next = current.Neighbours.Any(c => r.Next(1000) < 250 && c.Links.Count == 0)
…giving a 25% chance of forcing.
A larger % value would produce mazes with a mixture of longer dead end paths and shorter walls, but as I preferred the mazes with the previous version (effectively using 100%), I decided to stick with it and didn’t use this code.