[racket] Doing collision detection in universe.ss

[Yaron Minsky]

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.

y
____________________
Racket Users list:
http://lists.racket-lang.org/users

[Stephen Bloch]

On Nov 27, 2012, at 8: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.

Right, and the question doesn't even make sense at the "image" level because images don't have locations.

One "purist" answer would be to write your own collision detection, based on whatever data type you're using for your model. If it has two fields "player-posn" and "monster-posn", you can do a distance formula calculation to find out how close those two points are to one another, and decide whether it's close enough to constitute a "collision". If it has a list of posns (or structs that contain posns), you can do that for each pair of elements in the list.

But that's a pain, however much one might learn from the process. If you just want to get a game with collision detection up and running, it would be nice if the image and/or universe libraries provided some support. An easy example would be rects-intersect?: call it on the bounding rectangles of your two translated images, and it tells you whether they intersect. (A student could write that easily enough, and use it henceforth.) Spiffier, in case you wanted to treat irregularly-shaped objects properly, would be a function images-intersect? that takes in two translated images and tells whether there is a pixel location for which both have nonzero alpha channels.

How do you represent a "translated image"? It could be an image and a posn, or it could be just an image formed by place-image onto an all-transparent background.

> 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.

And vice versa, of course: there are lots of things that are easy in universe, but very difficult in Scratch.


Stephen Bloch
sbl...@adelphi.edu

[Jay McCarthy]

And if you don't want to write your own...

I have a Planet package or github repo for almost everything...

(old) slow functional physics in Racket ---
https://github.com/jeapostrophe/pfp/blob/master/example.ss

(old) interface to fast Chipmunk library ---
https://github.com/jeapostrophe/chipmunk/

my current system in pure Racket with a broad phase / narrow phase
distinction: https://github.com/get-bonus/get-bonus/tree/master/gb/physics

Personally, I think you should use this opportunity to teach your kid
the Pythagorean Theorem, like the Boostrap curriculum teaches:
http://www.bootstrapworld.org/materials/

Jay

--
Jay McCarthy <j...@cs.byu.edu>
Assistant Professor / Brigham Young University
http://faculty.cs.byu.edu/~jay

"The glory of God is Intelligence" - D&C 93

[John Clements]

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.

John

[John Clements]

Followup: I see that the "just-alpha" arg to "get-argb-pixels" is undocumented. Investigating....

John

[John Clements]

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

[Stephen Bloch]

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
sbl...@adelphi.edu

[Hendrik Boom]

On Tue, Nov 27, 2012 at 08:56:13PM -0500, 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.

