Make and draw a maze in C#

[draw a maze]

This example shows how to generate and draw a maze. To create the maze, it uses a spanning tree algorithm.

A spanning tree is a tree that connects all of the nodes in a network. The following steps show the spanning tree algorithm works.

  1. Add any node to the tree. This node is the tree’s root. Add its links to a candidate list.
  2. While the candidate list is not empty, repeat:
    1. Pick a random link from the candidate list.
    2. Add that link’s destination node to the tree. Add the destination node’s links that lead to nodes that are not already in the spanning tree to the candidate list.
    3. Remove any links from the candidate list if they point to a node that is already in the tree.

To use the algorithm in this example to make and draw a maze, the program uses the MazeNode class to represent the squares in a rectangular grid. The following code shows the heart of the MazeNode class.

class MazeNode
{
    public const int North = 0;
    public const int South = North + 1;
    public const int East = South + 1;
    public const int West = East + 1;

    // The node's neighbors in order North, South, East, West.
    public MazeNode[] Neighbors = new MazeNode[4];

    // The predecessor in the spanning tree.
    public MazeNode Predecessor = null;

    // The node's bounds.
    public Rectangle Bounds;

    ...
}

The class’s Neighbors array holds references to other MazeNode objects that are adjacent to a particular node. For example, a maze square in the middle of the maze is adjacent to the squares north, south, east, and west of that square. The square in the maze’s upper left corner is adjacent only to squares to the south and east because the places where its other neighbors would be lie outside of the maze’s area.

The MazeNode class’s Predecessor field is a reference to the node that comes befroe this one in the spanning tree. You can follow Predecessor links to trace the tree back to its root.

The Bounds field gives the location in the maze represented by this node.

The MazeNode class includes drawing code. The program needs it to draw a maze but it’s reasonably straightforward and isn’t necessary for the maze creation algorithm so I won’t describe it here. Download the example to see the details.

The program uses the following MazeLink class to represent a link in the candidate list.

class MazeLink
{
    public MazeNode FromNode, ToNode;
    public MazeLink(MazeNode from_node, MazeNode to_node)
    {
        FromNode = from_node;
        ToNode = to_node;
    }
}

This class simply contains references to the link’s nodes and a constructor to make initializing a link easy.

The main program uses the following code to create and draw a maze.

private int Xmin, Ymin, CellWid, CellHgt;

private void btnCreate_Click(object sender, EventArgs e)
{
    // Figure out the drawing geometry.
    int wid = int.Parse(txtWidth.Text);
    int hgt = int.Parse(txtHeight.Text);

    CellWid = picMaze.ClientSize.Width / (wid + 2);
    CellHgt = picMaze.ClientSize.Height / (hgt + 2);
    if (CellWid > CellHgt) CellWid = CellHgt;
    else CellHgt = CellWid;
    Xmin = (picMaze.ClientSize.Width - wid * CellWid) / 2;
    Ymin = (picMaze.ClientSize.Height - hgt * CellHgt) / 2;

    // Build the maze nodes.
    MazeNode[,] nodes = MakeNodes(wid, hgt);

    // Build the spanning tree.
    FindSpanningTree(nodes[0, 0]);

    // Display the maze.
    DisplayMaze(nodes);
}

This code reads the width and height that the user wants the maze to have. It then calculates the width and height it needs to use for the maze cells to make the maze fit in the available area.

Next the code defines the nodes array and calls the MakeNodes method to initialize it. That code simply creates MazeNode objects for each of the node cells and sets their Neighbors entries. It’s straightforward so it’s not shown here. See the code for details.

The main program then calls the following FindSpanningTree method to implement the algorithms shown earlier.

