Title: Make mazes with topographic features in C#

The example Make and draw a maze in C# shows how to use a random spanning tree algorithm to make mazes. This example shows how to modify the algorithm to make mazes that have specific topographic features.

The previous example makes mazes by building a candidate list of links that it could add to the growing spanning tree. Then as long as that list isn't empty, the program picks a random link from it and adds it to the growing spanning tree.

This example doesn't select links form the candidate list with equal probability. Instead it selects random links with weighted probabilities. Different ways of assigning the weights give different topographic features.

The following code shows the changes to the MazeLink class.

// The method used to weight links. public enum Favor { None, Age, Horizontal, Vertical, ZigZag, Straight, } // The number of rounds that this link // has been in the candidate list. public int Age = 0; // The link's weight. public int Weight(Favor favor) { switch (favor) { case Favor.None: return 1; case Favor.Age: return Age * Age; case Favor.Horizontal: if (FromNode.Bounds.Top == ToNode.Bounds.Top) return 5; else return 1; case Favor.Vertical: if (FromNode.Bounds.Left == ToNode.Bounds.Left) return 5; else return 1; case Favor.ZigZag: { MazeNode from_pred = FromNode.Predecessor; if (from_pred == FromNode) return 1; bool is_horz = (FromNode.Bounds.Top == ToNode.Bounds.Top); bool pred_is_horz = (from_pred.Bounds.Top == FromNode.Bounds.Top); if (is_horz == pred_is_horz) return 1; else return 10; } case Favor.Straight: { MazeNode from_pred = FromNode.Predecessor; if (from_pred == FromNode) return 1; bool is_horz = (FromNode.Bounds.Top == ToNode.Bounds.Top); bool pred_is_horz = (from_pred.Bounds.Top == FromNode.Bounds.Top); if (is_horz != pred_is_horz) return 1; else return 10; } default: throw new InvalidEnumArgumentException(); } }

The Age field keeps track of the number of rounds the link has been in the candidate list.

The Weight method returns the weight that the main program should use for the link. The following table describes the weighting methods used by this program and shows example mazes.

Method	Effect	Example
None	All links have the same weight so the program selects them randomly. This gives the same result as the previous example.
Age	The program favors links that have been in the candidate list the longest. This gives the maze longer paths than a random maze.
Horizontal	The program favors horizontal links so the maze contains longer horizontal paths.
Vertical	The program favors vertical links so the maze contains longer horizontal paths.
ZigZag	The program prefers links with predecessor links that go in different directions. This gives the maze more walls that zigzag. A side effect of that is that the maze has more long diagonal paths.
Straight	The program prefers links with predecessor links that go in the same direction. This gives the maze longer paths.

The Straight option gives longer paths in general and in particular it often creates long paths from the root node. in this example the maze's upper left corner is the root node so there are often long paths that travel along the top and left edges of the maze. (See the picture at the top of the post.) Sometimes those paths run the entire width and height of the maze. You can reduce that effect if you use a location in the middle of the maze as the root node.

The main program uses the following code to select links with weighted probabilities.

// Pick a random link using a weighting. int total_weight = links.Sum(link => link.Weight(favor)); int selected_weight = rand.Next(0, total_weight + 1); int link_num = -1; for (int i = 0; i < links.Count; i++) { selected_weight -= links[i].Weight(favor); if (selected_weight <= 0) { link_num = i; break; } } MazeLink selected_link = links[link_num]; links.RemoveAt(link_num);

The code first uses the Sum extension method to add up the weights of the links in the candidate list. It uses the anonymous method link => link.Weight(favor) to get the link's weight. This anonymous method passes the link's Weight method the favor parameter to tell it which favoring method to use.

After is has calculated the total of the link weights, the code picks a random value between 0 and the total weight. It then loops through the links subtracting their weights from the selected value. When the selected weight is 0 or smaller, the program has reached the randomly selected link. It sets selected_link equal to that link and removes it from the candidate list.

Most of the rest of the program is similar to the previous example. One important difference is the addition of the following code, which occurs later in the loop that builds the spanning tree.

// Increase the candidates' ages. foreach (MazeLink link in links) link.Age++;

This code increments the ages of the links in the candidate list so the links can calculate their weights properly if we are favoring older links.

Try experimenting with the example. Try making new weighting methods. If you find interesting way to weight the links, email me and let me know.

Download the example to experiment with it and to see additional details.