Title: Solve mazes in C#

This example shows how to solve mazes that were created by the example Make and draw a maze in C#. See that example for information about how to build a maze. Read the following sections to learn how to solve mazes.

MazeNode

The maze's spanning tree is drawn in pink in the picture on the right. The tree's root is the square in the maze's upper left corner, although you could use any node as the maze's root.

In the previous example, each node also had a Neighbors array that contains references to the nodes to its North, South, East, and West. For the current example, I've renamed this array AdjacentNodes because I want to use Neighbors to list the nodes that you can reach from a node. The Neighbors list holds the nodes in the AdjacentNodes array that are not blocked by a maze wall.

The only other new field on the MazeNode class is InPath, a Boolean that indicates whether the node is in the path that we are currently studying. You'll see how that works in the next section.

The following code snippet shows the fields defined by the MazeNode class.

public 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; // Nodes that are adjacent in order North, South, East, West. public MazeNode[] AdjacentNodes = new MazeNode[4]; // The predecessor in the spanning tree. public MazeNode Predecessor = null; // The node's bounds. public RectangleF Bounds; // True if the path contains this node. public bool InPath = false; // The nodes that you can reach from this node. public List<MazeNode> Neighbors = null; ... }

The MazeNode class's only new method is the following DefineNeighbors method.

// Define this node's neighbors. public void DefineNeighbors() { Neighbors = new List(); foreach (MazeNode adj in AdjacentNodes) { // See if we can reach the adjacent node from this one. if ((adj != null) && ((adj.Predecessor == this) || (adj == this.Predecessor))) { Neighbors.Add(adj); } } }

This method initializes the node's Neighbors list. Recall that the AdjacentNodes array holds references to the nodes to the North, South, East, and West of the current node. Note that some of those entries might be null if the node lies at the edge of the maze. Some of those

The DefineNeighbors method loops through the node's AdjacentNodes array. If an entry is not null, then the code must determine whether the path to that node is blocked by a wall. There is no wall if the spanning tree that generated the maze contains a link between the two nodes. That happens if either this node's Predecessor is the other node, or if the other node's Predecessor is this node. If the adjacent node meets those criteria, then the method adds it to the current node's Neighbors list.

Solving

After you generate a maze, you can click on it to pick start and end positions. The following code executes when you click on the maze.

