[racket] Doing collision detection in universe.ss (solution!)

On Nov 27, 2012, at 11:21 PM, John Clements wrote:

> 
> On Nov 27, 2012, at 11:04 PM, John Clements wrote:
> 
>> 
>> On Nov 27, 2012, at 5:56 PM, Yaron Minsky wrote:
>> 
>>> I've been weaning my son off of Scratch in favor of Racket, and trying
>>> to get him to write interactive games using universe.ss and image.ss.
>>> I'm wondering if anyone has suggestions for how to do things like
>>> collision detection.  image.ss has these nice first-class images, but
>>> I don't see a good way of querying two images to see if they overlap.
>>> 
>>> Has anyone else had luck in doing this?  universe has a nice
>>> programming model, but I've found it challenging to find simple ways
>>> of doing the kinds of things that Scratch makes easy.
>> 
>> Sounds like you want a raster model for images.  2htdp/image *almost kinda sorta* provides it, in that it exposes a "freeze" primitive that renders an image as a bitmap.  For images that are frozen, it should be possible to determine collision in a straightforward way. In fact, I suppose you could just use memoization to keep around a frozen version of any image.
>> 
>> It seems to me like the simplest interface would be one that accepted the two images and their relative positions, and returned #t if they overlap.
>> 
>> I think that the hardest part will be writing the collision detector, and I think even that part won't be too horrible; first do a fast check to see if their bounding boxes overlap. If they do, then blit the alpha channels of the overlapping region into a small fresh buffer, and ... um... yeah, that part gets a bit interesting. It's probably faster to pack the bitmask into 64-bit ints, and then just check the matching ints for non-zero-ness. Lots of fiddly details.
> 
> Followup: I see that the "just-alpha" arg to "get-argb-pixels" is undocumented. Investigating....

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

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?

John

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 4370 bytes
Desc: not available
URL: <http://lists.racket-lang.org/users/archive/attachments/20121128/c7d270c7/attachment.p7s>