Lab 4

CS151 Home

Rules of the Game

We describe a one-player word game similar to Boggle. The player selects words from a grid of letters by clicking on sequences of letters. We will call each such sequence a path. When the path are contiguous and contains no cycles (i.e., no location is traversed by the path more than once), when it forms a valid English word according to its presence in a dictionary (provided), and when that word has not yet been chosen in the game, the player scores points for the word according to a formula given in Part 2. If the path is discontinuous, contains cycles, or represents an invalid or already-selected word, the player loses points according to the same formula.

Before you begin, make sure you have included your name, and the require statements to load all the libraries needed (shown on the right). One of these libraries, matrix, is probabaly new to you -- keep the documentation handy.

Part 1: Generating Letter Grids

First, you will build some utilities to generate letter grids (game boards). Letters will be selected at random and used to populate a matrix of letters. Here in Part 1, you do not need to concern yourself with the appearance or presentation of the letter grid: you just need to produce the data structure storing the letters, for use in the graphical application later.

We require that you write this function:

make-letter-grid : num num -> matrix-of-char

Use make-matrix and random. Uppercase letters should be chosen randomly, with the following restriction: every third letter must be a vowel. Calling (make-letter-grid 4 4) should produce something like this:

Note that character literals are written and displayed in Racket like so: #\A. Note also that as you count row-by-row, starting from the upper left corner, every third letter is a vowel. (Other positions can contain vowels as well.)

Part 2: Input Validation

A cell in the letter grid is referenced using a posn. Numbering starts from (0, 0) in the top-left corner. In the example, (make-posn 1 2) is the character #\M.

The representation as a path, as defined above, is simply a list of posn values.

Write the following functions.

1. valid-path? : list-of-posn -> boolean, which checks whether the input path satisfies two conditions:
   
   
   • contiguity: every posn value in the path is horizontally, vertically, or diagonally adjacent in any direction to the posn immediately preceding it.
   • freedom from cycles: no posn appears more than once in the path.
2. path->word : list-of-posn matrix-of-char -> string, which converts a path in a grid into a word. For example,

      (path->word (list (make-posn 1 0) 
                        (make-posn 1 1) 
                        (make-posn 2 2) 
                        (make-posn 1 2)) 
                  grid)

   where grid is the example grid shown above in Part 1, should return the string "FARM". You will need to use matrix-ref and Racket's string manipulation functions.
3. score-string : string -> num, which assigns a score to a word. Every consonant in the word adds 2 points and every vowel adds 1. For example, (score-string "FARM") evaluates to 7.

Part 3: Rendering

In this part, you will add animation and interactivity to your word game.

The world of this game consists of

1. a letter grid,
2. a list of words that have already been found by the player,
3. an ongoing path through the grid, represented by a list of posns,
4. a string message, showing the word currently being built, or how the score was affected by the last move, and
5. the current total score of the player.

Follow these steps to produce your rendering and interaction code.

1. Define a struct named world that contains the components listed above.
2. Write the function render-grid : matrix -> img that renders a matrix of characters as an image. Each character should be rendered in 20-point font, in a black bounding box of size 30 x 30. Running (draw-grid grid) where grid is the example grid from Part 1, should look like this:

   

   You will need to make use of matrix->rectangle and text.
3. Write render-words : list-of-string -> img to consume a list of strings and render them one below the other, in 12-point font. For example, (show-words (list "FARM" "FROM" "FOOL")) should produce the following image:

   

4. Write render : world -> scene. It must draw the current letter grid at the top-left of the scene, the player's current score, the message, and below that, the list of words found by the player. A rendering of the world using the grid from before, where (list "FARM" "FROM" "FOOL") is the list of words found so far, "+ 6 points for FOOL" is the message, and the current score is 20, should look more or less like this.

   

Part 4: Game Play

Download words.txt into the same directory as the program that you are working on. Copy the following line of code into your definitions:

(define dictionary (read-words "words.txt"))

This reads a list of short (<= 6 letters) English words into the global variable dictionary, which is a list of strings. You can refer to this list elsewhere your program.

Write a function add-word : world -> world. This function converts the current path (part c in the description of the world) into a word. It checks the following conditions:

1. whether the path is valid,
2. whether the word is in the dictionary, and
3. whether the word has not yet been found by the player.

If all three of these conditions are true, the move is good, and this happens:

1. the score of the found word is added to the current total score,
2. the found word is added to the list of found words,
3. the current path is reset to the empty list, and
4. the message is changed to "+ p points for word" where p is the score of the found word. For example, if "FOOL" was the found word, the message should be "+ 6 points for FOOL".

If any of the conditions do not hold, the move is not good, and this happens:

1. the score of the word is subtracted from the current total score as a penalty,
2. the current path is reset to the empty list, and
3. the message is changed to "-p points for invalid word".

Finally, write the function read-mouse : world num num mouse-event -> world. This function is similar to read-key from Lab 2, except that it tracks mouse events rather than key-events. read-mouse should update the world only when the mouse-button is released (when the mouse-event is "button-up").

If the player clicks anywhere outside the rendered grid, it indicates that a word is complete, and the world should be updated using add-word. The place where the player clicks are the x and y co-ordinates of the mouse, which are the second and third arguments to read-mouse.

If the player clicks within the grid, the posn that is clicked on should be added to the current path. The message should be updated to be the partial word that corresponds to the current path (including the most recently added posn). Note: you will first need to translate the mouse's x and y coordinates to the correct posn value. In the example scene shown in part 3, the mouse co-ordinates (x = 45, y = 92) corresponds to (make-posn 3 1).

Play

Define a world init-world, the world at the start of game play, with a 4 x 4 random letter-grid. Set the message of init-world to be "New Game".

Evaluate this big-bang expression, and have fun!

(big-bang init-world (to-draw render) (on-mouse read-mouse))

Submit

Submit your work by clicking the CS151 Handin button on the DrRacket toolbar by 10 pm on Sunday (Oct 24). Make sure your work is submitted as Lab4. As always, feel free to mail the lab instructors or the mailing list with any questions.

Extra-Not-For-Credit

These are exercises for your own enjoyment and learning. Feel free to discuss them with us.

1. Adjust the scene height when the list of found words overflows its bounds.
2. Render the clicked letters in the grid with a different color while a word is in progress.
3. Implement a timer. Stop the game after two minutes.
4. Write a program to find all the valid words in a grid [hard].