Due: Thursday November 7th, 6:00 p.m. Weight: 13% of your mark in this course
The purpose of this assignment is to give you experience with
designing an ADT, writing a module to implement it, doing more advanced
pointer manipulations, and writing precise specifications.
It will also give you a chance to design and write a reasonably large
program almost completely from scratch.
.
The object of the game is to move your player piece through a labyrinth
to land on (and hence win) prizes.
We have based our specifications on a real board game call Labyrinth, however,
we have taken some liberties with the rules to suit our
purposes.
There are 26 square tiles. Each has a picture stamped on it that represents a small section of a labyrinth, or maze. Each section is either straight, a 4-way cross intersection, a 3-way T-intersection, or an ``elbow'' joint (a 90 degree turn). See figure 1 for a diagram of the tile types. The playing board consists of a five-by-five square array of these tiles. If adjacent tiles line up nicely, a clear path can exist from one spot on the board to another. However, the board is laid out randomly to begin with (with a uniform distribution among the 3 tile types and their various rotations), and so there are many dead ends.
Five tiles have a prize sitting on them, and the prizes are numbered one through five. The two players will compete to win the prizes, in order from one to five. The prizes are numbered only to indicate the order in which they must be won; they are of equal value to the players. The winner is simply the player with the greatest number of prizes.
There is one spare tile, not currently part of the board. Each player has a player piece. Player A's piece is initially sitting on the tile in the upper left corner; player B's on the tile the lower right corner.
Figure 1: The four types of tile: straight, cross, T, and elbow.
The T and elbow tiles each have four distinguishable rotations,
and the straight tile has 2;
All rotations of the cross tile are indistinguishable from each other.
Thus, in total, there are 4+4+2+1 = 11 distinguishable
combinations of tile type and rotation.
The two players take alternating turns, with player A going first. A single turn consists of two steps:
If there are players or prizes on the row or column being shifted, they are shifted along with it. If a player or prize is shifted right off the end of the board with the new spare tile, that player or prize is placed onto the opposite end of the row or column that was just shifted -- it wraps around to the other side.
In choosing where to slide the spare tile in, your goal is to make it easier for you, and harder for your opponent, to reach the next prize.
When moving your piece, it is legal to wrap around from one edge of a row or column of the board to its other edge, as long as this doesn't take your piece through a wall. For example, if the tile at row 1, column 5 is T-intersection with an arm facing east, and the tile at row 1, column 1 is a straight piece going east to west, you may move your piece from one of these tiles to the other.
It is legal to step over or land on the other player or a prize. If your move ends with you on a prize and it is the next prize to be won in the sequence from prize 1 to 5, you keep it and it is removed from the board.
Define an ADT for the data related to the game described below. The data includes the tiles, the board, the player pieces, and the prizes. You will have to decide on the appropriate operations your ADT.
Do not include an operation for playing the entire game, or even taking a single turn, in your ADT definition. Your operations should be the things that can be done to the tiles, the board, the player pieces, and the prizes. Using those operations to play the game is not the responsibility of the ADT itself. Try to write an algorithm for the game without knowing what data structures will be used for the board etc.; this should suggest appropriate operations to include in your ADT.
Your ADT definition should be complete, unambiguous, and concise.
Design a signature for an OOT module that will implement this ADT. Write thorough comments on the header for each subprogram, including any needed preconditions.
Place a high priority on information hiding and abstraction.
One design possibility is to have a module (and associated ADT) for single tiles, separate from the whole game data module (and its ADT). There are advantages and disadvantages to this approach, due to the limitations of modules. Perhaps the simplest approach is to have a single module that encompasses all of the game data, including the individual tiles and the board. If designed well, this will earn full marks. Whatever your chosen design, you should have a good understanding of its advantages and disadvantages.
Implement the module. All design decisions are up to you except for this: you must use a circular, doubly-linked list for each row and each column of tiles. Thus, each node in your data structure will represent a single tile, and will have four pointers pointing to the four tiles adjacent to it.
We are not claiming that this is the best data structure for the game board. (As you work on implementing the module, think about alternatives and their relative advantages and disadvantages.) We have chosen it because it will increase your level of skill with using pointers.
Now use your module to create a program that lets two people play the Labyrinth game, as defined above, against each other. Again, all decisions are up to you, including input and output format. We expect most of you to use ordinary text-based input and output for this program, and we are providing some code to help you get this working. However, if you wish you may give the players the option of having the program use graphical output and/or mouse-based input. If you choose to do this, you may earn up to 5 bonus marks on the assignment. In any case, you must provide a text-based mode so that you can hand in your test cases entirely on paper.
Do not get carried away with the possibility of building a fancy interface that uses graphics. Even if you have completed all other aspects of this assignment, you probably have several other courses and a life outside of school that needs your attention.
Write a user's guide that explains how to use the program.
Assume that the user knows the rules of the game, and knows
how to start the program running.
See page 9 of the Course Handbook, under ``Use'', for some
suggestions on how to write a good user's guide.
The course web page contains suggestions for your data structures,
a generateRandomTile procedure, and a
a drawBoard procedure,
as well as a number of other hints.
You are not obliged to use any of these suggestions.
You should define your ADT and design your module signature before you implement your module (i.e., do parts A and B before doing part C). Thinking hard about the ADT definition and the module signature, and actually writing them down, will help you avoid plunging right into implementing bad design ideas. The head TA for CSC148 suggested that we tell you he is ``Really Glad'' that he took this approach when solving this assignment himself. He estimates that he saved at least 2 hours, and maybe 4, by writing the initial module signature first, complete with comments, because it allowed him to correct and simplify it before getting deep into the code.
The experience of doing subsequent steps in the development of your final program may well lead you to go back and modify your ADT or your module signature, but you will still save time overall.
If you did implement a graphical interface, produce printed (and annotated) test runs by running your program in its text-based mode, and hand in a diskette containing only a single copy of the program files for this assignment. The main program must be called main.t. If you do not follow these instructions, you will forfeit any bonus marks.
part A: ADT 15
part B: module signature 10
part C: module 35
part D: game 5
part E: users' guide 10
programming style 10
comments 10
overall quality of writing 5
TOTAL 100