Mazes For Programmers part 4, implementing the first two algorithms

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

Although in my previous post I described how I implemented the graphical UI, this of course was pretty useless without an algorithm to generate the mazes themselves. In this psot I’ll take a step back and look at my implementations of the first two algorithms he showed, Binary Tree and SideWinder.

On thing that puzzled me a little was that he first created an uncarved maze (ie without any doors), and then passed this to the algorithm-specific code to carve out doors. From an OO point of view, this seemed wrong to me, as the calling code should not need to know that there is such a thing as an uncarved maze. It should just pass in the number of cells in the horizontal and vertical directions, and have the algorithm-specific code create the uncarved maze behind the scenes. I’m not suggesting the author was wrong, just that this seemed a more natural use of OO to me.

So, my algorithm factory methods took two parameters, the number of cells in the horizontal and vertical directions, and returned a carved maze.

Binary tree

The code for the binary tree algorithm looked like this…

  public static class BinaryTree {
    public static Maze Create(int rows, int cols) {
      Maze maze = new Maze(rows, cols);
      Random r = new Random((int)DateTime.Now.Ticks);
      maze.Cells.ForEach(c => {
        List<Cell> neighbours = new List<Cell> { c.North, c.East }.Where(c1 => c1 != null).ToList();
        if (neighbours.Count == 1) {
          c.Link(neighbours.Single());
        } else if (neighbours.Count == 2) {
          c.Link(neighbours.Skip(r.Next(100) > 50 ? 0 : 1).First());
        }
      });
      return maze;
    }
  }

In many respects, this is very similar to his code. Line 6 made use of Linq to get a collection of the north and east neighbouring cells in one line. In this case it wasn’t that much cleaner than his code, but in other places where I wanted more neighbours, it made the code cleaner.

Lines 7-11 were done as an if statement, simply because the code is easier to read. I found that it wasn’t immediately obvious what his code was doing, which is why I did it differently. I experimented with a single line of Linq, which was certainly shorter, but as sometimes happens, shorter isn’t necessarily clearer, so I left it as it is.

The bit inside the Skip() method on line 10 decides whether we take the first or second item in the collection, Remember that for this algorithm, we are only interested in north and east neighbours, so we will only ever have zero (if we are in the north-east cell), one (if we are on the northern or eastern boundary) or two (anywhere else) items in the collection. Therefore, we either take the first item (ie don’t skip) or the second (skip one item).

One of his suggestions for further investigation was to see how the algorithm could be modified to bias it towards longer horizontal or vertical runs. The number 50 on line 10 is what influences that bias. I found that using r.Next(100) and comparing the result against 50 gave a more random-looking (if there is such a thing) selection than using a smaller number. By increasing the 50, we get longer horizontal corridors. If we use a number less than 50, we get longer vertical corridors.

SideWinder

My implementation of the SideWinder agorithm contained a few (dare I say it) improvements on his code…

  public static class Sidewinder {
    public static Maze Create(int rows, int cols) {
      Maze maze = new Maze(rows, cols);
      Random r = new Random((int)DateTime.Now.Ticks);
      List<Cell> run = new List<Cell>();
      maze.Cells.ForEach(c => {
        if (c.WesternBoundary) {
          run = new List<Cell>();
        }
        run.Add(c);
        if (c.EasternBoundary || !c.NorthernBoundary && r.Next(100) > 50) {
          Cell cr = run.Rand();
          if (!cr.NorthernBoundary) {
            cr.Link(cr.North);
          }
          run.Clear();
        } else {
          c.Link(c.East);
        }
      });
      return maze;
    }
  }

As mentioned in part 2 of this series, I added some convenience properties to detect if a cell is on a boundary. This is much neater than checking if the next cell if null, even if that is what is actually happening behind the scenes. Due to that, I was able to clean up the code where he checked if he should close the run…

  if (c.EasternBoundary || !c.NorthernBoundary && r.Next(100) > 50) {

I think this reads much more cleanly than his code.

Also, I added a Cells property, that enumerates all the cells in the maze. By using the WesternBoundary property, I was able to use just one ForEach construct, instead of a nested for loop. This is probably personal choice, but having a love of functional programming, I don’t like seeing for loops in my code.

There are still a few improvements I could do to these classes, but I’m not sure it’s worth it. There comes a point when more is less.

Series Navigation<< Mazes For Programmers part 3, graphical UIMazes For Programmers part 5, Dijkstra’s algorithm >>

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.