Project 3: A Maze of Twisty Little Passages

In the classic Adventure game of Crowther and Woods, there is a maze in which all rooms look identical. Further, exiting one room to the north gives no assurance that you enter the next room from the south. The trick to exploring the maze is dropping items, so that you can tell when you return to a room.

In this project, we'll investigate algorithms for navigating such mazes with a limited number of items you can drop. Every room except for two special rooms has degree 10 (for the 8 compass directions, together with up and down). Self-looping passages are permitted. We'll abbreviate the different exits from a room as having directions 0 through 9. You will be given n distinguishable objects labeled with letters of the alphabet starting with ``A''. These objects can be dropped in a room and later picked up when you return to the same room. Only one object can be dropped in a room (since the objects are individually distinguishable, there is no advantage to dropping multiple objects).

There are two special rooms. One is the start room, which has just one passage to/from the maze. The other is the treasure room, which also has just one passage to/from the maze. The passage out has direction 0 for both rooms.

You will have a fixed number of turns with which to explore the maze. The number will depend on the maze, and will be known to the player in advance. Each group will come up with some mazes, and some mazes will be supplied by the instructor/TA.

The primary goal is to find the treasure room; the secondary goal is to map as much of the maze as possible. Your players will thus be scored as follows:

• 1 point for each distinct edge traversed. You don't get an extra point for traversing it in the opposite direction.
• 10 points for each distinct room visited, excluding the start and treasure rooms.
• The final score is doubled if the player has found the treasure room.

Since the score reveals information about the maze, players will be unaware of their scores.

To avoid hard-coding of solutions to the known mazes, the simulator will randomly assign the direction labels for each room each time it is run. Also, players are not permitted to write persistent files to be read on future runs, since such files could lead to short-cuts on repeated instances of the same map.

At the end of the project we'll run some tournaments on a variety of mazes, including some you won't have seen before. We'll vary n, to see how strongly scores depend on the number of available objects. Since there might be some randomness in the performance of your players, we'll probably run several instances on the same map and average the results.