Mazes For Programmers part 8, a random walk with Wilson’s algorithm

• Tweet
• Email

• Tweet
• Email

This was my first real challenge. I converted his code for the Binary Tree and Sidewinder two algorithms, and Aldous-Broder turned out to be pretty straightforward to implement, so my code looked a lot like his.

However, Wilson’s algorithm was a different matter altogether. I had been reading the book at night, and didn’t have it by my side when I tackled this algorithm. I had read his description of the algorithm a few times, and it seemed easy enough. Ha, famous last words.

My first attempt was pretty rubbish. The algorithm didn’t terminate, and what it produced along the way was not very impressive. Unsure what had gone wrong, I re-read his description (whilst avoiding the code) and realised that I had mis-read it, and had got two small, but significant points wrong. I could go into a lengthy discourse about how important it is to understand your requirements, learn from your mistakes and so on, but as I never do this myself, I don’t feel justified in telling anyone else to do it!

Once I understood the algorithm correctly, I did a lot better. The code I produced was fairly clean, fairly different from his, and fairly in need of some rethinking…

public static Maze Create(int rows, int cols) {
  Maze maze = new Maze(rows, cols);
  Random r = new Random((int)DateTime.Now.Ticks);
  List<Cell> walk = new List<Cell>();
  // Pick a random cell to mark as visited. This will be the end point of our first walk
  Cell first = maze.Cells.Rand(r);
  bool[,] visited = new bool[rows, cols];
  visited[first.Row, first.Col] = true;
  // Pick a starting cell for our first walk
  Cell current = maze.Cells.Where(c => c.Row != first.Row && c.Col != first.Col).Rand(r);
  walk.Add(maze.Cells.First(c => c.Row == current.Row && c.Col == current.Col));
  while (visited.Cast<bool>().Any(cell => !cell)) {
    Cell next = walk.Last().Neighbours.Rand(r);
    if (visited[next.Row, next.Col]) {
      walk.Add(next);
      // Carve cells along the current walk
      walk.Zip(walk.Skip(1), (thisCell, nextCell) => (thisCell, nextCell)).ForEach(c => {
        c.thisCell.Link(c.nextCell);
        visited[c.thisCell.Row, c.thisCell.Col] = true;
        visited[c.nextCell.Row, c.nextCell.Col] = true;
      });
      walk.Last().Link(next);
      // Start a new walk from a random unvisited cell
      if (maze.Cells.Any(c => !visited[c.Row, c.Col])) {
        walk = new List<Cell> { maze.Cells.Where(c => !visited[c.Row, c.Col]).Rand(r) };
      }
    } else if (walk.Contains(next)) {
      // Mark all cells that we are about to snip as not visited
      walk.Skip(walk.IndexOf(next) + 1).ForEach(c => visited[c.Row, c.Col] = false);
      // Snip off all cells after the last time we visited this cell
      walk = walk.Take(walk.IndexOf(next) + 1).ToList();
    } else {
      walk.Add(next);
    }
  }
  return maze;
}

That’s quite a lot of code! The comments should explain what it does, and if you’ve read the book, you should understand the algorithm, so it shouldn’t need too much explanation. I’ll just pick out a few points that may be of slight interest.

Structure

The main difference between my code and his is that he used nested while loops to build the path, whereas I had one loop, and an if statement to decide what to do on each step. I’m not sure there is a huge difference between the two, but if I were to do this again, I would probably try his approach, as it is slightly clearer what is going on.

The array type

Another difference was that he maintained an array of cells, which started out containing all cells in the maze, and was reduced every time a cell was visited. His loop ended when this array was empty. I chose a slightly different path, and used an array of bools, as this is (ever so slightly) faster and easier to work with. For one thing, it didn’t need initialising, as a bool defaults to false, which is the initial state of the cells.

My first thought was to check if any cells were left to be visited by using (guess what…) a Linq method, such as Any. However, I discovered that you can’t use Linq on a multidimensional array. This seemed a shame, until I discovered that with a very small trick, you can use Linq. All you need to do is use the Cast() method…

visited.Cast<bool>()

…and you had access to all the usual Linq goodness.

Carving paths

His code for carving out a path looked like this…

0.upto(path.length-2) do |index| 
  path[index].link(path[index + 1]) 
  unvisited.delete(path[index]) 
end 

I took advantage of the Linq Zip function, which is not something I use regularly, but is extremely useful when I do. For those not familiar with it, it allows you to “zip up” two collections, hence the name. For example, if you had two List<int>s, you could pair them up as follows…

