Title: Animate maze solving, version 3

The previous maze-solving examples Animate maze solving, version 1 and Animate maze solving, version 2 used a recursive method named Solve that returns an IEnumerable containing the paths that the program was searching.

Removing Recursion

To remove the recursion, think about what happens during recursion or any method call for that matter. Here's the structure of the Solve method.

private IEnumerable<List<MazeNode>> Solve( MazeNode end_node, List<MazeNode> path) { ... foreach (List<MazeNode> test_path in Solve(end_node, path)) yield return test_path; ... }

The method does a bunch of stuff and then uses a foreach loop to iterate over the paths returned by a recursive call to the Solve method. When the program makes that call, it saves the current call's position and local variables. It then calls the method again passing it the desired end node and the path that we need to examine with a new node added at the end.

To remove the recursion, we can imitate those steps. In order to animate the solution, we also need to save that kind of state information and then later restore it so we can continue execution at the animation's next step.

The Solve Method

Here's the new version of the Solve method.

private List<MazeNode> Path = null; private List<int> LastUsedNeighbor = null; // The final node in the Path list is the node we are visiting. // If LastUsedNeighbor has an entry for that node, then // we have visited some of its children. // See if we have a solution. // If not, try the last node's next neighbor. private void Solve() { // See if we have reached the end node. int last_node_index = Path.Count - 1; MazeNode last_node = Path[last_node_index]; if (last_node == EndNode) { FoundSolution = true; tmrStep.Enabled = false; return; } // See if the last node has any more neighbors we can visit. bool found_neighbor = false; int neighbor_index = LastUsedNeighbor[last_node_index]; MazeNode neighbor = null; for (; ; ) { // Try the next neighbor. neighbor_index++; // If we have checked all neighbors, break. if (neighbor_index >= last_node.Neighbors.Count) break; // See if this neighbor is not already in the current path. neighbor = last_node.Neighbors[neighbor_index]; if (!neighbor.InPath) { // Visit this neighbor. found_neighbor = true; LastUsedNeighbor[last_node_index] = neighbor_index; break; } } // See if we found a neighbor to visit. if (found_neighbor) { // Visit this neighbor. Path.Add(neighbor); LastUsedNeighbor.Add(-1); neighbor.InPath = true; } else { // We have visited all of the last node's neighbors. // Remove the last node from the Path list. last_node.InPath = false; Path.RemoveAt(last_node_index); LastUsedNeighbor.RemoveAt(last_node_index); } }

As before, the Path list stores the path we are currently exploring. The LastUsedNeighbor list holds the index of the last neighbor that we have considered for the last node in the path. When a "recursive" call returns, we use LastUsedNeighbor to decide which neighbor to explore next. If the current node has no more neighbors, then the "recursion" ends and control moves to the "calling method."

The Solve method first checks to see if we have reached the maze's destination node. If we have reached that node, the method sets FoundSolution to true, disables the tmrStep Timer, and returns.

If we have not yet found a solution, the method gets the index of the last neighbor visited. It then enters a loop to consider other neighbors of the current node. If the next possible neighbor index is greater than the current node's neighbor count, then the code breaks out of the loop having found no new neighbor to use.

If the next neighbor considered is not currently in the test path, the code sets found_neighbor to true to indicate that we should use that neighbor. It adds the neighbor index to the LastUsedNeighbor list, and breaks out of the loop.

When the loop ends, the method checks whether it found a new neighbor to try. If it did find a neighbor, the code adds it to the Path list. It also adds -1 to the LastUsedNeighbor list to indicate that the last neighbor of this node is -1. That makes the Solve method's loop starting looking for a new neighbor at index 0, which is this node's first neighbor.

When the loop ends, if the method did not find a new neighbor to explore, then it must "move up" the "recursive call stack." In that case, it removes the last node from the Path list because that node did not lead to a solution. It also removes the last entry from the LastUsedNeighbor list because we are done considering that node's neighbors.

Now each time this method is called, it performs one step in the search for a complete path.

Searching for a Solution

When the program needs to start finding a path through the maze, it executes the following StartSolving method.

// Start solving the maze. private void StartSolving() { // Remove any previous results. Path = new List<MazeNode>(); LastUsedNeighbor = new List<int>(); 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); LastUsedNeighbor.Add(-1); StartNode.InPath = true; // Solve. FoundSolution = false; tmrStep.Enabled = true; }

This method creates new, empty Path and LastUsedNeighbor lists and then defines the nodes' neighbors as usual. It then adds the start node to the Path list and adds -1 to the LastUsedNeighbor list. It sets the start node's InPath value to true, sets FoundSolution to false, and starts the tmrStep Timer.

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

// Take a step in solving the maze. private void tmrStep_Tick(object sender, EventArgs e) { Solve(); picMaze.Refresh(); }

This code calls the Solve method to take the next step searching for the solution. It then refreshes the picMaze PictureBox so its Paint event handler can display the current path.

Conclusion

This example uses a timer to animate maze solving. Instead of using recursion, it uses the Path and LastUsedNeighbor lists to keep track of where it is in the process of finding a path through the maze. You can always remove recursion from any program if you try hard enough. In the worst case, you can imitate the recursion as this example does.

The previous version of the program used an enumerator created by a recursive method. The process of returning an enumerator is a bit strange and recursion can also be confusing, but personally I like that solution. It's weird, but understandable once you figure out how to return enumerations.

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