Mazes For Programmers part 10, improving the Aldous-Broder algorithm to remove short dead-ends

This entry is part 10 of 11 in the series Mazes For Programmers

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.

Series Navigation<< Mazes For Programmers part 9, some statistics, and combining the Aldous-Broder and Wilson’s algorithmsMazes For Programmers part 11, Ruby vs C# speed tests >>

Be First to Comment

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.