On this page:
Natural Numbers
Recursion in Universe Programs
Before You Go...

Lab 5 Recursive Data


Purpose: The purpose of this lab is to practice working with recursive data.

Textbook references: Chapter 9.3: Natural Numbers, Chapter 9.4: Russian Dolls

Natural Numbers

A natural number is any non-negative integer. That means, the smallest natural number is zero, and every further integer produced by adding at least 1 to that number is also a natural number. Here is a recursive data definition for natural numbers that encompasses this information:

; A Nat is one of:
; - 0
; - (add1 Nat)
; and represents a natural number

Exercise 1 Your TAs should go over the template for this data definition with you. Copy the data definition and its template into your file.

Exercise 2 Design the function add-nats which takes two natural numbers and uses the recursive template to add these numbers together. You may use add1 but you may NOT use + when designing this function.

Exercise 3 Design the function exponentiate which takes two natural numbers and returns the result of raising the first number to the power of the second. For example, (exponentiate 2 3) would produce 8 (because 2^3 = 8). This function should follow the recursive template for natural numbers and should NOT use the pre-defined function expt.

Please submit the above exercise to the handin server by 10pm EDT on the day of lab.

Recursion in Universe Programs

In the remainder of today’s lab we will walk through the design of a small game. In this game you are trying to escape from a horde of zombies! If the zombies touch you, you die. The zombies continually move towards you as the clock ticks and you can move your character by pressing the arrow keys.

Step 1: What Stays the Same?

The first step is to determine what stays the same throughout the program. These things will be defined as constants at the top of our program. To help you out we have defined several constants below. You are welcome to add to these or change them if you feel the need.

(require 2htdp/image)
(define BG-WIDTH 700)
(define BG (empty-scene BG-WIDTH BG-HEIGHT))
(define DOT-SIZE 10)
(define PLAYER-IMG (circle DOT-SIZE "solid" "pink"))
(define ZOMBIE-IMG (circle DOT-SIZE "solid" "DarkSeaGreen"))
(define LOSE-IMG (overlay (text "YOU LOSE :(" 20 "dark red") BG))
(define PLAYER-INITIAL (make-posn (/ BG-WIDTH 2) (/ BG-HEIGHT 2)))
(define PLAYER-SPEED 2)
(define ZOMBIE-SPEED 2)

Exercise 4 Copy the above definitions into your file. You can feel free to change the colors and sizes if you wish.

Step 2: What Changes?

The next step is to determine what changes as the program runs. We will use these changes to determine our world state: the data we will use to represent this program.

Here is the data definition we will be using for our world state in this program:

(define-struct zombie [x y more])
; A ZombieGame is one of:
; - Posn
; - (make-zombie Nat Nat ZombieGame)
; and represents either the position of a player or a game with at least 1 zombie

Exercise 5 Complete the steps of the data design recipe for the above data definition.

Step 3: Which Handlers Do We Need?

The next step is to determine which of big-bang’s many handlers we may need. Handler functions are the functions that go in the different clauses of the call to big-bang.

Since we have a limited time to work on this program we have provided the signature and purpose of each required function below.

; draw-game : ZombieGame -> Image
; Draw the zombies and player on the background
; move-zombies : ZombieGame -> ZombieGame
; Move each zombie towards the player
; move-player : ZombieGame KeyEvent -> ZombieGame
; If the player presses an arrow key, move in that direction (otherwise no change)
; game-over? : ZombieGame -> Boolean
; Did the player get eaten by a zombie?
; draw-end-scene : ZombieGame -> Image
; Draw the "you lose" screen after the player is eaten

Step 4: Main Function

Now that we know which functions we are going to use, we can write our main function which will call big-bang. We write this function first before designing the helper functions because we are following a top down approach to programming. This helps provide clarity when other people are reading your code.

Here is the main function definition for our program:

(require 2htdp/universe)
; play-zombie-game : Nat -> ZombieGame
; Play the zombie game with the given number of zombies
(define (play-zombie-game n)
  (big-bang (initial-zombies n PLAYER-INITIAL)
    [to-draw draw-game]
    [on-tick move-zombies]
    [on-key move-player]
    [stop-when game-over? draw-end-scene]))