List<int> seq1 = new List<int> { 1, 2, 3, 4, 5 };
List<int> seq2 = new List<int> { 6, 7, 8, 9, 10, 11 };
var zip = seq1.Zip(seq2, (n1, n2) => (n1, n2));

This would produce a collection of tuples…

(1, 6)
(2, 7)
(3, 8)
(4, 9)
(5, 10)

Notice that the sequence emitted has the same length as the shorter of the two input sequences, as the method zips up pairs until it runs out. Any remaining items are discarded.

Obviously, this isn’t a very exciting example, but you get the point. The lambda inside Zip can do pretty much anything you want, such as multiplying the numbers, etc.

In my case, I wanted to pair each cell in the walk with the next one, so I had them together to call the Link() method. You can see the idea behind this with our numbers. If we only use seq1, but use it twice…

seq1.Zip(seq1.Skip(1), (n1, n2) => (n1, n2))

…we get each number paired with the one after it…

(1, 2)
(2, 3)
(3, 4)
(4, 5)

Applying this to the walk, we can zip up each cell with the one after it, then link them together…

walk.Zip(walk.Skip(1), (thisCell, nextCell) => (thisCell, nextCell)).ForEach(c => {
  c.thisCell.Link(c.nextCell);
  visited[c.thisCell.Row, c.thisCell.Col] = true;
});

Removing the unnecessary visited array

Once I had the code working, I began wondering if it could be cleaned up at all. One thing that bothered me was the visited array. This was used to mark which cells had been visited. However, a little consideration led me to realise that this wasn’t actually necessary. With one caveat (see below), you can identify a cell that has been visited by checking if it has any links. If it does, it has been visited. Therefore, we don’t need to maintain a separate array, we can just check the links.

The one place where this fails is on the very first walk. Our single “visited” cell (which hasn’t actually been visited, it was just picked at random when we started) does not yet have any links. Therefore, the above method would fail, and the algorithm would never finish its first walk. This turned out to be very easy to fix, I just checked if the next cell was the first cell, or had any links…

if (next == first || next.Links.Any()) {

Removing the visited array also meant that I had less work to do when carving a path, as I didn’t need to modify the array. I could now do the whole thing in one line…

walk
  .Zip(walk.Skip(1), (thisCell, nextCell) => (thisCell, nextCell))
  .ForEach(c => c.thisCell.Link(c.nextCell));

Once you get used to using Linq in this way, your code becomes much shorter and more concise. I split this down over three lines as this blog doesn’t handle long lines well, but in the code it’s all on one line, as opposed to four lines in the author’s code, two of which are really just noise. As I’ve said before, this isn’t a criticism of Ruby, it’s another example of how Linq makes coding so much more expressive.

The final version of the code looked as follows…

public static Maze Create(int rows, int cols) {
  Maze maze = new Maze(rows, cols);
  Random r = new Random((int)DateTime.Now.Ticks);
  List<Cell> walk = new List<Cell>();
  // Pick a random cell to mark as visited. This will be the end point of our first walk
  Cell first = maze.Cells.Rand(r);
  // Pick a starting cell for our first walk
  Cell current = maze.Cells.Where(c => c.Row != first.Row && c.Col != first.Col).Rand(r);
  walk.Add(maze.Cells.First(c => c.Row == current.Row && c.Col == current.Col));
  while (maze.Cells.Any(c => !c.Links.Any())) {
    Cell next = walk.Last().Neighbours.Rand(r);
    if (next == first || next.Links.Any()) {
      walk.Add(next);
      // Carve cells along the current walk
      walk.Zip(walk.Skip(1), (thisCell, nextCell) => (thisCell, nextCell))
        .ForEach(c => c.thisCell.Link(c.nextCell));
      // If there are any unvisited cells, start a new walk from a random one
      if (maze.Cells.Any(c => !c.Links.Any())) {
        walk = new List<Cell> { maze.Cells.Where(c => !c.Links.Any()).Rand(r) };
      }
    } else if (walk.Contains(next)) {
      // Snip off all cells after the last time we visited this cell
      walk = walk.Take(walk.IndexOf(next) + 1).ToList();
    } else {
      walk.Add(next);
    }
  }
  return maze;
}

This was easily the most challenging, and therefore interesting exercise so far in the book. A sample coloured maze looked like this…

Plotting the longest path showed some meandering behaviour that would keep someone busy for a while…