Title: Animate maze solving, version 1

The post Solve mazes in C# solves mazes very quickly, but it only shows you the final path from the start point to the end point. It might be nice to make a program to animate maze solving so you can see the paths that it tries before it finds the final solution.

To use the program, enter the maze's width and height, and then click Create. After you create the maze, left click to set the start point and right click to set the end point. After you select the start and end points, the program searches for a solution while displaying the paths that it considers.

Approaches

One approach would be to save all of the paths that the program tries in some sort of list. Then the program could use a timer to loop through the saved paths and display them. Unfortunately the list of paths could be quite long. For example, in order to solve the maze shown at the top of this post, the program examined 723 paths. That's still a manageable number, but for larger mazes the program would use a lot of memory to store the paths.

One of the bigger problems with displaying paths as they are found is that the program uses recursion to find them. To display the paths, the program would need to pause while inside a possibly deep recursive search, display the current path, and then resume the recursive execution. This post and the next two show different approaches to displaying paths while searching for them.

This post uses a trick that allows a method to return an enumeration. That lets the method return a result to the calling method and then resume execution.

Code

After you select the maze's start and end points, the program executes the following StartSolving method to search for a solution.

private int NumPaths = 0; private bool FoundSolution = false; private List<MazeNode> Path = null; // Start solving the maze. private void StartSolving() { NumPaths = 0; // Remove any previous results. Path = new List<MazeNode>(); foreach (MazeNode node in Nodes) node.InPath = false; // 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. FoundSolution = false; Running = true; foreach (List<MazeNode> test_path in Solve(EndNode, Path)) { NumPaths++; Path = test_path; picMaze.Refresh(); Thread.Sleep(Interval); Application.DoEvents(); if (!Running) break; } Running = false; // Show the result. picMaze.Refresh(); Console.WriteLine("Examined " + NumPaths.ToString() + " paths."); }

This method clears any previous path and builds the maze network. It sets FoundSolution to false to indicate that the program has not yet found a solution. It also sets Running to true to indicate that the program is still running. You'll see how those variables are used shortly.

The most interesting part of the method is its foreach loop. That loop makes the program loop over the values returned by the Solve method described shortly.

For each path returned by the Solve method, the code sets variable Path equal to the latest test path. It then refreshes the picMaze PictureBox control to show the current path. (Download the example to see how it draws the path.)

The method then calls Thread.Sleep to pause the program so you can see the path. After the program wakes up, the program calls Application.DoEvents so it can process any pending events. In particular that allows the program to notice if you create a new maze, click to set new start or end points, or close the program.

If the Running variable is false, then you have stopped the program. In that case, the StartSolving method breaks out of its loop so the method ends.

If you press the Create button, click to set new start or end points, or close the program, the program calls the following StopRunning method.

// Stop running. private void StopRunning() { Running = false; }

This code simply sets Running to false to tell the StartSolving method to break out of its loop.

One particularly interesting time when the program calls StopRunning is when you try to close the program's form. When you do that, the Form1_FormClosing event handler calls StopRunning. If you don't do that, then the program knows that it should close but it continues executing its search. The form disappears but its code keeps running. Comment out the call to StopRunning in the Form1_FormClosing event handler to see this strange affect.

The example's final interesting new piece of code is the following Solve method. You may recall that this method returns an enumeration of test paths that the StartSolving method uses in its foreach loop.

private IEnumerable<List<MazeNode>> Solve( MazeNode end_node, List<MazeNode> path) { // Yield this path. yield return path; // See if we have reached the end node. MazeNode last_node = path[path.Count - 1]; if (last_node == end_node) { FoundSolution = true; yield break; } // 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; foreach (List<MazeNode> test_path in Solve(end_node, path)) yield return test_path; if (FoundSolution) yield break; neighbor.InPath = false; path.RemoveAt(path.Count - 1); // Redraw the path without this latest node. yield return path; } } }

This method uses a neat little trick that allows a method to return the items in an enumeration one at a time. Notice that it is declared to return an IEnumerable of lists of MazeNode objects. Each item in the enumeration is a list of nodes that represents a test path.

The method takes as a parameter the path that it should examine. The method returns that path and then explores the paths leading out of the end of that path.

The code starts by using a yield return statement to return the initial path. The yield return statement pauses the Solve method and returns control to the calling method. The calling method might be another call to Solve.

If you look a bit farther along in the Solve method's code, you'll see where the method calls itself. When it does, it loops through the values returned by the recursive call and uses yield return to return them higher up the recursive call stack.

The recursive calls use yield return to pass values up the call stack until they reach the StartSolving method, and that method displays the current path.

At that point, control returns to the Solve method that first called yield return and the method resumes.

After the yield return statement, the Solve method checks to see if it has found the maze's end point. If it has, then the code sets FoundSolution to true. It then calls yield break to end its enumeration and return control to the calling method.

After checking to see if it has found a complete path, the method loops through the neighbors of the current path's last node. For each of those neighbors, the code checks the neighbor's InPath value to see if the node is already in the path. (That happens if the neighbor is the current path's second-to-last node. This check prevents the path from doubling back on itself.) If the node is not in the path, the method tries adding the neighbor to the path.

The code adds the neighbor to the current path list and sets the neighbor's InPath value to true. The method then recursively calls itself and loops through the paths that the recursive call returns. It calls yield return to return each of the paths returned by the recursive call.

After it finishes examining paths via the neighboring nodes, the method checks the FoundSolution variable to see if a solution has been found. If a path has been found, the method calls yield break to finish end enumeration. Note that in this case the method does not remove the current neighbor from the path so the path returned to the calling method includes that neighbor. In fact, the recursive calls that this instance of the method made may have left many other nodes added to the end of the initial path.

If the program has not yet found a complete path, the code sets the current neighbor's InPath value to false to remove the node from the path. The code also removes that node from the end of the Path list.

Finally the method calls yield return to return the original path without the neighbor added at the end. That makes the program display the initial path, then display paths that extend the initial path via neighbor nodes, and finally backtrack to the initial path.

Summary

I know this is a bit confusing, so here's a summary. The Solve method is declared to return an IEnumerable<List<MazeNode>>. The method can then use yield return to return items for the enumeration.

The StartSolving method loops through the paths returned by the enumeration. That method could break out of its loop at any time, although in this example it does not.

When it calls itself recursively, the Solve method loops through the paths returned by the recursive call and uses yield return to return them. That adds them to its own enumeration.

When the method finds a path from the start point to the end point, it uses yield break to end its enumeration. It uses the variable FoundSolution to tell instances of the method farther up the call stack that the solution has been found so they know to end their enumerations.

There are a few key steps inside the StartSolving method's foreach loop. Each time through the loop, the method displays the current path, sleeps for a while, calls Application.DoEvents, and then checks Running to see if it should break out of the loop early. That allows the program to stop the search if you click on the maze, click Create, or close the form.

My next few posts show other ways to manage the trick of displaying paths while continuing a recursive search for a solution path.

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