Make mazes with topographic features in C#

[make mazes]

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. [make mazes]
Age The program favors links that have been in the candidate list the longest. This gives the maze longer paths than a random maze. [make mazes]
Horizontal The program favors horizontal links so the maze contains longer horizontal paths. [make mazes]
Vertical The program favors vertical links so the maze contains longer horizontal paths. [make mazes]
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. [make mazes]
Straight The program prefers links with predecessor links that go in the same direction. This gives the maze longer paths. [make mazes]

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.

Download the example to see additional details. Then experiment with it. Try making new weighting methods. If you find interesting way to weight the links, describe it in a comment below.


Download Example   Follow me on Twitter   RSS feed   Donate




About RodStephens

Rod Stephens is a software consultant and author who has written more than 30 books and 250 magazine articles covering C#, Visual Basic, Visual Basic for Applications, Delphi, and Java.
This entry was posted in algorithms, drawing, graphics, mathematics and tagged , , , , , , , , , , , , , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *