1 Can’t Stop Implementation: Part 1

The game of Can’t Stop is described in handout 3. In the next two assignments, you will implement a game master for assisting human players in playing the game of Can’t Stop. In this assignment, you will implement and test the data structures for representing the playing board of the game. In the next assignment, you will implement the game master itself.

I describe the game master here in order to provide the context for understanding the purpose and meaning of the data structures for this assignment. Although they are tailored for later use in implementing the game master, they are meaningful on their own and can (and should) be written and tested before having a full working implementation of the whole game.

2 Overview of the Game Master

The game master has three phases of operation.

Preparation:

The game master creates and initializes the game board. It also prompts for the names of between 1 and 4 players and assigns colors to them in order from the list (red,yellow,green,blue).

Play:

The game master supervises the play of the game. Players take turns in the order in which their names were entered, with player 1 moving first. When it is player i’s turn, player i interacts with the game master until the turn is over or the player resigns from the game. Turn then passes to the next active player in sequence, coming back to player 1 after the last player has taken his turn.

Termination:

The game master ends the game when a player has won or all players have resigned.

At the beginning of each move, the game master displays the game board and gives the player the option of rolling the dice, ending the turn, or resigning from the game. If the player elects to roll the dice, then the game master presents four random dice rolls to the player, who groups them into two pairs. (Cf. problem set 2.) The game master then plays the chosen pairs one at a time, if possible. If neither pair plays, then the player goes bust and the turn ends. Otherwise, the player is prompted for the next move, at which time he is again given the option of rolling, ending the turn, or resigning from the game. If a player elects to resign from the game, the player is removed from the list of active players, but any columns already captured by that player remain out of play.

3 Data Structures for Representing the Board and Players

Roughly 40% of the code to implement the game master is involved with representing and manipulating the game board and players. Below are descriptions of the four ADT’s involved with that part of the implementation, which form the basis of this assignment.

3.1 ADT board

A board defines data for representing the game board and functions for managing and displaying the board. Think of the board as a device for recording the progress of the game.

The board itself is easily represented by an array of columns. Because Can’t Stop uses only columns 2, . . . , 12, an array of length 11 would suffice. However, it is most convenient to allocate an array of length 13 so that columns 2,…,12 are in array slots [2]…[12], and slots [0] and [1] remain unused. In addition, it is very useful to have the board record the columns where the three towers are located so that it can easily find which columns to update at the end of a turn.

At the start of a player’s turn, startTurn() is called. This notifies the board that a new turn is starting, and it tells the board who is currently playing so that it can figure out which color tile to move.

To carry out a move, the player rolls dice, chooses two pairs, and adds them up to get two column numbers in which to move. This is all done outside of the board module. The board’s role is to figure out for each of the two dice totals whether or not it is possible to move in those columns, and if so, to actually perform the move. That’s what the function move() does. It is called is called twice, once for each of the two dice totals. It attempts to advance the tower on the corresponding column if one has already been placed there, or to place a tower on the column on the square following the current position of the player if no tower has been placed yet. It returns true if it succeeds. It returns false if it fails for any of three reasons: no tower is on the column and all three towers have been used up, column is already captured, tower has reached the end of the column and can’t move further.

When the game master decides the turn is over, it calls commitBoard() to end the turn and record the progress of the player, or it calls revertBoard() to remove the towers and revert the board back to the state it was in at the beginning of the turn.

Much of the work of the board functions described above is delegated to functions in the column module. For example, move() will carry out its work by calling the column functions startTower() and advanceTower(). Similarly, commitBoard() and revertBoard() will delegate much of their work to the corresponding column functions commitColumn() and revertColumn().

3.2 ADT column

A column defines the data for representing a single column of the game board. There are many ways of representing a column. The one most closely resembling the physical board represents each cell of the column by the set of markers that it contains. However, what one is most interested in about a column is which square a particular marker resides on. This suggests an alternative representation whereby the marker positions are represented by an integer array marker of column positions, indexed by color. One can use the value -1 to indicate that no marker of that color resides on the column. By considering the tower to be a white marker, its position can be represented in the same way.

Some additional information about the column will also need to be represented such as its number (for printing), its length, and some state information that lets one easily determine if the column is playable or not.

The functions on columns have mainly to do with towers. startTower() places a marker on the most advanced square belonging to a given player. It returns false to indicate failure if the column is not playable. advanceTower() moves the marker one square forward if possible and returns false if the column is not playable or the tower cannot be moved. commitColumn() moves the current player’s marker to the tower position and then removes the tower. revertColumn() simply removes the tower without updating the player’s marker.

3.3 ADT player

A player defines data for representing a player and functions for managing and displaying the player. A player has a string name (for printing), a color, and a count of the number of columns won. It has functions for obtaining each of those three data items. It also has a function notifyColumnWon() that will be called whenever the game master decides that the player has won another column. All it does to the player is to increment the stored count of columns won.

3.4 ADT color

The color ADT defines an enumerated type color_t for the colors white, red, yellow, green, and blue. It has functions colorName() and colorLetter() for obtaining the full name of the color and the capitalized first letter of the color name, respectively. Thus, colorName(yellow) returns "yellow" and colorLetter(yellow) returns 'Y'.

4 Assignment

For this assignment, you are to implement the four abstract data types described above: board, column, player, and color. Whenever questions arise about the exact meaning or purpose of a construct, remember that this is in the context of “Can’t Stop”, so you can use the rules and constraints of that game for guidance. For example, the column functions can assume that valid column numbers lie in the range [2,…,12] and that no column is longer than 13 squares. However, good coding practice would dictate that your programs fail gracefully if these assumptions are violated (such as by printing out an error message and then exiting) and that they never crash or corrupt memory. Checking for and reporting error conditions also makes your programs much easier to debug. You should feel free to ask me questions about any parts of the specification that are not clear.

I have placed header files for the four ADTs into the Zoo course directory

Your job is to write the corresponding implementation files. You will also need to write unit test programs to test the correctness of each of your modules. To help you get started, I have furnished a program test_board.c that can be compiled and linked to your implementations to produce a program test_board, which exercises the functions in board. The file test_board.out gives the results of running test_board.c when linked to my implementation of the ADTs. You will need to write similar programs to test your other modules.

Finally, I have placed both header and implementation files for a module util that contains three useful utility functions: safe_malloc(), safe_realloc(), and fatal(). You are free to uses these or not as you choose.

5 Deliverables

You should submit a complete set of source code files for the assigned modules (including copies of the header files and any needed utilities that I furnished), the unit test programs for testing your code (including my test_board.c), and a working multitarget Makefile that will build all of the unit tests. For each unit test program, you should also submit the output that it produces.