Hints for Assignment 2

As promised, below are a bunch of hints for doing assignment 2. These generally pertain to step C, wherein you will implement your game data module.

You are not required to use any of these hints.

Sample boards and moves

Click here to see some sample boards drawn in a text-based mode, and a few sample moves. This should help you get a sense of the game.

Some declarations

Below are some declarations that you may find helpful.

    type directionType : enum (left, right, down, up)

    % The tile type.
    % For elbows, the last two characters in the name indicate the directions
    % of the exits.  For Ts, the last characters indicate the direction of the
    % stem.
    type tileType : enum (elbowUR, elbowRD, elbowDL, elbowLU, Tdown,
        Tleft, Tup, Tright, straightHoriz, straightVert, cross)

    const numTileTypes := 11

    const numPrizes := 5

    % Each node contains the type of tile, whether the it contains a prize,
    % whether it contains the red or blue players' pieces, and pointers to
    % its left, right, upper and lower neighbours.
    type squareType :
        record
            tile : tileType
            prize : int
            hasAPlayer : boolean
            hasBPlayer : boolean
            left : ^squareType
            right : ^squareType
            up : ^squareType
            down : ^squareType
        end record

    const boardSize := 5

These declarations include a type, squareType, for storing each of the 25 tiles in the board. Even though you are required to use circular, doubly-linked lists for the rows and columns, there are other ways to go about defining your square or node type. For instance, you could remove the hasAPlayer and hasBPlayer booleans from the record and instead keep a pointer for each player that points directly to the tile that they are on.

These declarations use "enumerated types" in two places. With an enumerated type, you can compute the next value in the sequence using "succ" (which stands for "successor"). See pages 29-30 of the text for information about enumerated types. Another option is to simply declare constants for each of the tile types and directions. Eg, "const elbowUR : int := 1".

Notice that we have defined 11 different tile types. Really, these represent combinations of tile type and rotation.

Pointing to the board

One thing that is not included in these declarations is some pointer or pointers to the 25 tiles. There are many options here also. For example, you could store just one pointer to one of the tiles (perhaps the upper left one -- it's arbitrary which one you choose). From here you can get to every other tile. Or you could store an array of pointers to the leftmost tile in each row. Plus an array of pointers to the topmost tile in each column, perhaps. You could even have another two arrays to point into the bottom and right hand sides of the board.

Generating a random tile

Below is a function that can generate a random tile from the 11 possibilities. It uses our enumerated type for tiles, declared above.

    % makeRandomTile
    %----------------------------------------------------------------
    % Return a tile selected at random.

    function makeRandomTile : tileType

        var which : int
        randint (which, 0, numTileTypes - 1)
        var t : tileType := tileType.elbowUR
        for i : 1 .. which
            t := succ (t)
        end for

        result t

    end makeRandomTile

Creating a random board

Linking up 25 random tiles to make the initial board is one of the trickier pieces of code you'll write in your module. The head TA wrote in the comments in his solution "This is a MESS if it's not abstracted properly." Here's a suggestion to make it easier:

Write a procedure that can create a single row of 5 random tiles, and which you will call 5 times. Write another procedure that can take pointers to two consecutive rows and link their up and down pointers to create proper columns.

Drawing the board

You program must be able to run in a "text-based" mode. (Additionally, you can provide a graphics mode if you wish.) By "text-based", we mean all input and output is done by plain old text with simple puts and gets. There can be absolutely nothing that relocates the cursor on the screen. The reason for this restriction is that in text-based mode, you can produce physical printouts that show your your program running. Once you start jumping around the screen, this is not possible.

You can draw a nice board with only plain old characters, as in the example above. The code for this is a bit of a pain however, because you can't do the logical thing:

	% The obvious algorithm:
	for row : 1..5
	    for column : 1..5
		draw a picture representing the tile at (row, column)
	    end for
	end for

Think about why you can't.

Well, you can use this algorithm if you draw a whole tile using a single character. But that's not practical since your picture of the tile has to show the tile type, and who's sitting on it (if any player is) and what prizes are sitting on it (if any).

Click here to get code that will draw a board for you in a text-based mode. If you want to use this code without changing it at all, you are required to save it in its own file and then "include" that file in the spot where you need the code in your program. (And don't bother printing out and handing in the file containing our code.) An include tells the compiler to act as if the code were right there in your file. It's a little different than using an import statement. (See the text, p. 125 if you'd like to know the difference.)

Our drawBoard code presumes the existence of several subprograms. You will have to write these if you want to use our drawBoard:

    % tileTypeAt
    %----------------------------------------------------------------
    % Return the type of the tile at location (row, col).
    function tileTypeAt (row : int, col : int) : tileType

    % playerAAt
    %----------------------------------------------------------------
    % Return true if player A is at location (row, col), and false otherwise.
    function playerAAt (row : int, col : int) : boolean

    % playerBAt
    %----------------------------------------------------------------
    % Return true if player B is at location (row, col), and false otherwise.
    function playerBAt (row : int, col : int) : boolean

    % prizeAt
    %----------------------------------------------------------------
    % Return the prize number at location (row, col), or zero if there is
    % no prize there.
    function prizeAt (row : int, col : int) : int

Sliding the spare tile in

Sliding the spare tile in is probably the other trickiest piece of code. Consider a specific example: sliding the spare tile into row 4 from the left hand side. There are two main approaches to consider. I won't give every detail of the approaches, but here's the general idea:

Insert the spare tile into the circularly-linked list for row 4 (this is quite easy because nothing really has to move; just a few pointers change) then adjust all the up and down pointers in row 4 and the two rows beside it (this is tricky).
Or don't change any pointers at all. Leave the tile nodes linked up exactly as they are, but shift the contents of each tile in row 4 over one tile to the right.

The choice is yours. One of these may be easier than the other to implement.

All of this should cause you to wonder about the wisdom of this data structure. Was it a good choice?

How will the players specify their moves?

If input has to be text only, you will have to come up with some way for the players to say where they want their piece to move in part (b) of their turn. Perhaps the simplest thing is to ask the player to type in a string, where each character represents a single step in one direction. For instance, "UULLLD" could mean "up, up, left, left, left, down"

If you add the optional graphics mode, your players can use the mouse to specify their moves.

Checking if a player's move is valid

A string representing a move can be invalid for two kinds of reason:

It could have illegal characters in it, or some other kind of problem that you can tell just by looking at the string.
Or it could look like a legal move, but turn out to be illegal once you consider the tiles on the board. For instance, it could ask to move down onto a tile that contains a straight piece that's oriented left to right.

You'll have to check for errors like these, either as you move a player's, or in advance of that.

You might find it convenient to have a function like this:

    % openOn
    %----------------------------------------------------------------
    % Return true iff tile is open on side d, that is, iff you can
    % arrive at or leave the tile from side d.

    function openOn (tile : tileType, d : directionType) : boolean

Back to the csc148 home page