There are two arts to collision detection: figuring out whether two
images collide (which gets trickier when they're in motion) and
organising all your objects so you don't have to test very many
combinations of them.

Both of these can get quite complicated, and are susceptible to
nontrivial, complicated, and often necessary efficiency improvements
depending on special properties of the game.

A one-size-fits-all solution may be good enough for tinkering with, but
serious use may well need serious hacking.

-- hendrik

[Yaron Minsky]

To be clear, I'm firmly interested in tinkering, which is why I'm
using universe.ss and image.ss.

I do think that a good design goal for Racket's kid-oriented libraries
would be to be feature compatible with Scratch. It would be great if
there were good ways of doing everything that Scratch can do, from
playing sounds to detecting collisions, to (more aggressively) on-line
hosting of the final result. I'd love it if Racket were strictly
better than Scratch for someone who really can figure out how to
program, but it's just not true now.

y

[Matthew Flatt]

For what it's worth

https://github.com/mflatt/scratchy

is an implementation of the Scratch sprite and evaluation model plus a
textual language. It has all of the drawbacks of Scratch --- mutation,
race conditions, and busy waiting --- without the nice graphical
syntax! It has a collision detector that's much like John's, but I
spent some time making it go faster. There's also a notion of "lands"
within a program.

I wrote Scratchy as an example of building languages in Racket for this
year's RacketCon.[*] I dream about a phase 2 where I figure out how to
change the evaluation model to something good and/or connect with
`2htdp/universe', but I don't see that happening soon.

[*] At the suggestion of my son. He's a Scratch fan, though he quickly
became frustrated by the lack of abstraction in Scratch, and I
don't know whether to be happy or sad that he's a 12-year-old who
understands the phrase "race condition". Scratchy has "lands" because
he wanted something like that for his game.

[Jay McCarthy]

General purpose use.

On Wed, Nov 28, 2012 at 5:38 AM, Yaron Minsky <ymi...@gmail.com> wrote:
> Is this oriented towards educational use, or is it a more
> general-purpose library?
>
> y

[Stephan Houben]

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 <bl...@adelphi.edu>

[Yaron Minsky]

Is this oriented towards educational use, or is it a more
general-purpose library?

y

On Tue, Nov 27, 2012 at 10:51 PM, Jay McCarthy <jay.mc...@gmail.com> wrote:

[Jens Axel Søgaard]

2012/11/28 Hendrik Boom <hen...@topoi.pooq.com>:

> There are two arts to collision detection: figuring out whether two
> images collide (which gets trickier when they're in motion) and
> organising all your objects so you don't have to test very many
> combinations of them.

Back in the summer holiday I played with 2d-range trees for the latter purpose.
I combined it with a partial port of chipmunk.

The code with a very small example is here:
https://github.com/soegaard/this-and-that/blob/master/snoopy/racket-chipmunk.rkt

The code isn't done. Writing code for the math library turned out to be
more interesting.

--
Jens Axel Søgaard

[Stephen Bloch]

On Nov 28, 2012, at 7:37 AM, Yaron Minsky wrote:

I do think that a good design goal for Racket's kid-oriented libraries
would be to be feature compatible with Scratch.  It would be great if
there were good ways of doing everything that Scratch can do, from
playing sounds to detecting collisions, to (more aggressively) on-line
hosting of the final result.  I'd love it if Racket were strictly
better than Scratch for someone who really can figure out how to
program, but it's just not true now.

I was playing with this, too, a year and a half ago (after watching one of Dan Garcia's typically-inspiring talks).  To my mind, the big thing missing from Scratch-based curricula was testing, because their uncompromisingly-imperative paradigm doesn't allow for any way to test a program other than "run it, watch it, and decide whether it looks right."  In order to fit real testing into a beginning curriculum, I wanted to make Scratch more functional.  Which gets difficult because anything you do with a sprite affects not only the sprite but the global graphics window.  And then life happened, and I didn't get back to the project. :-)

Keep in mind, however, that there are some tasks for which universe, image, et al are much better than Scratch, notably raster graphics.  The picturing-programs library includes "build-image" and "map-image", analogous to "build-list" and "map", which produce raster images by computing the color of each pixel independently and which can be used by students who haven't seen loops or recursion yet.  (These were inspired by a similar impulse to Yaron's above: I wanted to beat the Python-first curricula at their own game, and many Python-first curricula introduce nested for-loops early in order to process images pixel by pixel.)

Stephen Bloch

sbl...@adelphi.edu

[Stephan Houben]

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 <bl...@adelphi.edu <mailto:bl...@adelphi.edu>>

> sbl...@adelphi.edu <mailto:sbl...@adelphi.edu>

[Shriram Krishnamurthi]

Yaron, this summer my students, Kathi Fisler, and I built a block-based, functional language with types (expressed as colors) and testing. It runs in the browser, uses the WeScheme runtime and can express most Bootstrap programs.

It needs more polish before we can release it to the world. We would be happy to give previews to anyone who wants to see them.

--
Sent from phone. Please pardon terseness and mistakes.

[Prabhakar Ragde]

Shriram wrote:

> Yaron, this summer my students, Kathi Fisler, and I built a block-based,
> functional language with types (expressed as colors) and testing. It runs
> in the browser, uses the WeScheme runtime and can express most Bootstrap
> programs.
>
> It needs more polish before we can release it to the world. We would be
> happy to give previews to anyone who wants to see them.

If this is DrBlocket, then Danny Yoo gave a 10-minute talk on it at
RacketCon this October; slides and video are here:

http://con.racket-lang.org

--PR

[Yaron Minsky]

This sounds ideal.  I'll check it out.

[Yaron Minsky]

This sounds great.  I'm curious how it compared to snap, which is scratch like, but with more abstraction capabilities and more FP mixed in.

One key thing to aim for I believe is the online component. This is where scratch really shines. They manage to male coding a highly social activity, which makes it much more engaging.

I'd love to beta test with my kids and report back.

y

[Yaron Minsky]

Ah, looking at scratchy more closely, I now think I understand it.
It's neat, but it's not quite what I'm looking for. In particular, I
was looking for a set of libraries that made the kinds of things one
can do in scratch easy to do. But scratchy is its own little
language, and doesn't give you access to lambda abstractions or other
tools of the trade of Racket.

That said, the functionality is all there, so maybe I can bend it to
my will somehow...

y

[Matthew Flatt]

Right --- you don't want `#lang scratchy'. The `scratchy/runtime'
library might be useful.

[Hendrik Boom]

On Wed, Nov 28, 2012 at 02:26:56PM +0100, 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

When the situation gets intense (i.e., lots and lots of objects) one of
the big wins is not even to prefilter with bounding boxes, but to find
ways of sorting objects by location (bearing in mind they aren't point
masses) and managing never to even consider objects that are nowhere
near each other.

Sometimes the most efficient way to accomplish something is not to do
it.

-- hendrik