private MazeNode StartNode = null, EndNode = null; private void picMaze_MouseClick(object sender, MouseEventArgs e) { // Find the node clicked. if (Nodes == null) return; if (e.Button == MouseButtons.Left) StartNode = FindNodeAt(e.Location); else if (e.Button == MouseButtons.Right) EndNode = FindNodeAt(e.Location); // See if we have both nodes. if ((StartNode != null) && (EndNode != null)) StartSolving(); picMaze.Refresh(); }

The StartNode and EndNode variables store the start and end nodes. When you click on the maze, the code uses the FindNodeAt method described next to find the nodes at the points where you clicked. If you click with the left mouse button, the program stores the node in the StartNode variable. Similarly if you right-click, the code saves the node in the EndNode variable.

After saving the clicked node, the program checks whether the start and end nodes are both defined. If both nodes are non-null, the code calls the StartSolving method to solve the maze.

FindNodeAt

Before I describe the StartSolving method, I want to show you the following FindNodeAt method.

// Return the node at a point. private MazeNode FindNodeAt(Point location) { if (location.X < Xmin) return null; if (location.Y < Ymin) return null; int row = (location.Y - Ymin) / CellHgt; if (row >= NumRows) return null; int col = (location.X - Xmin) / CellWid; if (col >= NumCols) return null; return Nodes[row, col]; }

The method first compares the point's X and Y coordinates to the maze's smallest X and Y coordinates. If the point lies to the left or above the maze, the method returns null.

Next the code subtracts the maze's smallest Y coordinate from the point's Y coordinate and divides by the height of a maze cell. All of these values are integers so the result is truncated to an integer that gives the point's row number in the maze. If the row number is greater than the maze's largest row, the method returns null.

The method then uses similar steps to find the point's column number.

Finally, if both the row and column lie within the maze, the method returns the node at that position in the Nodes array.

StartSolving

The algorithm that you use to solve mazes is relatively simple. You start at the start node. If that node is not the end node, you examine each of its neighbors in turn and recursively find a path from the neighbor to the end node.

To keep track of the path that it is currently exploring, the program uses the following Path variable.

private List Path = null;

The following StartSolving method begins the search for a solution.

// Start solving the maze. private void StartSolving() { // Remove any previous results. Path = new List<MazeNode>(); // Make the nodes define their neighbors. foreach (MazeNode node in Nodes) node.DefineNeighbors(); // Start at the start node. Path.Add(StartNode); StartNode.InPath = true; // Solve recursively. Solve(EndNode, Path); // Clear the InPath values. foreach (MazeNode node in Path) node.InPath = false; // Show the result. picMaze.Refresh(); }

This method creates a new Path list. It then loops through all of the maze's nodes calling their DefineNeighbors methods to use the maze's spanning tree to define the nodes' neighbors.

Next the code adds the start node to the Path list. It sets the start node's InPath value to true so we know that the node is in the path.

The method then calls the Solve method to solve the maze.

After is has found the path, the method loops through the nodes in the Path list and resets their InPath fields to false so they are ready the next time you want to solve the maze. The method finishes by refreshing the picMaze PictureBox to show the result.

The following code shows the Solve method that the program uses to actually solve mazes.

private bool Solve(MazeNode end_node, List<MazeNode> path) { // See if we have reached the end node. MazeNode last_node = path[path.Count - 1]; if (last_node == end_node) return true; // Try each of the last node's children in turn. foreach (MazeNode neighbor in last_node.Neighbors) { if (!neighbor.InPath) { path.Add(neighbor); neighbor.InPath = true; if (Solve(end_node, path)) return true; neighbor.InPath = false; path.RemoveAt(path.Count - 1); } } return false; }

This method takes as parameters the desired end node and a list holding the nodes that are in the current test path.

The method first checks the last node on the path list to see if it has reached the desired end node. If the path reaches the end node, the method returns true to indicate that it has found a solution.

Next the code loops through the neighbors of the path's final node. If a neighbor's InPath field indicates that it is not already in the path, the code adds it to the end of the path. It then calls the Solve method recursively to see if the new path leads to a solution.

If the recursive call to Solve returns true, that means the path does lead to a solution. In that case the method leaves the path list unchanged and returns true so the calling method higher up the call stack knows that we found a solution. The recursive calls unwind until they reach the top and control returns to the StartSolving method that started the search.

If the recursive call to Solve returns false, that means the current path does not lead to a solution. For example, suppose the path up to this point was A → B → … → M. As we loop through the Neighbors list, we tried adding node N to the path, but the recursive call to Solve did not find a solution. In that case we reset node N's InPath value so we know that it is no longer in the path and remove it from the end of the path. We then continue the loop to try other node M neighbors.

If the method finishes trying all of node M's neighbors and cannot find a solution, the code returns false to indicate that there is no solution using the path A → M.

InPath

There are two interesting questions you can ask about the InPath field.

The first question about InPath is, "Why do we need InPath?"

That value lets the program know if a node is already in the path. If it is, we don't want to add it to the path again.

Because this program creates its maze by using a spanning tree (see the earlier example), there can be no paths that contain loops. That means we don't need to worry about the end of the current path leading into the path's middle. The only reason we need the InPath field is to prevent the path from doubling back on itself. For example, when we extend the path A → B → C, one of node C's neighbors that we will consider is node B. The InPath value prevents us from trying to add node B to the path again.

We could remove the InPath field if we keep track of the node that we just came from so we can avoid doubling back. You can make that change if you like. I think the version used here is a little (but only a little) less confusing. It's also in keeping with other network search algorithms where loops might be an issue.

The second question about InPath is, "Do we need to reset InPath to false when we remove a node from the path?"

Because all of the allowed moves through the maze lie on a spanning tree, we do not need to reconsider a node after it has been removed from the test path. If a node could not lead to a solution the first time we visit it, then it won't lead to a solution if we visit it again later. In fact, because of the maze's structure, we will not visit that node again. We would only visit a node again if we approached it from a different direction, and that would mean there was a loop in the maze.

All of that means we don't really need to reset the InPath values to false. I do it anyway for two reasons. First, that prepares the nodes in case you left- or right-click again to find a new path through the maze. In that case we need the InPath values to be false so we can begin the new search.

The second reason why I reset the InPath values is because it seems less sloppy and it fits with other path algorithms.

Drawing the Solution

When you click the Create button, the program creates the maze. It then draws it on a bitmap and displays that bitmap on the picMaze PictureBox. Once the PictureBox has a background image, it can display that whenever it needs to redraw.

When you left- and right-click on the maze to define the start and end points, the program saves those points and refreshes the PictureBox to execute the following Paint event handler.

private void picMaze_Paint(object sender, PaintEventArgs e) { e.Graphics.SmoothingMode = SmoothingMode.AntiAlias; if (StartNode != null) StartNode.DrawCenter(e.Graphics, Brushes.Red); if (EndNode != null) EndNode.DrawCenter(e.Graphics, Brushes.Green); if ((Path != null) && (Path.Count > 1)) { List<PointF> points = new List<PointF>(); foreach (MazeNode node in Path) points.Add(node.Center); e.Graphics.DrawLines(Pens.Red, points.ToArray()); } }

When the PictureBox needs to redraw itself, it starts with its background image, which shows the maze. The Paint event handler then draws on that image. Because the result starts with the background image, it is important that the Paint event handler not clear its Graphics object. If it calls e.Graphics.Clear, then the method will erase the maze.

The event handler sets the Graphics object's SmoothingMode and then draws the start and ends nodes if they are defined.

Then if the Path list holds a path, the code creates a new list of points. It loops through the nodes on the path and adds their centers to that list. The code then draws lines connecting the points in the list.

Conclusion

This method for solving mazes is fast and relatively straightforward. It starts at the start point. At each point it recursively tries moving to the neighbors at the end of the current path to see if they can produce a solution.

You can use this algorithm to solve mazes. It is also similar to some of the algorithms that you use to find paths and shortest paths through a network.

You might also think about how you could make the program display the test paths as it considers them. I'll post an example that does that when I have a chance. (And get an example working.😉)

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