Exercise 6 Copy the above definition into your file. You can use #; before the definition to comment it out until you get a chance to define all the necessary helper functions.

Step 5: Design of Handlers

You may have noticed an additional function in our above definition: initial-zombies. This function is intended to produce the given number of zombies at random locations on the screen. It takes as input a natural number. Recall that the recursive definition for a natural number is

; A Nat is one of:
; - 0
; - (add1 Nat)
; and represents a natural number
(define (nat-template n)
  (cond [(zero? n) ...]
        [(positive? n) (... (nat-template (sub1 n)) ...)]))

Exercise 7 Use the above template for natural numbers to design initial-zombies. Recall that random is a function that will get you a random number. The signature, purpose, and tests for this function have been provided below.

; initial-zombies : Nat ZombieGame -> ZombieGame
; Add the given number of zombies to the given game
(check-expect (initial-zombies 0 PLAYER-INITIAL) PLAYER-INITIAL)
 (initial-zombies 2 PLAYER-INITIAL)
 (make-zombie (random BG-WIDTH) (random BG-HEIGHT)
              (make-zombie (random BG-WIDTH) (random BG-HEIGHT) PLAYER-INITIAL)))

Exercise 8 Design draw-game, the function which draws the current state of the game. Zombies should be drawn using ZOMBIE-IMG (defined in the constants above) and the player should be drawn using PLAYER-IMG.

Next we need to design our on-tick function and our on-key function. These functions are a bit complicated so we have provided them below.

; move-zombies : ZombieGame -> ZombieGame
; Move each zombie towards the player
(check-expect (move-zombies PLAYER-INITIAL) PLAYER-INITIAL)
 (move-zombies (make-zombie 0 0 (make-zombie 500 300 PLAYER-INITIAL)))
 (make-zombie 1 1 (make-zombie 498 300 PLAYER-INITIAL)))
(define (move-zombies zg)
  (cond [(posn? zg) zg]
        [(zombie? zg)
         (update-zombie (move-towards (zombie-x zg) (zombie-y zg) (get-player zg))
                        (move-zombies (zombie-more zg)))]))
; update-zombie : Posn ZombieGame -> ZombieGame
; Add a zombie to the given game at the given position
(check-expect (update-zombie (make-posn 10 5) PLAYER-INITIAL) (make-zombie 10 5 PLAYER-INITIAL))
 (update-zombie (make-posn 0 100) (make-zombie 10 5 PLAYER-INITIAL))
 (make-zombie 0 100 (make-zombie 10 5 PLAYER-INITIAL)))
(define (update-zombie zposn zg)
  (make-zombie (posn-x zposn) (posn-y zposn) zg))
; move-towards : Nat Nat Posn -> Posn
; Move the given coordinates towards the given position
(check-expect (move-towards 0 0 (make-posn 10 10)) (make-posn 1 1))
(check-expect (move-towards 100 200 (make-posn 5 1)) (make-posn 99 198))
(define (move-towards x y p)
  (make-posn (floor (+ x (* ZOMBIE-SPEED (/ (- (posn-x p) x)
                                            (total-diff (make-posn x y) p)))))
             (floor (+ y (* ZOMBIE-SPEED (/ (- (posn-y p) y)
                                            (total-diff (make-posn x y) p)))))))
; total-diff : Posn Posn -> Number
; Produces the sum of the difference in x and the difference in y
(check-expect (total-diff (make-posn 2 0) (make-posn 3 2)) 3)
(check-expect (total-diff (make-posn 10 5) (make-posn 5 10)) 10)
(define (total-diff p1 p2)
  (+ (abs (- (posn-x p1) (posn-x p2)))
     (abs (- (posn-y p1) (posn-y p2)))))
; get-player : ZombieGame -> Posn
; Get the player in the given zombie game
(check-expect (get-player PLAYER-INITIAL) PLAYER-INITIAL)
 (get-player (make-zombie 10 5 (make-zombie 6 11 (make-posn 2 3))))
 (make-posn 2 3))
