Title: Animate maze solving, version 2

My earlier post Animate maze solving, version 1 uses a method that returns an enumeration to show the steps used to find a path through a maze. That method works but it uses a loop that includes calls to Thread.Sleep and Application.DoEvents.

That technique works, but it's inelegant and can sometimes interfere with the normal operation of the event loop. For instance, the previous example needed to provide a special way to break out of the loop if the user tried to close the form. If the code did not do that, then the program could remain in a sort of zombie mode where the form has disappeared but the code was still running.

This post describes an improved solution.

Approach

Making a method return an enumeration is a clever way to return results from inside a sequence of recursive calls and then resume those calls later, and its still worth using that technique. The problem with the previous example was that it looped through the enumeration in a foreach loop. That made it awkward to process events within the loop and to leave the loop early.

This example's approach takes advantage of a useful but often overlooked fact about enumerations: they have enumerators. An enumerator is an object that keeps track of the position within an enumeration. A foreach loop uses an enumerator to loop through the values.

The new example keeps its own reference to an enumerator and uses it to move through the values when a timer fires. Because the program uses a timer, it doesn't need to sleep and use Application.DoEvents to process pending events. That's basically what the normal event loop does while the program is waiting for the timer to fire.

Code

The new example's Solve method is the same as before. It still recursively searches for a path through the maze, uses yield return to return paths, and uses yield break to break out of the recursion when it has found a solution.

The following code shows the new version of the StartSolving method.

IEnumerator<List<MazeNode>> PathEnumerator = null; // Start solving the maze. private void StartSolving() { // 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; // Create the IEnumerable to generate paths. FoundSolution = false; IEnumerable<List<MazeNode>> enumerable = Solve(EndNode, Path); // Get the enumerable's enumerator. PathEnumerator = enumerable.GetEnumerator(); // Start the timer. tmrStep.Enabled = true; }

This new version builds a maze network and adds the start node to the Path list as before. It then calls the Solve method and saves its IEnumerable result in variable enumerable.

Note that the Solve method does not actually do anything at this point. In fact the Solve method is not even invoked.

After setting the enumerable variable, the program calls its GetEnumerator method to get an enumerator object. Again, the Solve method doesn't do anything at this point. The enumerator has not requested a value so Solve has not produced one yet.

The StartSolving method enables its timer and ends.

When the timer fires, the following Tick event handler executes.

// Get and display the next path. private void tmrStep_Tick(object sender, EventArgs e) { PathEnumerator.MoveNext(); Path = PathEnumerator.Current; picMaze.Refresh(); }

This code calls the enumerator's MoveNext method to generate the next value in the enumeration. This is where the Solve method springs into action. It executes until it produces a result and returns it with the yield return statement. At that point, the Solve method is suspended and control returns to the Tick event handler.

The event handler uses the enumerator's Current property to get the enumeration's current value and refreshes the program's PictureBox to show the current path.

Each time the Tick event occurs, the program uses the enumerator to get the next path in the enumeration and displays it.

The new example doesn't need a clever way to break out of a foreach loop because it does not use such a loop. It still needs the FoundSolution variable so it can climb out of the recursive calls to the Solve method.

If you create a new maze or click the maze to define the start or end point, the program disables its timer so it stops the previous search. If you close the form, the normal event loop is smart enough to stop waiting for the timer, so the program ends normally.

If you define new start and end points to begin a new search, the new call to StartSolving creates a new enumerator and the whole things starts over.

Summary

Using an enumeration with yield return and yield break in this way is still confusing, but it's a lot less confusing than the previous version. (At least in my humble opinion.)

The remaining complexity comes from the recursion. The yield statements provide a sneaky trick for temporarily leaving the recursion, but that's still the most complicated part. In my final post on this topic, I'll show how you can eliminate the recursion entirely so you don't need to use yield. I'm not sure it's less confusing or in any way better than this version, but it does emphasize that you can remove recursion if you really want to.

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