Title: Make and draw a maze in C#

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 to experiment with it and to see additional details.