Scratch

MoreGamesNow · 2012-04-09 17:57:42

Does anyone know how Scratch checks if one sprite is touching another? Does it just run through every pixel and see if it is touching the other one? Seems that bit maps would be the most efficient actually (AND all of the pixels), is this what Scratch does? I'm just interested, because if there's one block I rely on the most, it is that one.

roijac · 2012-04-09 18:04:24

scratchspritemorph motionops touching:

MoreGamesNow · 2012-04-09 18:34:56

I'm pretty much illiterate when it comes to squeak, but I found the code if you want to translate:

Code:

touching: anObject
    "Answer true if any visible part of me touches a visible part of the given sprite."
    "Details: Currently uses the bounding box; should follow this up with comparison of visible pixels."

    | aSpriteOrSymbol stage intersection f1 f2 map oldVis |
    aSpriteOrSymbol _ self coerceSpriteArg: anObject.

    aSpriteOrSymbol = #mouse ifTrue: [
        (stage _ self ownerThatIsA: ScratchStageMorph) ifNil: [^ false].
        ^ self containsPoint: stage adjustedCursorPoint].

    aSpriteOrSymbol = #edge ifTrue: [^ self isOnEdge].

    (aSpriteOrSymbol isKindOf: self class) ifFalse: [^ false].
    (self isHidden not and: [aSpriteOrSymbol isHidden not]) ifFalse: [^ false].
    intersection _ self bounds intersect: aSpriteOrSymbol bounds.
    (intersection width > 0 and: [intersection height > 0]) ifFalse: [^ false].

    f1 _ Form extent: intersection extent depth: 2.
    f2 _ f1 deepCopy.
    oldVis _ self visibility. self visibility: 100.
    self drawOn: ((FormCanvas on: f1) copyOffset: intersection topLeft negated).
    self visibility: oldVis.

    oldVis _ aSpriteOrSymbol visibility. aSpriteOrSymbol visibility: 100.    
    aSpriteOrSymbol drawOn: ((FormCanvas on: f2) copyOffset: intersection topLeft negated).
    aSpriteOrSymbol visibility: oldVis.

    map _ Bitmap new: 4 withAll: 1.
    map at: 1 put: 0.  "transparent"
    f1 copyBits: f1 boundingBox from: f1 at: 0@0 colorMap: map.    "make mask with 0 where transparent, 1 elsewhere"
    f2 copyBits: f2 boundingBox from: f2 at: 0@0 colorMap: map.    "ditto for other sprite image"
    f2 displayOn: f1 at: 0@0 rule: Form and.                        "and the masks together"

    ^ (f1 tallyPixelValues at: 1) < (f1 width * f1 height)            "are any pixels of the result non-zero?"

I see the word "bitmap" though, so is it that?

bobbybee · 2012-04-09 18:37:33

It uses bounding-box collision. Try making a circle and star. See where the touching block reports a collision. It may not be perfect.

If you don't know, bounding-box collision is where they draw a box around 2 bitmaps. If the boxes intersect, it assumes there is a collision.

MoreGamesNow · 2012-04-09 19:38:30

It appears fine to me hmm

bobbybee · 2012-04-09 19:41:18

That's strange. It might use an optimized version of bounding-box. (like it uses a couple boxes)

ZeroLuck · 2012-04-10 04:37:51

I don't understand Squeak very well, but I think they are first testing collision with a bounding-box and after that they are creating two new image in which the sprites are painted.
Then they loop through every pixel.

roijac · 2012-04-10 04:43:45

looping through every pixel? no way, too slow
maybe making two sets of pixels and intersecting...

LS97 · 2012-04-10 05:09:45

I didn't look at the code above, but I assume it's the correct one and I'll go by memory. When I, at my time, was browsing the source for that same block, I found it does something really clever.

It first quickly does a bounding box check to see if the boxes around the two sprites intersect. If they don't, it returns false. Simple. If they do, it goes and checks the individual pixels.

First it takes the image of the first sprite (the portion that intersected sprite 2) and prints it onto an imaginary canvas -- but not as-is: that's what the "depth 2" is for. It makes a black and white image, with black being any colour and white being transparent.

Then it prints the other sprite in the position where the boxes intersected before, in a similar way (black and white). Then those pixels are copied onto a new bitmap, and the pixels are counted. And then it reports whether there are any pixels that are still 0. If there are no 0 pixels left, it means they're not touching, and vice versa.

(I edited the post because it wasn't very clear before, is it understandable now?)

Last edited by LS97 (2012-04-10 05:14:25)

MoreGamesNow · 2012-04-10 09:08:24

LS97 wrote:
Then it prints the other sprite in the position where the boxes intersected before, in a similar way (black and white). Then those pixels are copied onto a new bitmap, and the pixels are counted. And then it reports whether there are any pixels that are still 0. If there are no 0 pixels left, it means they're not touching, and vice versa.

So it basically preforms checks each pixel, only of the square that might be intersecting? Thats a nice way to optimize just the bitmap. Good idea to whoever came up with it.

Scratch

archived forums

#1 2012-04-09 17:57:42

The "touching []?" block

#2 2012-04-09 18:04:24

Re: The "touching []?" block

#3 2012-04-09 18:34:56

Re: The "touching []?" block

Code:

#4 2012-04-09 18:37:33

Re: The "touching []?" block

#5 2012-04-09 19:38:30

Re: The "touching []?" block

#6 2012-04-09 19:41:18

Re: The "touching []?" block

#7 2012-04-10 04:37:51

Re: The "touching []?" block

#8 2012-04-10 04:43:45

Re: The "touching []?" block

#9 2012-04-10 05:09:45

Re: The "touching []?" block

#10 2012-04-10 09:08:24

Re: The "touching []?" block

LS97 wrote:

Board footer