Mazes For Programmers part 7, the Aldous-Broder algorithm, and when random is not very random

• Tweet
• Email

• Tweet
• Email

As mentioned in the previous post in this series, I decided not to convert his Ruby code into C#, but rather to read his description of the algorithm, then try and write my own code. This way I am forced to understand the algorithm, which is far more productive than simply copying out someone else’s code without really knowing what it does.

I had actually seen his code for Aldous-Broder, so had a basic idea of how he went about it, but hadn’t looked at it very closely, so was mainly writing it myself. The end result was actually very similar to his.

One thing I discovered when running it was that my mazes were anything other than non-biased. Pretty much every maze I generated had an empty corridor right across the top row, leading me to realise that I had done something wrong. Furthermore, every now and then, the algorithm would run for a very long time, only linking cells every now and then.

I realised that I had hit on a basic issue with random numbers, and that is that computer-generated random numbers are anything other than random. They are a stream of random-looking numbers, which mainly depend on the first number to determine what comes next. You can see this by seeding the random generator with a fixed number, and repeatedly producing a stream of numbers…

Random r = new Random(0);
for (int i = 0; i < 40; i++) {
  Console.WriteLine(r.Next());
}

You’ll find that this produces the same sequence of numbers every time, showing quite clearly that the sequence is not random. This is not a failing of the .NET implementation ether, this is something you’ll see with most random-number generators. There are complex, boring reasons for this, but this blog post is not the place to go into them.

Under normal circumstances, this isn’t usually a problem, as you create a Random object and reuse it for your sequence. If you don’t pass a seed, it will use some pseudo-random seed, such as the current number of ticks.

A common requirement in generating mazes is to pick a random element from an array of cells. The author took advantage of Ruby’s built-in sample function to do this. As .NET doesn’t have such a function (as far as I know anyway), I wrote my own…

    public static T Rand<T>(this IEnumerable<T> items) =>
      items.Skip(new Random().Next(1000) % items.Count()).First();

This skips a random number of elements, then takes the next one.

The significant flaw with this method is that it creates a new Random object each time you call it. When you aren’t using it that much, then this isn’t such a problem, but when you call it repeatedly very quickly, then the Random objects it creates are seeded with the same value, leading to a sequence that is about as non-random as you can get! Try running the following code to see what I mean…

for (int i = 0; i < 40; i++) {
  Console.WriteLine(new Random((int)DateTime.Now.Ticks).Next());
}

Odds on that you’ll get the same number 40 times!

Once I realised this, it was easy to change the Rand() method to take a Random object as a parameter and use that, only creating a new one if we didn’t pass anything in. This means that when an algorithm is going to need a lot of these quickly, we can create one Random object and reuse it in every call. The modified method looked like this…

    public static T Rand<T>(this IEnumerable<T> items, Random r = null) =>
      items.Skip((r ?? new Random()).Next(1000) % items.Count()).First();

As my maze-generating algorithms all had a Random object knocking around, it was easy to pass this in as needed…

Cell cr = run.Rand(r);

With the modified version of the method, my Aldous-Broder mazes looked nice and non-biased.