1

I am working on a Racket program for a class and I am totally stumped as to how to implement one of the features.

The program uses Big-Bang and is supposed to implement a simple Space Invaders game.

I have everything working except one piece, and that is - how to handle the case when a missile collides with an invader. The reason I'm struggling is that I don't know how to write a function where I have two lists of arbitrary size, and I have to check the fields of each object in one list with each object in another list and remove an object in each list if they have the same values.

The world state is the game:

(define-struct game (invaders missiles tank))

where invaders and missiles are both lists.

To produce the next state of the game, I implement a function called 'tock'.

Normally, I would just do:

(define (tock s)
  (make-game (next-invaders (game-invaders s)) 
             (next-missiles (game-missiles s))
             (next-tank (game-tank s)))

But since the contents of the invaders and missiles lists might impact each other due to a collision, I can't simply update the positions independently and move on, I have to remove any collisions and then update the positions.

So I've tried:

(define (tock s)
  (make-game (check-collision (game-invaders s) 
                              (game-missiles s) 
                              (game-tank s))

But this makes check-collision take a tank, which it doesn't need.

(define (tock s)
  (make-game (next-invaders (game-invaders s) (game-missiles s)) 
             (next-missiles (game-missiles s) (game-invaders s)) 
             (next-tank (game-tank s))))

In this version, I have a function called next-invaders which takes the list of invaders and missiles, and a function called next-missiles which takes the list of missiles and invaders. The first function checks each invader against each missile, attempts to remove any collided invaders and returns the remaining invaders. The second function checks each missile against each invader and attempts to remove any collided missiles and returns the remaining missiles. The answers should be the same, but it's duplicate work and I'm worried about a possible race condition. I don't know how else to construct a single expression where one function only needs two fields and the other one needs three and I still wind up producing the next state of the game.

Here's an example of next-invaders. If there are no invaders, it does nothing. If there are invaders but no missiles, it just moves each invader (move-invader) and recursively calls itself to iterate through all invaders. If there are both missiles and invaders, then I check for a collision between the first invader in the list, and every missile in the list; so check collision is recursive.

(define (next-invaders loi lom)
  (cond [(empty? loi) empty]
        [(empty? lom) (move-invader (first loi) (next-invaders (rest loi) lom))]
        [(check_collision (first loi) lom) 
         (next-invaders (cons (rest loi) empty) lom)]
        [else
         (move-invader (first loi)
                       (next-invaders (rest loi) lom))]))

Is the 'answer' to check-collision the correct way to "remove" the collided invader from the list of invaders?

(define (check_collision i lom)
  (cond [(empty? lom) false]
        [(and (<= (- (missile-x (first lom)) (invader-x i)) HIT-RANGE)
              (<= (- (missile-y (first lom)) (invader-y i)) HIT-RANGE)) 
         true]
        [else (check_collision i (rest lom))]))

Is this the correct way to test each element of each list against one another?

Update: Still going in circles on this problem. check-collision works and invader-function works, but when I return to missile-function, I don't know how to indicate that a missile needs to be deleted in the case where there was a collision detected in invader-function.

(define-struct invader (x y dx))
;; Invader is (make-invader Number Number Number)
;; interp. the invader is at (x, y) in screen coordinates
;;         the invader along x by dx pixels per clock tick

(define-struct missile (x y))
;; Missile is (make-missile Number Number)
;; interp. the missile's location is x y in screen coordinates

(define-struct collision (invaders missiles))

(define (tock s)
  (make-game (handle-invaders (collision-invaders (next-invaders-and-missiles (make-collision (game-invaders s) (game-missiles s)))))
             (handle-missiles (collision-missiles (next-invaders-and-missiles (make-collision (game-invaders s) (game-missiles s)))))
             (handle-tank (game-tank s))))

(define (next-invaders-and-missiles c)
  (cond [(and (empty? (collision-invaders c)) (empty? (collision-missiles c))) (make-collision empty empty)]
    [(or (empty? (collision-invaders c)) (empty? (collision-missiles c))) (make-collision (collision-invaders c) (collision-missiles c))]
    [else
     (missile-function (make-collision (collision-invaders c) (collision-missiles c)))]))


;; Collision -> list Of Missiles
;; produce an updated listOf Missiles taking collisions into account
(define (missile-function c)
  (cond [(empty? (collision-missiles c)) (make-collision (collision-invaders c) empty)]
    [else
     (if (< (length (invader-function (first (collision-missiles c)) (collision-invaders c))) (length (collision-invaders c)))
         (make-collision (collision-invaders c) (remove (first (collision-missiles c)) (collision-missiles c)))
         (missile-function (make-collision (collision-invaders c) (rest (collision-missiles c)))))]))


;; Missile, listOf Invaders -> listOf Invaders
;; produce an updated listOf Invaders taking collisions into account
(define (invader-function m loi)
  (cond [(empty? loi) empty]
    [else
     (if (check-collision? (first loi) m)
         (remove (first loi) loi)
         (invader-function m (rest loi)))]))

;; Invader, Missile -> Boolean
;; produce true if the coordinates of a missile are within HIT-RANGE of     the coordinates of an invader
(define (check-collision? i m)
  (and (<= (- (missile-x m) (invader-x i)) HIT-RANGE) (<= (- (missile-y m) (invader-y i)) HIT-RANGE)))
Improve this question
2
  • One particular issue with collision detection is the order by which you iterate over objects: you generally do not want collision be dependant on the (arbitrary) order of elements in your lists. Typically, an arbiter function groups collisions as collision objects, and then the collision is resolved for a group of objects, to ensure determinism. That's probably not important in your case, however. Commented Oct 18, 2018 at 8:12
  • Which exact language are you using? Are you using Racket, Scheme, Beginning Student Language, Intermediate Student Language, or something else? Commented Oct 18, 2018 at 18:38

1 Answer 1

Reset to default
1

I haven't reviewed all the code, but the general solution is to have one function that takes the lists of missiles and invaders, checks for all the collisions, and then returns both updated lists by returning a pair of lists. So something like this:

(define (tock s)
  (let* [(next (next-invaders-and-missiles (game-invaders s) (game-missiles s)))
         (next-invaders (first next))
         (next-missiles (rest next))]
    (make-game next-invaders next-missiles (game-tank s))))

(define (next-invaders-and-missiles loi lom)
  ... ;; code that finds collisions and removes them from both lists
  (cons new-loi new-lom))
Improve this answer
Sign up to request clarification or add additional context in comments.

13 Comments

What does let* do? I've never seen that notation before. It looks like this is a way to call more than one function in a function, which I didn't know how to do.
It's like let, but it performs the bindings sequentially instead of in parallel. So the binding of next-invaders and nexxt-missiles can refer back to next.
If I didn't do that I'd have to use nested let, or bind next-invaders and next-missiles to dummy values and then reassign them with set!, or just use car and cdr in the call to make-game.
So, 'car' and 'cdr' have meaning in Racket? Those are new to me too. Also, I know how to check one item from loi against each item of lom, but i don't know how to check each item of loi against each item of lom.
julieb: car is like first, and cdr is like rest. Barmar: I think julieb is actually using one of the Racket student languages, like BSL or ISL. Those don't have set!, and they use first and rest instead of car and cdr.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.