[racket] Doing collision detection in universe.ss (related question)

From: Stephan Houben (stephanh42 at gmail.com)
Date: Wed Nov 28 14:49:40 EST 2012

Here is John's gist extended with
the method based on integer masks per scanline.

https://gist.github.com/4163396

Stephan

On 11/28/2012 2:26 PM, Stephan Houben wrote:
> Apart from introducing a bounding box check, I would
> suggest converting each scanline into a single exact integer
> with 1 bits corresponding to alpha unequal 0. Then for each scanline,
> you can use arithmetic-shift and bitwise-and, and then check the result for
> being non-zero.
>
> Stephan
>
>
> 2012/11/28 Stephen Bloch <bloch at adelphi.edu <mailto:bloch at adelphi.edu>>
>
>
>     On Nov 28, 2012, at 3:10 AM, John Clements wrote:
>
>      > Okay, the totally-dumb collision detection implementation was
>     shorter than expected; only 73 lines, including (light) testing.
>       Here's a link to that code:
>      >
>      > https://gist.github.com/4159778
>
>     Simple, straightforward.  I notice that your test cases use
>     "empty-scene", which raises another thought in my mind.
>
>     At SIGCSE a year or two ago, somebody (I think it was either Anne
>     Mulhern or Emmanuel Schanzer) suggested that students be taught to
>     build complex images not with the idiom
>              (place-image ... (place-image ... (place-image ...)))
>     but rather
>              (overlay        (place-image ...)
>                              (place-image ...)
>                              (place-image ...))
>     This imposes less of an ordering on the images -- in fact, if they
>     don't overlap, the order is completely irrelevant.  And it's easy to
>     insert or remove individual images from the stack of slides, because
>     that doesn't change the parenthesis nesting.  And it allows students
>     to decide where each image belongs, then forget about this decision
>     rather than keeping the location information around separately until
>     we do the place-image.
>
>     But for the latter to work, the various slides we're stacking up
>     need to be mostly transparent.
>
>     What would break if empty-scene defaulted to the color (make-color 0
>     0 0 0) rather than 'white (i.e. (make-color 255 255 255 255))?
>
>     I guess if people did this routinely, the bounding-box computation
>     John proposes adding to the collision-detection algorithm wouldn't
>     help.  And the implementation of overlay might need to be revised to
>     optimize for this case.
>
>      > It's observed to be darn slow: it took 4ms for collision
>     detection between the two 65x65 images. This could be acceptable for
>     a game with one or two collision detections per frame.
>      >
>      > You could improve this *hugely* just by doing some bounding-box
>     computation.
>      >
>      > Should I put this code in 2htdp/private/image-more.rkt somewhere?
>
>     Sounds useful to me.
>
>
>
>
>     Stephen Bloch
>     sbloch at adelphi.edu <mailto:sbloch at adelphi.edu>
>
>
>     ____________________
>        Racket Users list:
>     http://lists.racket-lang.org/users
>
>

Posted on the users mailing list.