Scratch

bobbybee wrote:

I'm porting some Scratch projects to HTML5, and I can't seem to find a reasonable implementation of the if touching color block. (and a fast one, anyways)

well, that's the first thing i thought of, and probably isn't the fastest.
you take the square are where the sprite is without the sprite as an 2darray of colors, then generate a binary number where 1 is places with the wanted color, and 0 is any other color.
then you make the same except with the sprite and 1 is where the sprite's visible and 0 is where it's transparent.
then just take the two numbers and check if n1&n2 > 0 (binary AND)
if the sprite is touching you'll get yes, else no 

Hardmath123 wrote:

You need to use the getImageData function:

Code:

var imgd = context.getImageData(x, y, width, height);
var pix = imgd.data;

The actual algorithm will be quite expensive, I'm actually now curious how Scratch made it work... 

I think, essentially, it get any sprites under it and works out if the part of that sprite is under this one, If that sprite contains the colour that is you selected "true"

blob8108 wrote:

Hardmath123 wrote:

The actual algorithm will be quite expensive, I'm actually now curious how Scratch made it work... 

I saw a thread on exactly that recently, and now I can't find it.    Darn.

Grr.

bobbybee wrote:

I would like to note the code shown below is the code for the block. Could someone Squeak savvy translate it into something human-readable for me?

Code:

touchingColor: soughtColor
    "Answer true if any of my non-transparent pixels touch pixels of the given color in the world."

    | r myImage sensitivePixelsMask map imageBelowMe |
    r _ self bounds intersect: owner bounds.
    r area = 0 ifTrue: [^ false].

    "make a mask with 0 where transparent, 1 elsewhere"
    myImage _ self imageForm asFormOfDepth: 16.
    sensitivePixelsMask _ Form extent: myImage extent depth: 1.
    map _ Bitmap new: (1 bitShift: (myImage depth min: 15)).
    map atAllPut: 1.
    map at: (Color transparent indexInMap: map) put: 0.
    sensitivePixelsMask
        copyBits: ((r origin - self position) extent: r extent)
        from: myImage form
        at: 0@0
        colorMap: map.

    "grab an image of the world below me"
    imageBelowMe _ owner patchAt: r withoutWatchersAnd: self andNothingAbove: false.

    "intersect world pixels of the color we're looking for with sensitive pixels mask"
    map atAllPut: 0.  "clear map and reuse it"
    map at: (soughtColor indexInMap: map) put: 1.
    sensitivePixelsMask
        copyBits: imageBelowMe boundingBox
        from: imageBelowMe at: 0@0 clippingBox: imageBelowMe boundingBox
        rule: Form and
        fillColor: nil
        map: map.

    ^ (sensitivePixelsMask tallyPixelValues at: 2) > 0  "true if any pixels are 1"

Well from what I can see from the comments, what it does is make a mask of pixels that are transparent and those that aren't like this:


It then grabs an image of the rectangle of stage below the sprites costume.

It makes a difference of the two things (the colour that is being looked for on the world below it and the black mask) and checks to see if any of the pixels have been affected for example, this one would be affected:
it might for example, have had three points below it that were blue. When the differential was made, these points are shown up and scratch can tell this. It would in this case return true.

If the image still looked like the mask at the start:

the scratch program would know that there had been no blue values underneath and would return false.


Obviously the way that the scratch program does these things is quite complicated and if you would like more help understanding then feel free to ask.

Last edited by rookwood101 (2012-05-16 17:50:53)

I think he's indicating pixels which will change with the mask on them; namely the red ones. Am I right?

C'mon, applejack. Time to do what you do best, ideafy. ... um... For now, I can only think of scanning half of the pixles, and then scanning the next half if you find no say, red. Uhh... Just... pretend all the pixels under the sprite are numbers. Subtract the number  of the color you want from the stuff under sprite, and take away all the negatives. Then, take all the numbers, make them negative. Add the number of your color to all the numbers. if there are any 0s, yes, you are touching the color. Wait. That was stupid. It would take forever. I have a new idea. Keep a chart of how commonly all the colors are used in scratch (colors that have no data will be scanned for by checking every pixel the sprite is on. But if white is very common, it will check for that color every 20 pixels, or something. If it finds no white, it scans again, checking every 20 pixels, but starting on the second pixel, and so on. It would be cool to scan in a checker-boardish way for checking every other pixel. You would be more likely to encounter one color of pixel next to one of the same type. And if that color is isolated in a single pixel, it has a 50/50 chance of being found. Ask me to explain more, if you feel confused.

amcerbu wrote:

Computationally, I don't think there're many ways to avoid checking all the pixels in the image with all the ones below it.  Things are gonna get a little hairy if you have alpha support in your sprites (or anti-aliasing).  What rookwood101 said seems right. 

The one thing you can do to improve efficiency is to first identify where the pixels are of the specified color.  If they aren't within the bounding rectangle of the sprite, you know the sprite isn't touching that color.  I guess this is only efficient if there are fewer pixels of the color... oh well.

You can use two binaries and AND them 

amcerbu wrote:

@roijac- But that still requires you to check every pixel.  It may be that the implementation for the && operation is faster than others, but think about this.

Code:

// True is black, false is white



bool TouchingColor(bool[][] StageData, bool[][] SpriteData, int STARTINGX, int ENDINGX, int STARTINGY, int ENDINGY)
{
  // STARTINGX and STARTINGY correspond to stage coordinates.  
  for(int i = STARTINGX; i < ENDINGX; ++i)
  {
    for(int j = STARTINGY; j < ENDINGY; ++j)
    {
      if(StageData[i][j] && SpriteData[i - STARTINGX][j - STARTINGY]) return true;
    }
  }
  return false;
}

That's what I was afraid of.

Is there an efficient algorithm to find the bounds of a mask? Then you just need to check each of the pixels on the border.

I'm not sure we should consider "right under" as touching a color (though Scratch does).

veggieman001 wrote:

If it's porting a Scratch project, then wouldn't you want the same functionality?

More like writing a library that has functions for each block.

veggieman001 wrote:

bobbybee wrote:

veggieman001 wrote:

If it's porting a Scratch project, then wouldn't you want the same functionality?

More like writing a library that has functions for each block.

Ah. That's what I'm doing with Simplicity in Processing (and I'm nearly done with the first version too!) and it'll mostly work with HTML5 canvas as well. 

Cool.