Chapter 6. (Recursion Is Easy)

#|

You’ve seen lists, you’ve seen very basic recursion, and you know how to use big-bang to create a simple game. You are probably wondering when we get to make an interesting game. The answer is right now. In this chapter, we will use lists and leverage the full power of recursion to make the classic Snake game.

|#

6.1 Robot Snake

Walking along a dark corridor, Chad suddenly finds himself in a deep pit among DrRacket’s mischievous minions. The crazy critters are out of control and have scattered radioactive goo all over the place. He sees a tunnel on the other side of the pit and considers jumping over the dangerous, glowing puddles—but there are too many! Chad then stumbles across a jittering, broken robotic snake. Upon closer inspection, he finds a panel on the snake that houses its instruction manual. As it turns out, the snake is designed to dispose of radioactive goo by gobbling it up. As the snake eats more goo, it becomes larger. Chad looks at the snake again. Its segments are falling apart and its wiring is haphazard. He guesses that as long as the snake does not bump into the walls or itself, it will work just fine. Can you help Chad operate the snake?

In this chapter, we turn Chad’s encounter into an interactive game. The player uses the arrow keys to control a snake, which is placed in a rectangular pit. Appearing and disappearing goo items are scattered all around the pit, and it’s up to the snake to devour them. When the snake eats a piece of goo, though, a new one appears at a random position in the pit. In order for the snake to eat, its head must be over a piece of goo.

6.2 A Data Representation for the Snake Game

Before we develop a data representation, let’s look at an example. In the situation on the right, the snake is moving upward and has nearly hit the edge. The player can move the snake either right or left by hitting the arrow keys. If she doesn’t, the game will end on the next clock tick. The best option is for her to move to the right, so that she doesn’t become trapped in the corner. Also, turning right means her snake can easily eat that nearby piece of radioactive goo by moving down.

Let’s begin by considering how we will represent elements of the game as data. In the previous chapter, we used structures to represent our world, and we will do the same here:

(struct pit (snake goos))

This structure definition helps us represent the state of the world as a pit structure with two fields. The first field, snake, keeps track of the current state of the snake. The second field, goos, tells us about the pieces of goo in the snake pit.

Our representation choice for the snake pit implies that we need a snake representation. Again, we use a struct:

(struct snake (dir segs))

The snake structure has two fields: dir, which is the direction in which the snake is slithering, and segs, which is a list of segments. A direction is one of the following strings: “up”, “down”, “left”, or “right”. These correspond to the four arrow keys on your keyboard. We think of segments as a non-empty list of posns. The list can never be empty because, at the very least, the snake must have a head. As the game progresses and the snake eats more, this list will grow.

A posn is simply a point in two-dimensional space:

(struct posn (x y))

As in physics, we think about any object—snake segments or goos—as a point in the plane. With this representation, a check for collisions becomes especially easy. Objects collide when they both occupy the same point. We do pay a price for this simplicity, however. In particular, the segments of a snake cannot be arbitrary posns. Two neighboring segments may differ in at most one direction, not both, and the difference must be 1. Fortunately, the game creates snakes so that this is always true.

We also need the data representation for goo:

(struct goo (loc expire))

The loc field contains a posn representing the goo’s location. The expire field represents the number of clock ticks left before this goo expires.

Now we have introduced all of the structs needed to represent a world, and we can experiment with some simple worlds. Here is one:

> (define snake-example
    (snake "up" (list (posn 1 1) (posn 1 2) (posn 1 3))))
> (define goo-example
    (list  (goo (posn 1 0) 3) (goo (posn 5 8) 15)))
> (define pit-example
    (pit snake-example goo-example))
> pit-example
(pit
 (snake
  "up"
  (list (posn 1 1) (posn 1 2) (posn 1 3)))
 (list
  (goo (posn 1 0) 3)
  (goo (posn 5 8) 15)))

As you can see, we built the world in three steps. The first definition introduces a snake with three segments. The second one creates a list of two goos. And the third one combines these two in a pit.

6.3 The Main Function

Once you have figured out the data representations, the next task is to write the main function. Its purpose is to set up the initial game scenario and establish the event handlers. The goal of writing this function is to associate actions in the game with computer interaction modes.

For the Snake game, start-snake uses big-bang to set up and launch the game:

(define (start-snake)
  (big-bang (pit (snake "right" (list (posn 1 1)))
                 (list (fresh-goo)
                       (fresh-goo)
                       (fresh-goo)
                       (fresh-goo)
                       (fresh-goo)
                       (fresh-goo)))
            (on-tick next-pit TICK-RATE)
            (on-key direct-snake)
            (to-draw render-pit)
            (stop-when dead? render-end)))

The big-bang expression in this function consists of five parts. The first is the initial world, a snake pit. One important part is the to-draw clause. As implied by the name, render-pit renders the current world so that the player can see where the snake is and how to find the goo. The on-tick clause tells DrRacket to call next-pit every time the clock ticks. This function handles a number of actions: removing expired goo, checking if the snake can eat and grow, and making the snake slither. We also need a way to control the direction that the snake is moving in, so we hand big-bang the direct-snake function in the on-key spec. Finally, the game must stop when the snake dies, meaning we should supply a stop-when spec.

6.4 Clock Ticks

We could start anywhere with our discussion, but clock ticks mean action, and action is fun. The on-tick clause in start-snake tells DrRacket to call the next-pit function on every clock tick:

(define (next-pit w)
  (define snake (pit-snake w))
  (define goos (pit-goos w))
  (define goo-to-eat (can-eat snake goos))
  (if goo-to-eat
      (pit (grow snake) (age-goo (eat goos goo-to-eat)))
      (pit (slither snake) (age-goo goos))))

Like all clock tick handlers, this function consumes and produces a world. In this case, the function handles snake pits: making the snake longer when it has eaten, moving the snake, and handling the aging and renewing of goo.

The actual work proceeds in two steps. First, the internal definition goo-to-eat uses can-eat on the world’s snake and the world’s list of goo. This function returns #f or a goo within reach of the snake’s head. Second, if goo-to-eat produces a goo, then the snake eats the nearby goo and grows, and the goo ages. Otherwise, the snake slithers and the goo ages.

Also note the first two local definitions. They extract the pieces from the given structure. Doing so is common because it makes it easier to read the rest of the function.

Eating and Growing

In order for us to determine when the snake needs to grow, we need to know when it can eat. We define the function can-eat to determine if there is a nearby goo that the snake’s head can grab. If so, the function produces the piece that is to be eaten:

(define (can-eat snake goos)
  (cond [(empty? goos) #f]
        [else (if (close? (snake-head snake) (first goos))
                  (first goos)
                  (can-eat snake (rest goos)))]))

This function takes a snake and a list of goo. It then acts as a list-eater of the latter and determines if the snake’s head, which is the first segment in its list of segments, is close to any of the goo items in the list of goo.

Like all list-eating functions, can-eat checks if the list of goo is an empty list. If it is, then the snake cannot eat because there is no goo. Otherwise, there is at least one goo in the list, so we use close? to ask if the head is close to the first goo. If it is, we’ve found a goo to eat, so we return it. If it isn’t, we continue searching by recurring on the rest of the goos.

For the purposes of our simplistic game, the close? predicate just returns true when the given segment has the same location as the given goo:

(define (close? s g)
  (posn=? s (goo-loc g)))

But you can probably imagine how to change this definition for other interesting modes of play.

While we call can-eat a predicate, you should note that it doesn’t just return Boolean values. Like member, can-eat produces #f if the snake cannot eat any of the goo. And also like member, it produces a real value, namely, the goo that the snake can eat. The next-pit function exploits this fact when it calls eat to tell that function which specific goo is to be absorbed.

Next, eat removes the goo and replaces it with a new goo item:

(define (eat goos goo-to-eat)
  (cons (fresh-goo) (remove goo-to-eat goos)))

The eat function consumes a list of goo and a goo-to-eat. The assumption is that goo-to-eat is in the list, so we remove it and cons on a fresh goo to the front of the list.

All we need now is the function grow, which actually makes the snake longer:

(define (grow sn)
  (snake (snake-dir sn)
         (cons (next-head sn) (snake-segs sn))))

This function creates a new snake that is one segment longer than the given one. It does so by calling next-head on the snake and by consing the resulting new head to the existing snake. While this trick may surprise you, the head is really just a posn to the function, just like all the tail segments.

Slithering

Our snake can eat and grow, so now we need to make it move when it is not eating. To do so, we create a new snake by adding a new head for the snake and removing the last element of the current segs list:

(define (slither sn)
  (snake (snake-dir sn)
         (cons (next-head sn) (all-but-last (snake-segs sn)))))

Like grow, the slither function calls the function next-head to move the head. But the end of the snake needs to advance as well, which we accomplish by consing on the new head and removing the last segment using all-but-last.

Here’s the all-but-last function, which returns the given list of segments without its last one:

(define (all-but-last segs)
  (cond [(empty? (rest segs)) empty]
        [else (cons (first segs) (all-but-last (rest segs)))]))

Unlike the other list-eating functions we have seen so far, the all-but-last function works only on non-empty lists, because the snake always has a head. If the rest of the list is empty, meaning that there is one element in the list, then it returns empty. Otherwise, the function uses cons on the first element of the given list and recurs by calling all-but-last on the rest. As you probably guessed, this call retrieves all but the last segment of the rest of the list.

Now it’s time to look at the often-used next-head function:

(define (next-head sn)
  (define head (snake-head sn))
  (define dir  (snake-dir sn))
  (cond [(string=? dir "up") (posn-move head 0 -1)]
        [(string=? dir "down") (posn-move head 0 1)]
        [(string=? dir "left") (posn-move head -1 0)]
        [(string=? dir "right") (posn-move head 1 0)]))

The next-head function contains two internal definitions: one for the snake’s head and one for the snake’s direction. We use a cond to create the new head. The function returns a new segment based on the given direction of the snake and where the head is currently located. It employs posn-move to determine the new location of the head:

(define (posn-move p dx dy)
  (posn (+ (posn-x p) dx)
        (+ (posn-y p) dy)))

This function takes a posn and two numbers: dx and dy. It adds dx to the x coordinate of the posn and adds dy to the y coordinate of the posn. It thus allows us to move a posn by a certain number of points along the x-axis and y-axis of a plane.

Rotting Goo

Finally, we make the goo rot and replace expired goo with new goo. We start by defining age-goo, which appears in the next-pit function:

(define (age-goo goos)
  (rot (renew goos)))

The age-goo function consumes and produces a list of goo. Since its purpose is to rot each of the goos and replace any totally rotten goos with fresh ones, age-goo is defined as the composition of two helper functions: rot and renew. The rot function’s job is to decay each goo, so it just passes over the list, calling decay on each element:

(define (rot goos)
  (cond [(empty? goos) empty]
        [else (cons (decay (first goos)) (rot (rest goos)))]))

The renew function is a similar list-eater but uses rotten?:

(define (renew goos)
  (cond [(empty? goos) empty]
        [(rotten? (first goos))
         (cons (fresh-goo) (renew (rest goos)))]
        [else
         (cons (first goos) (renew (rest goos)))]))

Here’s rotten?, which is used to detect goo that should be replaced with fresh goo:

(define (rotten? g)
  (zero? (goo-expire g)))

We still need to create the fresh-goo function, which randomly creates new goo structures:

(define (fresh-goo)
  (goo (posn (add1 (random (sub1 SIZE)))
             (add1 (random (sub1 SIZE))))
       EXPIRATION-TIME))

The fresh-goo function creates a new piece of goo with its loc field set to be a random posn within the boundaries of the pit. The x and y fields of the posn are random numbers chosen from the range 1 to the constant SIZE. The goo’s expire field is set to be the constant value of EXPIRATION-TIME.

Note

#|

When we designed this game, we discussed the timing a lot. You may find a game with (add1 (random EXPIRATION-TIME)) more appealing. Why do we need add1 here?

|#

And that is all there is to handling clock ticks. Now we can turn our attention to other aspects of the game, such as player input and game-rendering functions.

6.5 Key-Events

As mentioned at the beginning of this chapter, the player will use the arrow keys to direct the snake. Let’s look at the direct-snake function that we saw in start-snake, because it deals with key-events:

(define (direct-snake w ke)
  (cond [(dir? ke) (world-change-dir w ke)]
        [else w]))

A key-handler such as this function takes two arguments: the current snake pit and a key-event. If that key-event is a direction, then we may want to change the direction of the snake in the pit; otherwise, we want to return the current world.

The dir? function checks whether the player has pressed an arrow key:

(define (dir? x)
  (or (key=? x "up")
      (key=? x "down")
      (key=? x "left")
      (key=? x "right")))

Next, we need a function that will change the direction of the snake in response to the player’s keystroke:

(define (world-change-dir w d)
  (define the-snake (pit-snake w))
  (cond [(and (opposite-dir? (snake-dir the-snake) d)
              ;; consists of the head and at least one segment
              (cons? (rest (snake-segs the-snake))))
         (stop-with w)]
        [else
         (pit (snake-change-dir the-snake d) (pit-goos w))]))

The function world-change-dir consumes two arguments: a snake pit and a direction. It extracts the snake from the pit and then checks whether the direction d is the opposite of the snake’s current direction. If this is true and the snake consists of more than just a head, the function returns the given world wrapped in stop-with. Remember that an instance of the stop-with struct tells big-bang to act as if the game has come to an end. And why does the function say so? Because a snake that flips its head runs into itself.

If the key-event d is acceptable or the snake consists of just a head, then it is time to create a new pit with a snake going in the chosen direction and the old goo. That’s the purpose of calling snake-change-dir. You can actually experiment with world-change-dir in the interactions panel. You start by building up a snake and then you include this snake in a simple world:

> (define snake-going-left (snake "left" (list (posn 2 18))))
> (define plain-world (pit snake-going-left empty))

Note that plain-world comes without goos, but that is okay for experiments. And then you apply the function to this world and a key-event, which you can do because a key-event is just a string:

> (world-change-dir plain-world "right")
(pit (snake "right" (list (posn 2 18))) '())

While plain-world contains a snake that is going left, the resulting pit contains a snake going right, which is precisely what you want. Before you read on, you may wish to open the source of the game in DrRacket and make up an experiment with snakes that contain some additional segments.

In order to complete the world-change-dir function, we need to define the helper function, opposite-dir?:

(define (opposite-dir? d1 d2)
  (cond [(string=? d1 "up") (string=? d2 "down")]
        [(string=? d1 "down") (string=? d2 "up")]
        [(string=? d1 "left") (string=? d2 "right")]
        [(string=? d1 "right") (string=? d2 "left")]))

The opposite-dir? function compares two direction values to check whether they point in opposite directions.

6.6 Rendering

Recall that the representation of the pit assumes that all pieces of the game are single points. This is convenient and makes it trivial to check whether the snake can eat a piece of goo, whether the snake has run into itself, and a few other things.

In an image, a snake’s head takes up many pixels, and so does a radioactive piece of goo. To achieve this kind of scale-up, we create images of the same size for all basic pieces of the game: the snake head, HEAD-IMG; the snake segments, SEG-IMG; and the goo, GOO-IMG. Our rendering function then composes these images into a complete scene. This all works smoothly because every point in the representation is scaled up to the size of a basic image, and all basic images are of the same size.

Now consider the main rendering function that appears in the big-bang expression:

(define (render-pit w)
  (snake+scene (pit-snake w)
               (goo-list+scene (pit-goos w) MT-SCENE)))

The render-pit function calls two functions in order to render the game: snake+scene and goo-list+scene. Both functions operate exactly as implied by their names. The snake+scene function draws the snake into a given scene, and the goo-list+scene function draws the list of goo into the scene. And as you can see, it all starts with an empty scene. In order to make render-pit work, we need to define these functions.

We start with the snake+scene function:

(define (snake+scene snake scene)
  (define snake-body-scene
    (img-list+scene  (snake-body snake) SEG-IMG scene))
  (define dir (snake-dir snake))
  (img+scene (snake-head snake)
             (cond [(string=? "up" dir) HEAD-UP-IMG]
                   [(string=? "down" dir) HEAD-DOWN-IMG]
                   [(string=? "left" dir) HEAD-LEFT-IMG]
                   [(string=? "right" dir) HEAD-RIGHT-IMG])
             snake-body-scene))

The process to render the snake onto the given scene consists of three steps. First, snake+scene adds the body of the snake to the scene using the helper function img-list+scene. This function adds one SEG-IMG at each position of the body; if the list is empty, it returns the given scene. Second, the function extracts the snake’s direction. Finally, snake+scene adds the image of the snake’s head to the composite scene it has so far. The image used for the head is chosen based on the direction of the snake.

Now let’s look at the img-list+scene helper function. It takes a list of posns, an image, and a scene:

(define (img-list+scene posns img scene)
  (cond [(empty? posns) scene]
        [else (img+scene
               (first posns)
               img
               (img-list+scene (rest posns) img scene))]))

As you can see, it is a standard list-eating function. It renders the given image at the positions specified by the given list of posns on top of the given scene. If the list is empty, then the function returns the given scene. Otherwise, it calls img+scene, which draws the given image at the first posn onto the scene that we get by calling img-list+scene again on the rest of the list of posns.

Here is the img+scene function:

(define (img+scene posn img scene)
  (place-image img
               (* (posn-x posn) SEG-SIZE)
               (* (posn-y posn) SEG-SIZE)
               scene))

It takes an image, a posn, and a scene. Using place-image, it places the given image at the x and y coordinates of the posn—multiplied by our agreed-upon size per image segment—onto the given scene.

All that is left to do as far as rendering is concerned is to draw the goo:

(define (goo-list+scene goos scene)
  (define (get-posns-from-goo goos)
    (cond [(empty? goos) empty]
          [else (cons (goo-loc (first goos))
                      (get-posns-from-goo (rest goos)))]))
  (img-list+scene (get-posns-from-goo goos) GOO-IMG scene))

Similar to the snake+scene function, goo-list+scene employs img-list+scene to render goos. The only difference is that we pass different arguments to the img-list+scene function. Instead of using the SEG-IMG constant, we use GOO-IMG for the image of a piece of goo.

We do need to define the get-posns-from-goo function in order to obtain the posns of each goo in the list of goo. Once again, this function uses the power of list recursion to create a list of posns from the list of goo that we provide the function. If the list is empty, then the function returns empty. Otherwise, the function uses goo-loc to access the loc field of the first piece of goo. We then use cons to attach this value to the recursion on the rest of the list of goo.

6.7 End Game

Now that we have completed the functions that help us handle the player’s key input and render the game, we need to define some functions that determine when the game ends. There are two conditions that determine whether the game is over: the snake collides with either itself or the surrounding walls.

Let’s consider the dead? function that appears in the start-snake function:

(define (dead? w)
  (define snake (pit-snake w))
  (or (self-colliding? snake) (wall-colliding? snake)))

This function returns #t if the snake from the world has collided with a wall or has collided with itself. If either is the case, then the stop-when clause in big-bang will be triggered and the game will end.

We should also produce an image for the stop-when clause, so that it is obvious when the game is over:

(define (render-end w)
  (overlay (text "Game Over" ENDGAME-TEXT-SIZE "black")
           (render-snake-world w)))

The render-end function overlays an image of “Game Over” on the last scene of the game. If you can think of something better, modify the code.

Next we look at the functions that determine if the snake collides with itself or the wall. First, we define self-colliding?:

(define (self-colliding? snake)
  (cons? (member (snake-head snake) (snake-body snake))))

The self-colliding? function consumes a snake and calls the built-in function member, which will check whether the head of the snake is the same as one of the segments in the rest of the snake’s body. That’s all there is to it because segments are just points.

All that remains for checking collision is to check against the walls of the pit:

(define (wall-colliding? snake)
  (define x (posn-x (snake-head snake)))
  (define y (posn-y (snake-head snake)))
  (or (= 0 x) (= x SIZE)
      (= 0 y) (= y SIZE)))

We start wall-colliding? by defining the x and y positions of the snake’s head. Then, we check if its x or y coordinate is equal to any of the boundaries of the pit. If none of these four conditions is true, then the snake has not collided with the wall.

6.8 Auxiliary Functions

We are almost finished with the Snake game, but we need to define two helper functions that have been used in various parts of our code. First, we need the posn=? function, which determines whether two posns have the same x field and the same y field:

(define (posn=? p1 p2)
  (and (= (posn-x p1) (posn-x p2))
       (= (posn-y p1) (posn-y p2))))

This function compares the fields of two posns for equality. Yes, we could use equal? but you should know why we don’t.

Beyond this equality function, we need four functions that manipulate the snake:

(define (snake-head sn)
  (first (snake-segs sn)))

(define (snake-body sn)
  (rest (snake-segs sn)))

(define (snake-tail sn)
  (last (snake-segs sn)))

(define (snake-change-dir sn d)
  (snake d (snake-segs sn)))

If you had bought a serious book on programming, it would explain these functions in gory detail. But this is a cheap book, and you get what you pay for.

Return—Chapter Checkpoint

In this chapter, we created the Snake game, which made heavy use of lists and recursive functions:

• We processed lists using a variety of list-eating functions.

• We gained a lot of experience with the 2htdp/image library to visually render a game.

Chapter Challenges

• Easy. Change the program so that the final image displays the number of pieces of goo that have been eaten.

• Easy. Alter the game so that it has a randomly varying number of goos.

• Medium. Add another type of goo that makes the snake grow two segments longer instead of one segment longer.

• Medium. Add obstacles to the game. If the snake touches the obstacles, the game is over.

• Medium. Once you have obstacles, make them move around at certain intervals.

• Difficult. Add a second snake that is controlled by the “w,” “a,” “s,” and “d” keys. You may want to look in the docs for on-pad, another kind of big-bang clause. Then find a friend to play against you.