CIT 594 Assignment 6: Beeper Hunt, Part I Spring 2004, David Matuszek

Purposes:

To give you some experience with:

• Program design
• Group programming
• Spanning trees
• Graph searching

General Idea:

In this assignment a robot wanders through a maze, collecting beepers. The goal is to collect as many beepers as possible within a given time limit.

There are various parts to this: Constructing the maze, placing beepers, moving the robot, and creating a visual display. I will specify in some detail what I want the program to do. Your first task is to determine the game architecture: what the classes are, and what methods they supply.

By the way, this assignment is based partly on the classic "Feed the Snake" game, and partly on Karel the Robot. Certain aspects have been considerably simplified.

Details:

Time

By "time" I really mean "robot steps." A robot takes one step in one time unit. The robot can take as much real time (within reason) as it needs to figure out where it should go next.

Magic Numbers

In the following sections I try to give reasonable numbers for the size of the array, the length of time beepers stay in the maze, etc. Please use named constants for these numbers, in case we decide to change them.

The Maze

The maze will be randomly generated. A new maze will be generated for each game, but once generated, it does not change throughout the course of that game.

The maze we will use will have a special form. There will be, in general, multiple paths from one location in the maze to another location in the maze. I'll try to describe the form of maze I have in mind, and I'll try to provide a picture in a future installment of this assignment.

Let's define a standard maze to be a maze that has exactly one path from any location in it to any other location in it. The maze we will use will be a 20 by 20 array, divided up into sixteen 5 by 5 subarrays. Each subarray will be a standard maze. However, there will be one opening between each pair of adjacent sub-mazes. Hence, a maze in the center has four openings (one to each of the four adjacent mazes), a maze along the edge has three openings, and a maze in the corner has two openings. So within a submaze, there is only one path between two locations, but you can go from any submaze to any adjacent submaze.

The Beepers

Beepers appear at random locations in the maze (but never in the same location as the robot). There are always two beepers in the array at any given time. Beepers will remain on the board for a fixed amount of time (maybe 50 steps) or until they are collected by the robot. (I may increase the number of beepers.)

The goal is to collect as many beepers as possible within a given time limit (say, 1000 time units).

The robot collects a beeper by moving into the maze location containing the beeper. (It should keep count of how many it has collected.) Each beeper will remain on the board for only a certain period of time, after which it disappears. Any time a beeper disappears or is collected by the robot, another beeper appears, so that there are always two in the maze at any given time.

The Robot

The robot's goal is to collect as many beepers as possible within the alloted time (one time unit = one step). To do this it will have to compute paths to the beepers, and decide which beeper to go after next.

The robot can move from any location in the maze to any horizontally or vertically adjacent location, provided there is not a maze wall in the way. The robot cannot move diagonally. There are walls all around the outside of the maze, so the robot does not have to worry about accidentally stepping outside the bounds of the array.

The robot has full knowledge of the maze and of beeper locations. It doesn't have to fumble around in the maze in order to discover where things are.

The Display

You should have a GUI that shows the maze, robot, and beepers, and shows the robot moving through the maze. It should give the user the ability to start a new game, and it should display a count of the number of beepers collected. The display should not be the focus of your efforts. (In fact, I might supply some code for this part.)

This Assignment:

Don't start coding!

Instead, make a rough design for the program. Decide what classes you think you should have, and what methods and responsibilities each class should have. Print this out and bring three copies of your rough design to class this Thursday, March 18. We will spend some time in class forming groups and discussing designs.