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

From: Stephan Houben (stephanh42 at gmail.com)
Date: Wed Nov 28 08:26:56 EST 2012

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>

>
> 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
>
>
> ____________________
>   Racket Users list:
>   http://lists.racket-lang.org/users
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20121128/09666c42/attachment-0001.html>

Posted on the users mailing list.