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

• Tweet
• Email

• Tweet
• Email

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.