On this page:
Warmup (20 minutes)
Balls that move and draw themselves (40 minutes)
Stationary obstacles (15 minutes)
User-controlled paddle (25 minutes)
More possibilities (ω minutes)
6.7

Lab 6 Entity-component-system

home work!

Purpose: To explore what can be done with structured data that contains functions.

Since we can treat functions just like any other ordinary value, we have the ability to make structures that contain functions. Instead of a handful of simple data-extracting functions like posn-x or first, these structures can come packaged with more complex behavior of their own. Today, we’ll use big-bang with a World where everything in it carries a few such functions. When we want to move everything, we don’t map a cond over our heterogeneous list. Instead, we’ll ask each thing in the list to move itself if it can. By not depending on any details other than whether something can move, our world-moving function is ready to adapt to a newer, broader data definition that we might come up with later.

Warmup (20 minutes)

; A [Maybe T] is one of
; - T      meaning we produced this T
; - OOPS   meaning we failed to produce a T
(define-struct missing ())
(define OOPS (make-missing))

Exercise 1 Write the template for a [Maybe T]. It should use the T template. (Hint: What predicate will return true for OOPS and nothing else?)

We can use Maybe for working with structures that might not contain what we’re looking for. If someone asks you to choose something vegan at a pizzeria, the answer is probably "there isn’t any." Here’s some structured data, which holds a collection of "keys" and an associated "value" for each one.

; An [AList K V] ("association list") is a [Listof [List K V]]

Here are a few useful functions for working with ALists:

Sample Problem Design the function lookup, which takes a K and an [AList K V] and returns the (first) V paired with that K, if there is one.
; Look through an [AList K V] to find the V that goes with a K
; K [AList K V] -> [Maybe V]
(check-expect (lookup 2 '((3 a) (5 b) (2 d))) 'd)
(check-expect (lookup 2 '((3 a) (5 b))) OOPS)
(define (lookup k pairs)
  (cond [(empty? pairs) OOPS]
        [(equal? k (first (first pairs))) (second (first pairs))]
        [else (lookup k (rest pairs))]))

Sample Problem Design the function has-key?, which takes a K and an [AList K V] and says whether K appears as a key in the AList.
; Look through an [AList K V] to see if K is present
; K [AList K V] -> Boolean
(define (has-key? k pairs)
  (ormap (λ (pr) (equal? k (first pr))) pairs))
(check-expect (has-key? 2 '((3 a) (5 b) (2 d))) #true)
(check-expect (has-key? 2 '((3 a) (5 b))) #false)

Sample Problem Design the function replace, which takes a K, a V, and an [AList K V] and produces an AList like the original but where the K is paired with the new V instead of the old one. If it wasn’t there to begin with, then add it as a new association pair.
; Go inside a [Listof [List K V]], and replace the V belonging to a K, or add
; the new pair if it wasn't there before.
; [Listof [List K V]] K V -> [Listof [List K V]]
(define (replace k v pairs)
  (cond [(empty? pairs) `((,k ,v))]
        [(equal? k (first (first pairs))) (cons `(,k ,v) (rest pairs))]
        [else (cons (first pairs) (replace k v (rest pairs)))]))
(check-expect (replace 2 'q '((3 a) (5 b) (2 d)))
              '((3 a) (5 b) (2 q)))
(check-expect (replace 2 'q '((3 a) (5 b)))
              '((3 a) (5 b) (2 q)))

When we finally get to big-bang, we’ll have different kinds of "Entities" moving around in the world, but some things stay still the whole time. Also, we have several kinds of things to draw onto the screen. Let’s not have our draw-world function get too hung up on details about what kind of Entities it’s drawing. All it really has to care about is whether each Entity can be drawn at all. We’ll represent drawability as an Operation stored in an AList:
; An [Operation Y ... Z] is a [List Symbol [SELF Y ... -> Z]]
; where the SELF is a [Listof Operation] that contains this Operation
; 
; An Entity is a [Listof Operation]
; 
; A Drawable is an Entity that includes a
; [List 'draw [Drawable Image -> Image]]
So a Drawable contains instructions on how to draw itself onto some background scene, but it needs some way to access the rest of its own data. A circle can’t draw itself in the right place in a scene without at least knowing its own location! Here’s a simple example, where we’re stuck drawing in the same place all the time:
; A blank canvas for drawing on
(define WIDTH 400)
(define HEIGHT 300)
(define canvas (empty-scene WIDTH HEIGHT))
; [List ['draw [SELF Image -> Image]]]
; Draws itself as a radius 10 orange circle on the center of the scene
(define shape1
  `((draw ,(λ (me scene) (place-image (circle 10 'solid 'orange)
                                      (/ (image-width scene) 2)
                                      (/ (image-height scene) 2)
                                      scene)))))

Exercise 2 One thing we’re going to do over and over is try to call a function that’s inside an Entity. The first input we pass to that function will be the list itself. The rest of the input will have to come to us as a list. Write the function call with signature [Listof [Operation Y ... Z]] Symbol [List Y ...] -> Z. It should be usable like (call shape1 'draw (list canvas)). In order to write this, you will probably need to read about apply.

Sample Problem Make a Drawable that’s like shape1 but looks up its own location to decide where to place itself.

; [List
;  ['loc  [SELF -> Posn]]
;  ['draw [SELF Image -> Image]]]
; Draws itself as a radius 10 orange circle on the center of the scene
(define shape2
  `((loc  ,(λ (me) (make-posn 34 56)))
    (draw ,(λ (me scene)
             (local [(define my-loc (call me 'loc '()))]
               (place-image (circle 10 'solid 'orange)
                            (/ (image-width scene) 2)
                            (/ (image-height scene) 2)
                            scene))))))

What we really want to be able to do is take a whole lot of Operation lists and draw only the ones that can be drawn. This requires trying to call a draw operation that might not be there. If an operation is missing, we’ll still produce some alternative result.
; Try to call an operation, but produce a chosen alternative result
; if the operation isn't in the list.
; [Listof [Operation Y ... -> Z]] Symbol [List Y ...] T -> Z ∪ T
(define (try ops sym args alternative)
  (if (has-key? sym ops)
      (call ops sym args)
      alternative))

Balls that move and draw themselves (40 minutes)

; A Ball is an Entity, specifically:
; [List
;  [List 'loc        [SELF -> Posn]]        Location, in screen coordinates
;  [List 'vel        [SELF -> Posn]]        Velocity, in pixels/tick
;  [List 'acc        [SELF -> Posn]]        Acceleration, in pixels/tick²
;  [List 'move       [SELF -> Ball]]        Update loc based on vel
;  [List 'accelerate [SELF -> Ball]]        Update vel based on acc
;  [List 'draw       [SELF Image -> Ball]]  Draw the Ball onto a scene
;  ...]
; (or some reordering of elements)
(define example-ball
  `((loc ,(λ (me) (make-posn 4 40))) ; starts at (4,40)
    (vel ,(λ (me) (make-posn 1 1)))  ; moves down 1, right 1
    (acc ,(λ (me) (make-posn 0 1)))  ; accelerates down 1 due to gravity
    ; Wishlist: More Operations for 'move, 'accelerate, 'draw
    ...))
 
; Add the respective components of two Posns (useful for computing a new
; location after moving or a new velocity after accelerating).
; Posn Posn -> Posn
(define (posn+ p1 p2) (make-posn (+ (posn-x p1) (posn-x p2))
                                 (+ (posn-y p1) (posn-y p2))))
(check-expect (posn+ (make-posn 3 5) (make-posn 2 10))
              (make-posn 5 15))
; Subtract the respective components of two posns
; Posn Posn -> Posn
(define (posn- p1 p2) (make-posn (- (posn-x p1) (posn-x p2))
                                 (- (posn-y p1) (posn-y p2))))
(check-expect (posn- (make-posn 3 5) (make-posn 2 10))
              (make-posn 1 -5))

Now we have a few functions to write: moving, accelerating, and drawing.

Sample Problem Building a new ball has to be done carefully. The amount of memory used when passing a function around as a value depends on what data has to be kept around in order to compute that function.

We might try something like this:
; Build a new ball with updated position
; Ball -> Ball
(define (expensive-move b)
  (replace
   'loc (λ (me) (posn+ (call b 'loc '()) (call b 'vel '())))
   b))
Now, an updated Ball with the new 'loc operation still needs to keep the old version of the Ball in order to known its own location. Imagine not knowing where you are unless you keep track of everywhere you’ve ever been!

Instead of making a function that builds a new Posn, we’ll make a new Posn and then build a function that returns it:
; Build a new ball with updated position
; Ball -> Ball
(define (move-ball b)
  (local [(define new-loc (posn+ (call b 'loc '())
                                 (call b 'vel '())))]
    (replace
     'loc (λ (me) new-loc)
     b)))

Alternatively, we could write a function that makes constant-valued functions for Operations that don’t depend on anything. We always compute a value before passing it into a function, so by the time field runs, we’re just giving it the actual Posn it should use, with no reference to the old ball.
; Build a function that always returns x
(define (field x) (λ (_) x))
; Build a new ball with updated position
; Ball -> Ball
(define (move-ball b)
  (replace
     'loc (field (posn+ (call b 'loc '())
                        (call b 'vel '())))
     b))

Exercise 3 Design the function accelerate-ball, which takes a Ball and produces a new Ball, with a different 'vel. Similar to move-ball, use the original Ball’s 'acc to determine the new Ball’s 'vel.

Exercise 4 Design the function make-ball, which takes Posns for the location, velocity, and acceleration, and an Image representing how the Ball should look when drawn. The Ball’s 'draw operation should place that input image at the Ball’s 'loc.

Exercise 5 Design the function draw-world, which takes a World, which is a [Listof Entity], and draws all of the drawable Entities onto canvas. Remember, an Entity does not have to have a 'draw Operation! Do you remember what function to use when you want to call an Operation that might not be there? Make sure you test your function on a world that includes a non-drawable.

Exercise 6 Design the function move*, which moves every movable Entity in the World (and keeps the non-movable ones as they were).

Exercise 7 Design the function accelerate*, which accelerates every acceleratable Entity in the World (and keeps the others as they were).

Exercise 8 Generalize move* and accelerate* into a single function, operate, but with the signature Symbol -> [World -> World].

Exercise 9 Try running a World with a few Balls in it.
(big-bang some-world
          [to-draw draw-world]
          [on-tick (compose (operate 'move)
                            (operate 'accelerate))])

Stationary obstacles (15 minutes)

; A Block is a [Listof Operation], specifically
; [List
;  [List 'top        [SELF -> Real]]         Y-coord of top edge
;  [List 'bottom     [SELF -> Real]]         Y-coord of bottom edge
;  [List 'left       [SELF -> Real]]         X-coord of left edge
;  [List 'right      [SELF -> Real]]         X-coord of right edge
;  [List 'draw       [SELF Image -> Image]]  Draw the Block onto a scene
;  [List 'collide    [SELF Ball -> Ball]]    Update a Ball if it collided
;  ...]
; (or some reordering of elements)
; Each Block represents a rectangular obstruction that balls might bounce
; off of. The 'top, 'bottom, 'left, and 'right operations return the
; locations of the Block's respective edges.
; The 'collide operation looks at a Ball and the Ball's previous location.
; If that ball's path made it cross one of the Block's edges, the location
; should be replaced with where the Ball would have bounced to, and the
; velocity should be reflected.

The purpose of a Block is to give a Ball something to bounce against. We need to extract a Ball’s location and velocity as well as the Block’s boundaries in order to determine whether the Ball collided with the Block (and if so, which side). Here’s a function (with lots of helpers) that will check whether a Ball collided with a Block. If so, the Ball’s horizontal or vertical speed gets reversed, and its position gets reflected across the Block surface that it hit.

; Collision check, replacing ball's position and velocity if needed
; Block Ball -> Ball
(define (block-ball-collision block ball)
  (local [(define current-loc  (call ball 'loc '()))
          (define last-loc     (previous-loc ball))
          (define top          (call block 'top '()))
          (define bottom       (call block 'bottom '()))
          (define left         (call block 'left '()))
          (define right        (call block 'right '()))
          ; Where does the current trajectory cross each block surface's plane?
          (define top-cross    (cross 'horiz top current-loc last-loc))
          (define bottom-cross (cross 'horiz bottom current-loc last-loc))
          (define left-cross   (cross 'vert left current-loc last-loc))
          (define right-cross  (cross 'vert right current-loc last-loc))]
    (cond [(and (crossed? posn-y last-loc current-loc top)
                (<= left top-cross) (< top-cross right)) ; top bounce
           (bounce 'horiz top ball)]
          [(and (crossed? posn-y current-loc last-loc bottom)
                (< left bottom-cross) (<= bottom-cross right)) ; bottom bounce
           (bounce 'horiz bottom ball)]
          [(and (crossed? posn-x last-loc current-loc left)
                (< top left-cross) (<= left-cross bottom)) ; left bounce
           (bounce 'vert left ball)]
          [(and (crossed? posn-x current-loc last-loc right)
                (<= top right-cross) (< right-cross bottom)) ; right bounce
           (bounce 'vert right ball)]
          [else ball])))
 
; Check whether a coordinate in a Posn crossed from one side of a threshold to
; the other (note: order matters we don't care if it crossed *from* the
; other side *to* the first side)
; [Posn -> Real] Posn Posn Real -> Boolean
(define (crossed? accessor lo hi threshold)
  (and (< (accessor lo) threshold) (<= threshold (accessor hi))))
 
; Determine where a Ball came from in the previous frame
; Ball -> Posn
(define (previous-loc b)
  (posn- (call b 'loc '()) (call b 'vel '())))
 
; An Orientation is one of
;  - 'horiz
;  - 'vert
 
; Project a Posn (representing location) onto a line
; Orientation Real Posn -> Posn
(define (projection orient line p)
  (cond [(symbol=? orient 'horiz) (make-posn (posn-x p) line)]
        [(symbol=? orient 'vert)  (make-posn line       (posn-y p))]))
 
; What's offset would move this Posn onto that line?
; Orientation Real Posn -> Posn
(define (proj-diff orient line p) (posn- (projection orient line p) p))
 
; Reflect a velocity across a horizontal or vertical line
; Orientation Posn -> Posn
(define (reflect-vel orient v)
  (cond [(symbol=? orient 'horiz) (make-posn (posn-x v)     (- (posn-y v)))]
        [(symbol=? orient 'vert)  (make-posn (- (posn-x v)) (posn-y v))]))
 
; Reflect a Ball's velocity and location across a line
; Orientation Real Ball -> Ball
(define (bounce orient line b)
  (local [(define current-loc (call b 'loc '()))
          (define loc-diff (proj-diff orient line current-loc))
          (define new-loc (posn+ current-loc (posn+ loc-diff loc-diff)))
          (define new-vel (reflect-vel orient (call b 'vel '())))]
    (replace 'vel (λ (_) new-vel) (replace 'loc (λ (_) new-loc) b))))
 
; Where does a trajectory cross a line?
; Orientation Posn Posn Real -> [Maybe Real]
(define (cross orient line start end)
  ; Instead of viewing Posns as "x and y,"
  ; we want to see them as "along and across"
  (local [(define posn-along   (if (symbol=? orient 'horiz) posn-x posn-y))
          (define posn-across  (if (symbol=? orient 'horiz) posn-y posn-x))
          (define start-across (posn-across start))
          (define end-across   (posn-across end))
          (define across       (- start-across end-across))]
    (if (= 0 across)
        OOPS ; cannot cross a line while moving parallel to it
        (local [(define start-along (posn-along start))
                (define end-along   (posn-along end))
                (define along       (- start-along end-along))
                (define direction   (/ along across))
                (define intercept   (- start-along
                                       (* direction start-across)))]
          (+ intercept (* direction line))))))

Exercise 10 Design the function make-block, which takes Reals for the top, bottom, left, and right edges of a block. We’ve given you the code you need for the 'collide Operation, but you’ll have to write the 'draw code yourself.

Exercise 11 Design the function collide*, which looks at every Entity with both 'loc and 'vel and tries to collide it with every Entity that has a 'collide Operation.

Exercise 12 Try running a World that contains Balls and Blocks.
(big-bang some-world
          [to-draw draw-world]
          [on-tick (compose collide*
                            (operate 'move)
                            (operate 'accelerate))])

User-controlled paddle (25 minutes)

; A Direction is one of 'left, 'still, 'right
; A Paddle is a [Listof Operation], specifically
; [List
;  [List 'width      [Paddle -> Natural]]       How wide is the Paddle
;  [List 'center     [Paddle -> Natural]]       X-coord of Paddle's center
;  [List 'direction  [Paddle -> Direction]]     Direction it's moving
;  [List 'draw       [Paddle Image -> Image]]   Draw the Paddle onto a scene
;  [List 'move       [Paddle -> Paddle]]        Update Paddle's position
;  [List 'collide    [Paddle Ball -> Ball]]     Update Ball if it collided
;  ...]
; (or some reordering of elements)
 
; How fast does a paddle move sideways
(define PADDLE-SPEED 4)
; Vertical extent of a paddle
(define PADDLE-THICKNESS 10)
; Height of paddle's bottom edge
(define PADDLE-BOTTOM (sub1 (image-height canvas)))
A Paddle is a movable thing for Balls to bounce against. It doesn’t exactly have a top, bottom, left, and right like a Block does, but it acts like a Block if a Ball hits it.

Exercise 13 Design the function paddle->block, which builds a Block that occupies the same space as the given Paddle. If you do this right, you can then
(define (paddle-ball-collision p b)
  (block-ball-collision (paddle->block p) b))

Exercise 14 Design the function move-paddle, which updates a Paddle’s 'center based on its current 'dir. A Paddle moves at PADDLE-SPEED pixels per tick when going 'left or 'right, and 0 pixels per tick when 'still.

Exercise 15 Design the function make-paddle, which takes a width, center coordinate, starting direction, and color, and produces a paddle.

Exercise 16 Design the function redirect*, which finds every Entity with a 'dir Operation and makes it match a given KeyEvent. "left" should make them all go 'left, "right" should make them all go 'right, and "down" should make them all hold 'still. Make sure you don’t put a 'dir on any Entity that didn’t have one to begin with.

(big-bang
 some-world
 [on-tick (compose collide* (operate 'move) (operate 'accelerate))]
 [on-key redirect*]
 [to-draw draw-world])

More possibilities (ω minutes)

We’ve built three kinds of Entities that will exist in our World: Balls, Blocks, and Paddles. We also have a notion of "components," small sets of Operations we expect to see in an entity. As a very simple example, the 'draw Operation forms a component on its own. That Operation itself is all that you need in order to draw some entity onto the scene. The ability to bounce off of something else is also a component, which consists of the 'loc and 'vel Operations. If we later came up with some new kind of entity that had location and velocity, a Block would already be able to bounce it! The Block doesn’t actually care whether it’s working on a Ball, as long as 'loc and 'vel are there.

We’ve also made several "systems" within our program, each of which is responsible for just one action associated with one component – the drawing system does not know or care about collision or movement. Once we got the systems built, all we had to do is compose them all together to get our World-updating function.

If you’ve made it this far, you can try adding another system for culling Balls that have drifted off the screen and cannot return (perhaps they’ve fallen below the bottom and are accelerating downwards). Which looping function would you use for this?

You could add a Portal entity that eats every Ball that gets close to one of its endpoints and spits it back out at the other end. Which Operations should a Portal have?

The entity-component-system arrangement is meant to be flexible about extending the design to include new features.