page 1  (18 pages)
2to next section

Studies of Recursion: Fractals and Mazes 405

bool traverse_maze( );
// Precondition: The user of the program is facing an unblocked spot in the // maze, and this spot has not previously been visited by the user. // Postcondition: The function has asked a series of queries and provided // various directions to the user. The queries and directions have led the // user through the maze and back to the exact same position that the // user started at. The return value of the function is a true/false value // indicating whether the user found a magic tapestry in the maze.

Figure 9.6 shows a drawing of what the maze might look like, along with a sample dialogue. A sample dialog written at this point?before we?ve written the function?is called a script, and it can help clarify a loose specification. As you might suspect, Jervis?s actual maze is rather more complex than this sample dialog might suggest, but simplicity often results in the best scripts.

A Sample Dialogue

Step forward & write your name on the ground. Have you found the tapestry? [Yes or No] NoPlease turn left 90 degrees.
Are you facing a wall? [Yes or No] NoIs your name written ahead of you? [Yes or No] NoStep forward & write your name on the ground. Have you found the tapestry? [Yes or No] NoPlease turn left 90 degrees.
Are you facing a wall? [Yes or No] Yes
Please turn right 90 degrees.
Are you facing a wall? [Yes or No] NoIs your name written ahead of you? [Yes or No] NoStep forward & write your name on the ground. Have you found the tapestry? [Yes or No] Yes
Pick up the tapestry, and take a step backward. Please turn right 90 degrees.
Please turn right 90 degrees.
Please step forward, then turn 180 degrees. Please turn right 90 degrees.
Please turn right 90 degrees.
Please turn right 90 degrees.
Please step forward, then turn 180 degrees.

FIGURE 9.6 Script for the Maze Traversal Function

This dialogue supposes that the
user starts at the entrance to the
maze drawn below. The starting
point of the user is represented by
the arrow in a circle, with the
arrow pointing in the direction that
the user is facing. The large X is
the magic tapestry.

cpp09.frm Page 405 Wednesday, October 30, 1996 6:41 PM