Search Unity

  1. We want you to join us at GDC this year! Take a peek at all of the events we will be hosting during the week of GDC.
    Dismiss Notice
  2. Tell us about your experience here and you’ll get early access to the 2018 Game Studios report + more goodies.
    Dismiss Notice
  3. Unity 2017.3 has arrived! Read about it here.
    Dismiss Notice
  4. Want to see the most recent patch releases? Take a peek at the patch release page.
    Dismiss Notice
  5. We've closed the job boards. If you're looking for work, or looking to hire check out Unity Connect. You can see more information here.
    Dismiss Notice

Thoughts about how to do Scratch-style collision detection?

Discussion in '2D' started by JoeStrout, Feb 13, 2018.

  1. JoeStrout

    JoeStrout

    Joined:
    Jan 14, 2011
    Posts:
    6,080
    I'm playing around with making an educational programming environment for kids coming from Scratch. So I'd like to recreate the semantics of that environment as much as possible.

    Most of it is pretty easy... except for collision detection. Scratch has basically three collision check methods:
    1. if touching <sprite>: checks whether any non-transparent pixel of this sprite is touching any non-transparent pixel of another sprite. But both sprites can be arbitrarily scaled and rotated.
    2. if touching <color>: checks whether any non-transparent pixel of this sprite is touching a pixel of the specified color, whether that is in the background or from some other sprite.
    3. if color <color1> is touching <color2>: checks whether there is any pixel of this sprite of color color1 that is touching the given color2 (in the background or from some other sprite), or vice versa.
    None of these would be too difficult if sprites weren't rotated and scaled... but since they are, I'm at a bit of a loss as to how to implement them in any reasonably performant way.

    Maybe we actually make a pixel buffer the size of the screen (or, perhaps, some bounding area around the sprite), draw the background and any other sprites in the area into it, and then draw our sprite with a custom shader that checks the contents of the pixel buffer as it draws? But how would we get the result of this test back out to the main code?

    Or maybe there's a better approach I'm overlooking?
     
  2. sngdan

    sngdan

    Joined:
    Feb 7, 2014
    Posts:
    429
    I did a pixel collision a while back and as far as I recall, it should handle rotation - but I did not care about scale, so that would need some adjustment. I implemented this over a tile map (background - also sprites) and cars (other sprites).

    It basically goes like this
    - find intercepting box of sprite textures (coordinate + bounds based)
    - read textures of intercepting box + compare pixel colors
    - i guess for scale one would need to read the pixels multiple times - but how to deal with antialias, etc. ?
    - how many objects are you talking about? not sure if this is better done on GPU or CPU
     
  3. JoeStrout

    JoeStrout

    Joined:
    Jan 14, 2011
    Posts:
    6,080
    Yeah, it's really the scaling that makes this hard. There is no antialiasing, but a sprite could be scaled up or down arbitrarily — turning a pixel into an arbitrary (non-axis-aligned) square of color, or (if scaling down) mixing several pixels down into one.

    As for how many objects, it's hard to say... most Scratch projects probably have no more than 100 or so sprites, because that's about all it can handle. Typical projects have much fewer. And of course you would always do AABB tests to filter out all the sprites that couldn't possibly be involved in the collision check.
     
  4. JoeStrout

    JoeStrout

    Joined:
    Jan 14, 2011
    Posts:
    6,080
    Thinking about it a bit more... I've noticed that the "touching color" test only checks the topmost color (excluding the sprite that's doing the test). So it really seems like drawing into a buffer is the way to go, for all three cases:
    1. if touching <sprite>: start with an empty buffer; draw the other sprite; then draw this sprite, and if at any point the pixel we're about to draw over is nonempty, return true.
    2. if touching <color>: draw the background and all relevant sprites into the buffer; then draw this sprite, and if at any point the pixel we're about to draw over is the specified color, return true.
    3. if color <color1> is touching <color2>: draw the background and all relevant sprites into the buffer; then draw this sprite, and if at any point the pixel we're over and the color we're about to draw match color1 and color2, return true.
    But how would I actually do that in Unity, short of writing my own rasterizer? I feel like it's something I ought to be able to do with a custom shader or camera or something. But it's got to be able to return a value (and perhaps even bail out early when it finds a hit). How do you do that?
     
  5. sngdan

    sngdan

    Joined:
    Feb 7, 2014
    Posts:
    429
    Let me see if I can find something later...I kind of know that I will find the version without rotation because I used it in a prototype. The one with rotation I think aligned one sprite by axis and then looked for the intersection box, so for that sprite you have to use a transparent texture and then determine which positions are read from the sprite texture.

    The actual collision detection is
    - calculate interception box (use i.e. sprite SpriteRenderer.bounds - this should also work for scaling but the trick is later how to read the pixels from the sprite texture)
    - Color[] sprite1 = GetPixels (interception box)
    - Color[] sprite2 = GetPixels (interception box) // or an algorithm that creates this in case the sprite is not axis aligned
    - for (int i = 0; i < sprite1.Length; i++)
    - if (sprite1.a !=0 && sprite2.a !=0) return true

    edit: not sure why but it is not taking [ i ] after sprite1 and sprite 2 in the loop
     
  6. JoeStrout

    JoeStrout

    Joined:
    Jan 14, 2011
    Posts:
    6,080
    Don't worry about the [ i ]... that's the local markup for italics, so yeah, it causes some grief.

    But anyway, I totally get what you're doing there, but I don't think it's going to work in the case of scaled/rotated sprites, at least not in any simple manner. It also doesn't really handle the "touching color" case which is very commonly used.

    As this has been rolling around in my head all morning, I'm starting to lean towards this approach:
    • make a RenderTexture the size of our sprite renderer bounds, and draw either the other sprite of interest, or the background plus all other sprites into it
    • make another RenderTexture of the same size, and draw our sprite into it
    • iterate over the pixels of these two textures, comparing them appropriately
    It's that last step that makes me cringe -- Scratch programmers often use very large sprites, so we would be potentially be looping (in C#) over thousands of pixels.

    On the other hand, once we've got it to that point, it is what my wife calls an "embarrassingly parallel" problem; every pair of pixels can be checked independent of the others. So it ought to be ideal for putting on the GPU. Especially if we can keep the render textures there (where presumably they were just rendered to), rather than moving them to main memory. That level of GPU shenanigans is will outside my experience base... but I suppose that's part of the fun!
     
  7. sngdan

    sngdan

    Joined:
    Feb 7, 2014
    Posts:
    429
    - I guess I do not understand the touching color case (I assume the background is a sprite / texture) so in my understanding it’s the same as sprite - sprite
    - yes, render textures simplify the rotation/scale handling but would you not need one for each collision pair? If you fill one up with all other items, you could determine if there was a collision but not with what? (It feels like you would be back to the approach I outlined above, but instead of manually calculating the texture / color array you use the renderer)
    - gpu would be interesting in particular since unity opened up this interface - it’s just something I am not experienced in and I also wonder how to get back the collision entities

    Would be great if you could update this post with your findings, it’s a topic that interests me in general (i started programming on c64, where you had hardware support for this)
     
  8. JoeStrout

    JoeStrout

    Joined:
    Jan 14, 2011
    Posts:
    6,080
    OK, here's what I've come up with... just hacked out, still needs cleaned up, etc... but it works.

    Code (CSharp):
    1.     public bool IsTouchingColor(Color32 targetColor, int tolerance=4) {
    2.         SpriteRenderer rend = GetComponent<SpriteRenderer>();
    3.         Bounds bounds = rend.bounds;
    4.        
    5.         RenderTexture rtex;
    6.         if (debugRendTex != null) rtex = debugRendTex;
    7.         else rtex = RenderTexture.GetTemporary(
    8.             Mathf.CeilToInt(bounds.extents.x*2),
    9.             Mathf.CeilToInt(bounds.extents.y*2),
    10.             16,         // do we actually need a depth buffer?!
    11.             RenderTextureFormat.ARGB32);
    12.        
    13.         testCamera.CopyFrom(Camera.main);
    14.        
    15.         Vector3 pos = transform.position;
    16.         pos.z = testCamera.transform.position.z;
    17.         testCamera.transform.position = pos;
    18.        
    19.         testCamera.aspect = (float)rtex.width / rtex.height;
    20.         testCamera.orthographicSize = rtex.height/2;
    21.        
    22.         testCamera.targetTexture = rtex;
    23.         testCamera.cullingMask &= ~LayerMask.GetMask("CollisionTestSubject");
    24.            
    25.         // disable this object, and render everything else
    26.         int origLayer = gameObject.layer;
    27.         gameObject.layer = LayerMask.NameToLayer("CollisionTestSubject");
    28.         testCamera.Render();
    29.        
    30.         // Copy the rendering into something we can access
    31.         Texture2D tex = new Texture2D(rtex.width, rtex.height, TextureFormat.ARGB32, false);
    32.         RenderTexture.active = rtex;
    33.         tex.ReadPixels(new Rect(0, 0, rtex.width, rtex.height), 0, 0, false);
    34.         RenderTexture.active = null;
    35.                
    36.         Color32[] targetPixels = tex.GetPixels32();
    37.        
    38.         // Now, render again with just our own sprite.
    39.         testCamera.cullingMask = ~testCamera.cullingMask;
    40.         testCamera.Render();
    41.         RenderTexture.active = rtex;
    42.         tex.ReadPixels(new Rect(0, 0, rtex.width, rtex.height), 0, 0, false);
    43.         RenderTexture.active = null;
    44.        
    45.         Color32[] selfPixels = tex.GetPixels32();    
    46.        
    47.         // Check now for where we are touching the target color.
    48.         bool result = false;
    49.         int count = selfPixels.Length;
    50.        
    51.         for (int i=0; i<count; i++) {
    52.             if (selfPixels[i].a < 255) continue;    // not our pixel
    53.             Color32 c = targetPixels[i];
    54.             if (c.a < 255) continue;                // not a target pixel (nothing rendered here)
    55.            
    56.             // check for hitting target color
    57.             if (c.r == targetColor.r && c.b == targetColor.b && c.g == targetColor.g && c.a == targetColor.a) {
    58.                 result = true;
    59.                 break;
    60.             }
    61.            
    62.             if (tolerance > 0) {
    63.                 // OK, let's check for *almost* hitting the target color.
    64.                 int d = 0;        // manhattan distance
    65.                 d += (c.r > targetColor.r ? c.r - targetColor.r : targetColor.r - c.r);
    66.                 d += (c.g > targetColor.g ? c.g - targetColor.g : targetColor.g - c.g);
    67.                 d += (c.b > targetColor.b ? c.b - targetColor.b : targetColor.b - c.b);
    68.                 if (d < tolerance) {
    69.                     result = true;
    70.                     break;
    71.                 }
    72.             }
    73.         }
    74.        
    75.         gameObject.layer = origLayer;
    76.        
    77.         return result;
    78.     }
     
  9. sngdan

    sngdan

    Joined:
    Feb 7, 2014
    Posts:
    429
    Cool - I will look at this tomorrow, I will also try to dig out my old version.

    - did you check performance?
    - this algorithm is not being able to say who was the collision partner, just that a pixel of color is being touched - is this enough?
     
  10. JoeStrout

    JoeStrout

    Joined:
    Jan 14, 2011
    Posts:
    6,080
    No. I expect it to be rather poor, but I don't see how to improve it (short of delving into arcane GPU coding, which I'd like to do sometime, but not today).

    Yes, that's all Scratch provides, and it's what that user base expects. There will be a separate function for testing against a specific other sprite, though.
     
  11. sngdan

    sngdan

    Joined:
    Feb 7, 2014
    Posts:
    429
    Did not have time today but I found my old project, it has pixel collision between two sprites and works with rotated sprites. The script is messy though and needs some cleaning...overall it seems straight forward...
    - step1: box collision (rotated bounding boxes)
    - step2: pixel collision (walk through each pixel of sprite1 until collision detected, translate local coordinate of sprite1 pixel to local pixel coordinate of sprite2, compare colors)
    - i see also various optimizations like caching the sprite textures + i left some notes in the script for unimplemented ideas

    Let me know if this could interest you...and I will try to find some time this week to put this into something that is sharable. Looks to me like a pretty fast system, no need for GPU
     
  12. JoeStrout

    JoeStrout

    Joined:
    Jan 14, 2011
    Posts:
    6,080
    No, I don't think that's useful in my case because scaled sprites make that approach unworkable. Thank you though.
     
  13. sngdan

    sngdan

    Joined:
    Feb 7, 2014
    Posts:
    429
    I looked into it today and it was quite easy to make it work with scaled sprites as well...
    - :) well kind of...it's not 100% perfect...it can miss pixels if it transforms between differently scaled sprites (it will work in most cases but say at scale 3 of source texture and scale 1 of hit texture, it will walk through hit texture in 3 pixel steps)
    - i think the only way to fix this is to define the overlap box of the rotated sprites in world space and then step through the corresponding pixels of both textures (which at worst case rotation is double the amount of pixels to check * scale)

    I hate my fascination to this retro stuff but I can't help it, grew up with it. I might work on the pixel collision and check how performant it is. I sometimes wonder if there would be a wider interest for an integrated retro toolkit, things like
    - pixel perfect setup
    - pixel collision (a full fledged solution, with scaled & rotated, brute-force vs. special contact points, color vs transparency, etc.)
    - screen wrap with physics support
    - mod / tracker support (recall the other thread you started)
    - crt shader
    - old school effects like tech-tech, raster-bars, scroll-texts, etc.
     
    JoeStrout likes this.
  14. sngdan

    sngdan

    Joined:
    Feb 7, 2014
    Posts:
    429
    The approach with the overlap box works...
    - very simple script, needs speed optimization now (I have a number of ideas)
    - needs a thought on how to deal with "between pixel positions" for rotated sprites (sub pixel overlaps / gaps - false detections)
    - I promise myself to finally look into the exact pixel mapping / rendering of Unity - there is a potential 0.5 pixel offset that I want to look into
     

    Attached Files: