Exercise 174: Equip your program from exercise 173 with food.

Exercise 174: Equip your program from exercise 173 with food 

At any point in time, the box should contain one piece of food. To keep things simple, a piece of food is of the same size as worm segment. When the worm’s head is located at the same position as the food, the worm eats the food, meaning the worm’s tail is extended by one segment. As the piece of food is eaten, another one shows up at a different location.
Your program should place the food randomly within the box. To do so properly, you need a design technique that you haven’t seen before—so-called generative recursion—so we provide function definitions:

; Posn -> Posn

; ???

(define (food-create p)

(food-check-create p (make-posn (random MAX) (random MAX))))

; Posn Posn -> Posn

; generative recursion

; ???

(define (food-check-create p candidate)

(if (equal? p candidate) (food-create p) candidate))

The code for the exercise can be downloaded here. 

Generative recursion is defined by wikipedia as recursion that creates an entirely new object.

The function food-check-create creates a random object (via food-create) and then checks to make sure it's not in the same position as the posn passed in.  This is  to ensure that the food does not appear directly under the snakes head thus prematurely ending the game.


The function as supplied does not ensure that the food does not appear under the snake body - however that shouldn't matter too much as this will not end the game due to the collision detection only checking the worms head - it would just seem a bit funny to watch.

In my answer below, I have modified this function somewhat. This is due to the nature of the error collision I have used in checking for food collisions. I am checking the co-ordinates of the food and of the snake and determining a collision has occurred if the x and y co-ordinates are the same. This is an issue because if the co-ordinates are out by 1-20 pixels, the snake would appear to touch (or overlap) the food and pass right over it.

Therefore I have locked the food generation to appear on only x and y co-ordinates that the snake can appear on. I could have also fixed this in the food-collision method, but this would have mean the snake could still only partially intersect the food. It would work, but still look funny (and this is not how snake games are meant to work!)

Whilst I was writing this final stage of this question, I finally recall the the posn structure and realise I probably should have been using them all along (instead of the structure I called segments). This would be a minor thing to change, but I will leave them called segments as this makes the code easier to read and makes it consistant with the answers I have already created.




; Constants


(define WORM-SIZE 10)
(define WORM-MOVE (* WORM-SIZE 2))
(define WIDTH 800)  ; width of the game
(define HEIGHT 500) ; height of the game
(define SEGMENT (circle WORM-SIZE "solid" "red"))
(define FOOD (circle WORM-SIZE "solid" "black"))


; these structs will hold the current list of worm segments, the direction
; the worm is travelling in, and our world object
(define-struct segment(x-pos y-pos))
(define-struct direction(x y))


; worm is a list of worm segments
; direction is the direction the worm is travelling
; segment is our current food segment
(define-struct world(worm direction segment))


(define WORM (list (make-segment 100 100)
                   (make-segment 100 80)
                   (make-segment 100 60)) )      


; To save repeating these directions in tests and code, we'll define them here
(define DOWN  (make-direction 0 1))
(define UP    (make-direction 0 -1))
(define RIGHT (make-direction  1 0))
(define LEFT  (make-direction -1 0))


; Functions





This first function food-create is one of the supplied functions. I have changed the dimensions for the allowed positions for the food segment. This is because we need to make sure the food is in a position that our worm can travel over completely. (Currently this is multiples of 20). If we don't do this, the food could be off by for example 5 pixels, so we could travel over it and not trigger a collision



; Posn -> Posn
; Creates a new item of food at anywhere on the screen *except* for the 
; point defined by posn p. (eg the current snake position)

(define (food-create p)
  (food-check-create
   p 
   (make-segment (* (random (/ WIDTH WORM-MOVE)) WORM-MOVE)
                 (* (random (/ HEIGHT WORM-MOVE)) WORM-MOVE))))



; Posn Posn -> Posn
; checks that the candidate and p are at different points on the screen.
; If they are at the same point, create a new candiate by recursing into
; food-create, otherwise return the new candidate (which will then be returned
; via food-create)
(define (food-check-create p candidate)
  (if (equal? p candidate) (food-create p) candidate))




; draw worm in its current location on the screen. Instead of simply drawing 
; a single dot on the screen, we need to recurse down our list of worm 
; segments drawing each one at a time
(define (draw-worm background worm)
  (cond [(empty? worm) background]
        [else (place-image
               SEGMENT
               (segment-x-pos (first worm)) (segment-y-pos (first worm))
               (draw-worm background (rest worm))
              )]))




; This is a new method for question 174.
; This draws the food on to the background of our world
; Returns a new image.
(define (draw-food background food)
  (place-image FOOD (segment-x-pos food) (segment-y-pos food) background) )


; function to determine if we have collided with a food block
; returns true if the worm's segment is on top of the food
(define (worm-hit-food? segment food)
  (cond ((and (= (segment-x-pos segment) (segment-x-pos food))
              (= (segment-y-pos segment) (segment-y-pos food))) true)
        (else false)))




; This is a new function for question 174. It grows the worm one segment.
; To do this we just append a segment in the existing foods position
; on to the worm. Another way to do this would be to append at the end of 
; the list.
; This method was simpler though (but doesn't look quite as good)
(define (grow-worm worm food)
 (cons (make-segment (segment-x-pos food) (segment-y-pos food)) worm  ))
       


; This is a new function for question 174. This method will check if we are
; in the same location as a food item, and if so, eat it. (and make the worm
; grow longer)
; returns a world state with either nothing changed, or a longer worm and
; a new food;
(define (eat-food world)
  (cond ((worm-hit-food? (first (world-worm world)) (world-segment world))
         (make-world  (grow-worm (world-worm world) (world-segment world))
                     (world-direction world)
                     (food-create (first (world-worm world)))))
        (else world)))



; Checks if the snake has collided with either itself, or with the walls
; Returns true in the event of a collision
(define (collision-detected world)
  (or
   (collision-detected-wall (first (move-worm-helper world )))
   (collision-detected-worm (first (move-worm-helper world))  (world-worm world ))))


; Returns true if the worm has collided with itself.
(define (collision-detected-worm segment worm)
  (member? segment worm))


; helper function for collision detection. Operates directly
; on a worm, rather than world object.
(define (collision-detected-wall segment)
 (cond [(> 0        (segment-x-pos segment)) true]  ; exceeding left edge
        [(> 0       (segment-y-pos segment)) true]  ; exceeding top edge
        [(< WIDTH   (segment-x-pos segment)) true]  ; exceeding right edge
        [(< HEIGHT  (segment-y-pos segment)) true]  ; exceeding bottom edge
        [else false]))




; Draw our final scene with the worm departing the board
; Displays a "Game Over" type message. We should probably be calculating the
; width and height of the image to calculate the offsets, but it's simpler just
; to arbitrarily put it somewhere in the bottom right of the screen

(define (final-scene world)
  (draw-worm
   (place-image 
    (text
     (cond  ((collision-detected-wall (first (move-worm-helper world )))
             "worm hit border" )
            (else "worm hit worm"))       
     20 "red")
    (- WIDTH 100)
    (- HEIGHT 50)
    (empty-scene WIDTH HEIGHT))
   (world-worm world)))



; Draws the current world.
(define (show world)
  (draw-food
   (draw-worm (empty-scene WIDTH HEIGHT) (world-worm world))
   (world-segment world)))


; Move the worm in the current direction. Instead of changing the position of
; a single segment, now we add a segment to start of the worm (in the 
; current direction) and get rid of the end of the worm
(define (move-worm worm direction)
   (cons (new-segment (first worm) direction) (remove-last worm))
)


; helper method to DRY up code when calling this from a world object
(define (move-worm-helper world)
  (move-worm (world-worm world) (world-direction world)))


; return a new segment moved in 'direction' from the segment passed in
(define (new-segment segment direction)
    (make-segment  (+ (segment-x-pos segment)
                  (* WORM-MOVE (direction-x direction)))
               (+ (segment-y-pos segment)
                  (* WORM-MOVE (direction-y direction)))))




; remove the last worm segment. this is a pretty unoptimised function. just
; reverse the list, grab the rest of it, and reverse it again to get it the
; correct order.
(define (remove-last worm)
   (reverse (rest (reverse worm))))






; This has changed for question 174 - we now need to check for food 
; collisions on each clock tick.
; On each clock tick, move the world further in time. This is a new function
; that takes part of the responsibily of the old move-worm function. It just
; moves the worm and creates a new world based on it.
(define (progress-world world)
  (eat-food
   (make-world
    (move-worm  (world-worm world)
                (world-direction world))
    (world-direction world)
    (world-segment world))
  ))


; handle keyboard events.
(define (handle-key-events ws ke)
  (cond
    [(string=? "left" ke)  (change-direction ws LEFT)]
    [(string=? "right" ke) (change-direction ws RIGHT)]
    [(string=? "up" ke)    (change-direction ws UP )]
    [(string=? "down" ke)  (change-direction ws DOWN)]
    [else ws]
  ))


; create a new world with the direction the worm is travelling in changed.
(define (change-direction world  direction)
  (make-world (world-worm world) direction  (world-segment world)))




; This is the big bang function that drives the game.
(define (worm-main rate)
  (big-bang (make-world WORM
                        (make-direction 1 0)
                        (make-segment 300 100)
                        )
            (to-draw    show)
            (stop-when  collision-detected final-scene)
            (on-key     handle-key-events)
            (on-tick    progress-world rate) ))


; start the game off!
(worm-main 0.1)




# TESTS


; Test when we move the worm up, a new segment is added to the start and removed
; from the end.
(check-expect (move-worm WORM LEFT)
              (list
               (make-segment (- 100 WORM-MOVE) 100)
               (make-segment 100 100)
               (make-segment 100 80)))


; Check the remove-last function removes the last segment correctly
(check-expect (remove-last WORM)
              (list (make-segment 100 100)
                   (make-segment 100 80)))


; Test that new segment returns a new segment in the correct position
; (as per the current direction)
(check-expect (new-segment  (make-segment 100 100) UP)
              (make-segment 100 (- 100 WORM-MOVE)))






; exceeding the bottom of the screen


;; Test our worm draws as we expect it.
(check-expect (draw-worm (empty-scene 200 200) WORM)
              (place-image SEGMENT 100 100
                           (place-image SEGMENT 100 80
                           (place-image SEGMENT 100 60 (empty-scene 200 200)))))
             


; Test our worm moves in the direction we expect
(check-expect (move-worm (list (make-segment 50 50)) DOWN)
              (list (make-segment 50 70)))
(check-expect (move-worm (list (make-segment 50 50)) UP)
              (list (make-segment 50 30)))
(check-expect (move-worm (list (make-segment 50 50)) LEFT)
              (list (make-segment 30 50)))
(check-expect (move-worm  (list (make-segment 50 50)) RIGHT)
              (list (make-segment 70 50)))

Exercise 170: Design an interactive GUI rogram that continually moves a one-segment worm...

 Design an interactive GUI program that continually moves a one-segment worm and enables a player to control the movement of the worm with the four cardinal arrow keys. Your program should use a red disk to render the one-and-only segment of the worm. For each clock tick, the worm should move diameter.

Download the complete source for this article here.


I  enjoyed this exercise - it was interesting to see how to develop this question. The main difficulty I faced was finding concise documentation on how the big-bang function works. This is the main function that drives these "world" exercises. It's heavily documented within the racket documentation, but in a very dry manner that just lists the individual methods, but doesn't describe clearly how to put every thing together. With the HTDP2e book, it's documented well, but in a very scattered manner over several chapters. Eventually I found  this pdf (provided by the same authors) that gave much in the way of needed detail.

The concept I was missing was the 'world' data structure provided by the first argument to big-bang. This is the main  'world scene' object -  a data structure containing the dynamic (changing) aspects of the game world. This is passed automatically into each of the given callback functions you supply (along with possibly other arguments) and is expected to be returned from each of these functions - possibly with a new world state.

As this is a functional program, we are not changing this world data structure, but rather  creating an entirely new representation of the world each time.

Game constraints and constants

We make the worm size configurable here and when we move the worm it will be by the amount specified. The hints provided in the question suggest two different means to keep track of the worm - via a physical or logical location and suggests that one of these may be easier than the other in terms of changing the size of the worm or the game board. They both seem fairly similar to me in this regard, but I have chosen a physical representation as it seems much easier in terms of drawing the wold. The logical position would need to be converted back to a physical position at the time of drawing.

(define WORM-SIZE 10)
(define WORM-MOVE WORM-SIZE)


(define WIDTH 800)  ; width of the game
(define HEIGHT 500) ; height of the game


; this struct will hold the current position of the struct. I imagine later 
; on it will end up holding a list of the tail of the worm
(define-struct worm(x-pos y-pos))


; a struct to hold the direction the worm currently moving in. 
(define-struct direction(x y))


; To save repeating these directions in tests and code, we'll define them here
(define DOWN  (make-direction 0 1)) 
(define UP    (make-direction 0 -1)) 
(define RIGHT (make-direction  1 0)) 
(define LEFT  (make-direction -1 0)) 

This is a key struct - this is our world data-structure and will be passed around to all the functions so that they can take appropriate action and modify the world as needed. Currently it just holds the worm position and direction, but later it will hold the positions of the worm food.

(define-struct world(worm direction))

Functions 

; This function draws a worm in its current location on the screen
(define (draw-worm background worm) 
  (place-image (circle WORM-SIZE "solid" "red") 
               (worm-x-pos worm) 
               (worm-y-pos worm) 
   background)) 





; This draws the current world. Currently it is just drawing the worm but this 
; will probably be extended to drawing other things such as food and obstacles.
(define (show world)
  (draw-worm (empty-scene WIDTH HEIGHT) (world-worm world)) )






The move-worm function is called on each clock tick and moves the worm in the last direction that was pressed. This function takes in a world and returns  a new world with the worm moved along the current direction. The direction doesn't need to change so isn't changed. To determine the new position of the worm, we multiply our direction for both the x and the y axis by the distance the worm should move and add this to the current position. As this x and y vector will be either -1, 0 or 1, this will either subtract, leave unchanged or add the worm travel distance to the  current position.



; This functions takes in a world and constructs a new world with the worm
; moved along the current direction.

(define (move-worm world)
  (make-world 
   (make-worm  (+ (worm-x-pos (world-worm world)) 
                              (* WORM-MOVE (direction-x (world-direction world))))
                (+ (worm-y-pos (world-worm world)) 
                              (* WORM-MOVE (direction-y (world-direction world)))))
   (world-direction world)))




The handle-key-events functions handles keyboard events. This is a very simple function that just calls the change-direction function with a new direction vector. This returns the new world state as returned by change-direction.


; Handle key board events and return a new world state.
(define (handle-key-events ws ke)
  (cond
    [(string=? "left" ke)  (change-direction ws LEFT)]
    [(string=? "right" ke) (change-direction ws RIGHT)]
    [(string=? "up" ke)    (change-direction ws UP )]
    [(string=? "down" ke)  (change-direction ws DOWN)]
    [else ws]
  ))




The change-direction function creates a new world with the direction the worm is travelling in changed to represent the key just pressed. This function doesn't do much - it just creates a new world struct and returns it. This could have been done in the handle-key-events function, but having a named function for it makes things clearer.


; Return a new world with the direction changed to match the direction passed in.
(define (change-direction world  direction)  
  (make-world (world-worm world) direction)) 




The worm-main function is the function that will start our game running. It calls the big-bang function with the initial state of the world, and details the call-back functions required to make the game work.
The initial state of our world is an empty scene with a worm stationed in the center moving to the right. We supply:

•  a function show that will draw our world as it currently stands
•  a function handle-key-events that will change the direction the worm is travelling
•  a function on-tick that will move the worm one unit in the current direction on each game tick

(define (worm-main rate)
  (big-bang (make-world (make-worm (/ WIDTH 2)  (/ HEIGHT 2))
                        (make-direction 1 0))
            (to-draw show) 
            (on-key handle-key-events)
            (on-tick move-worm rate) ))




This start the game off! 10 movements a second seems to provide a reasonable speed for the current worm/world size


(worm-main 0.1)

Tests

; Test our worm draws as we expect it.
(check-expect (draw-worm (empty-scene 100 100) (make-worm 50 50))
              (place-image (circle WORM-SIZE "solid" "red") 50 50 (empty-scene 100 100)))
   


; Test our worm moves in the direction we expect
(check-expect (move-worm (make-world (make-worm 50 50) DOWN))
              (make-world (make-worm 50 60) DOWN))
(check-expect (move-worm (make-world (make-worm 50 50) UP))
              (make-world (make-worm 50 40) UP))
(check-expect (move-worm (make-world (make-worm 50 50) LEFT))
              (make-world (make-worm 40 50) LEFT))
(check-expect (move-worm (make-world (make-worm 50 50) RIGHT))
              (make-world (make-worm 60 50) RIGHT))


; Test our change-direction function changes the direction, but doesn't impact the postion
(check-expect (change-direction (make-world (make-worm 50 50) DOWN) UP)
              (make-world (make-worm 50 50) UP))
(check-expect (change-direction (make-world (make-worm 50 50) DOWN) RIGHT)
              (make-world (make-worm 50 50) RIGHT))