// Build a spanning tree with the indicated root node.
private void FindSpanningTree(MazeNode root)
{
    Random rand = new Random();

    // Set the root node's predecessor so we know it's in the tree.
    root.Predecessor = root;

    // Make a list of candidate links.
    List<MazeLink> links = new List<MazeLink>();

    // Add the root's links to the links list.
    foreach (MazeNode neighbor in root.Neighbors)
    {
        if (neighbor != null)
            links.Add(new MazeLink(root, neighbor));
    }

    // Add the other nodes to the tree.
    while (links.Count > 0)
    {
        // Pick a random link.
        int link_num = rand.Next(0, links.Count);
        MazeLink link = links[link_num];
        links.RemoveAt(link_num);

        // Add this link to the tree.
        MazeNode to_node = link.ToNode;
        link.ToNode.Predecessor = link.FromNode;

        // Remove any links from the list that point
        // to nodes that are already in the tree.
        // (That will be the newly added node.)
        for (int i = links.Count - 1; i >= 0; i--)
        {
            if (links[i].ToNode.Predecessor != null)
                links.RemoveAt(i);
        }

        // Add to_node's links to the links list.
        foreach (MazeNode neighbor in to_node.Neighbors)
        {
            if ((neighbor != null) && (neighbor.Predecessor == null))
                links.Add(new MazeLink(to_node, neighbor));
        }
    }
}

The method sets the root node’s Predecessor to the root node. It then creates the candidate list and adds MazeLink objects to it to represent the links from the root node to its neighbors. The method then enters a loop that runs until the candidate list is empty.

Inside the loop, the method picks a random link in the candidate list and removes it from the list. Next the method sets the predecessor for the link’s end node equal to the link’s start node. In other words, if the link is A --> B, then the code sets B.Predecessor = A.

The method then loops through the candidate list and removes any link that ends at a node that is already in the spanning tree. It knows that a node is in the tree if its Predecessor field is not null.

Note that the code loops through the candidate list from the larger indexes to the smaller ones. That way if it removes a link from the list and indexes of the remaining links are not changed.

Finally, the code loops through the neighbors of the node that was just added to the spanning tree. If that node’s neighbor is not null and isn’t yet in the spanning tree, then the code adds a MazeLink to the candidate list to represent the link to that neighbor.

The last major piece of code in the example is the DisplayMaze method. That method loops through the MazeNode objects and makes them draw their adjacent maze walls. Basically a MazeNode object draws a wall along its edge if it doesn’t have a neighbor there (if the node is on the edge of the maze) or if it isn’t connected to its neighbor by a spanning tree link.

Download the example and look at the code for details.


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.

3 Responses to Make and draw a maze in C#

  1. Pingback: Make mazes with topographic features in C# - C# HelperC# Helper

  2. muszurkefal says:

    This is a very helpful guide, how to make random generated mazes. I used it to my home essay. This was the 1st source which helped me how to start my work at all.

    But: Uncle Bob would cry if he could see these meaningless comments above codes.
    Everyone knows how a constructor looks like, you don’t need to comment that, “this is a constructor”. 🙂
    Use comments, when it helps to understand the code. 🙂

    • RodStephens says:

      I’m going to push back a little about comments for two reasons. Ignore this if you want.

      First, you can roll your eyes if you like, but it doesn’t hurt you to read an obvious comment. But if you don’t understand something, it can really hurt you badly to not have thee comment there.

      For example, I worked on a project with about 25,000 lines of code. We transferred it to a code maintenance organization and they had the policy that “any comment that is not necessary must be removed.” So they removed a huge number of our comments. The problem is, something that may seem obvious now may not be obvious later. When they read our comments, they thought they were obvious because they were informative. Less than a year later, they couldn’t maintain the code because (as you guessed) they couldn’t understand the code without the comments. So they put them all back in.

      The second reason for obvious comments (and the real reason for commenting constructors) is so you can search the code to find the constructors. I’ve even seen code where constructors are scattered around a class so it’s hard to find them all. You can use various object hierarchy browsing tools, but searching is quick, easy, and doesn’t hurt you. (And I’m sure you know that comments do not add to the size of the compiled code so they really don’t cost you anything.)

      But feel free to not use those comments if you like.

Leave a Reply

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.