(define (get-player zg)
  (cond [(posn? zg) zg]
        [(zombie? zg) (get-player (zombie-more zg))]))
; move-player : ZombieGame KeyEvent -> ZombieGame
; If the player presses an arrow key, move in that direction (otherwise no change)
(check-expect (move-player (make-posn PLAYER-MIN 10) "left") (make-posn PLAYER-MIN 10))
 (move-player (make-zombie 100 200 (make-posn 200 100)) "right")
 (make-zombie 100 200 (make-posn (+ 200 PLAYER-SPEED) 100)))
(define (move-player zg key)
  (cond [(posn? zg) (move-posn zg key)]
        [(zombie? zg)
         (make-zombie (zombie-x zg) (zombie-y zg) (move-player (zombie-more zg) key))]))
; move-posn : Posn KeyEvent -> Posn
; Move the given position if an arrow key was pressed unless you are already at the edge
(check-expect (move-posn (make-posn PLAYER-MIN 10) "left") (make-posn PLAYER-MIN 10))
(check-expect (move-posn (make-posn 100 200) "left") (make-posn (- 100 PLAYER-SPEED) 200))
(check-expect (move-posn (make-posn PLAYER-MAX-X 50) "right") (make-posn PLAYER-MAX-X 50))
(check-expect (move-posn (make-posn 100 200) "right") (make-posn (+ 100 PLAYER-SPEED) 200))
(check-expect (move-posn (make-posn 50 PLAYER-MIN) "up") (make-posn 50 PLAYER-MIN))
(check-expect (move-posn (make-posn 100 200) "up") (make-posn 100 (- 200 PLAYER-SPEED)))
(check-expect (move-posn (make-posn 10 PLAYER-MAX-Y) "down") (make-posn 10 PLAYER-MAX-Y))
(check-expect (move-posn (make-posn 100 200) "down") (make-posn 100 (+ 200 PLAYER-SPEED)))
(check-expect (move-posn PLAYER-INITIAL "x") PLAYER-INITIAL)
(define (move-posn p key)
  (cond [(key=? key "left")
         (make-posn (max PLAYER-MIN (- (posn-x p) PLAYER-SPEED)) (posn-y p))]
        [(key=? key "right")
         (make-posn (min PLAYER-MAX-X (+ (posn-x p) PLAYER-SPEED)) (posn-y p))]
        [(key=? key "up")
         (make-posn (posn-x p) (max PLAYER-MIN (- (posn-y p) PLAYER-SPEED)))]
        [(key=? key "down")
         (make-posn (posn-x p) (min PLAYER-MAX-Y (+ (posn-y p) PLAYER-SPEED)))]
        [else p]))

Exercise 9 Copy the above function definitions into your program.

Exercise 10 Design the stop-when handler function, game-over?. If any of the zombies has reached the player, this function should return #t. Otherwise it should return #f. The function get-player which was defined above in the on-tick section will come in handy. In addition, we have provided a function below that checks whether two positions are touching. NOTE: If you changed the size of the dots defined by DOT-SIZE you may have to adjust this function’s tests accordingly.

; touching? : Posn Posn -> Boolean
; Are these positions touching?
(check-expect (touching? (make-posn 0 0) (make-posn 5 2)) #t)
(check-expect (touching? (make-posn 100 50) (make-posn 50 100)) #f)
(define (touching? p1 p2)
  (<= (sqrt (+ (sqr (- (posn-x p1) (posn-x p2)))
               (sqr (- (posn-y p1) (posn-y p2)))))
      (* 2 DOT-SIZE)))

Exercise 11 Design the function draw-end-scene which takes in a ZombieGame and draws the losing screen, regardless of its input.

Give your game a try! How long can you last against the zombies? You can change the speed of the zombie in the ZOMBIE-SPEED constant or the speed of the player in the PLAYER-SPEED constant if you want to adjust the difficulty level.

Before You Go...

If you had trouble finishing any of the exercises in the lab or homework, or just feel like you’re struggling with any of the class material, please feel free to come to office hours and talk to a TA or tutor for additional assistance.