How to do pixel-perfect collision detection of two partially transparent images

Question

So basically I to make so that when the two characters on the screen touch and someone presses a button it will take away their health. The only thing I don't know how to do is how to detect when they touch.

$(document).ready(function(){


var canvas = document.createElement("canvas");
var context = canvas.getContext("2d");
canvas.width = 1000;
canvas.height = 600;
document.body.appendChild(canvas);

var kGroundHeight = 500;

/*var upKey = 38;
var downKey = 40;
var leftKey = 37;
var rightKey = 39;
*/


var render = function() {
  gravity();
  gravity1();



  context.clearRect(0, 0, canvas.width, canvas.height);

    context.fillRect(0,kGroundHeight,canvas.width,10);

  context.drawImage(kirby, kirbyObject.x, kirbyObject.y);

    context.drawImage(link, linkObject.x, linkObject.y);

};




var main = function() {

  render();
  window.requestAnimationFrame(main);
};

main();
});




var linkReady = false;
var link = new Image();
link.onLoad = function() {

  linkReady = true;
};


linkObject = {};
link.src= "https://vignette1.wikia.nocookie.net/zelda/images/1/18/Link_(Sprite)_The_Legend_of_Zelda.png/revision/latest?cb=20130117162823";

linkObject.x = 200;
linkObject.y = 200;






var keys = {};




$(document).keydown(function(e) {
    console.log(e);

   move1(e.keyCode);

    if (keys[87] && keys[65]) {
       linkObject.y -=50;
       linkObject.x -=50;


    }else if(keys[87] && keys[68]){

      linkObject.y -=50;
      linkObject.x +=50;


    }else if(keys[83] && keys[68]){

      linkObject.y +=50;
      linkObject.x +=50;


    }else if(keys[83] && keys[65]){

      linkObject.y +=50;
      linkObject.x -=50;
    }

    keys[e.keyCode] = true;
}).keyup(function(e) {

   keys[e.keyCode] = false;



});

var upKey1 = 87;
var downKey1 = 83;
var leftKey1 = 65;
var rightKey1 = 68;
var attackKey1 = 75; 


var move1 = function(key) {

  if (key == upKey1) {
    linkObject.y -= 50;
  }else if(key == downKey1){

      var kGroundHeight = 500;

     if(linkObject.y + link.height ==  kGroundHeight){

      linkObject.y +=0;
    }else{

      linkObject.y +=50;

    }


    //console.log("down");
        console.log(linkObject.y);


  }else if(key == leftKey1){

    linkObject.x -=50;
  }else if(key == rightKey1 ){

    linkObject.x +=50;
  }
  // MORE DIRECTIONS!!!
};




var gravity1 = function() {
    var kGravityScale = 1;
  var kGroundHeight = 500;

  if (linkObject.y + link.height ==  kGroundHeight) {

    linkObject.y += 0;

  }else{
        linkObject.y += kGravityScale;
//console.log(link.width);
  }
};


var attack = function(a){



};



 var kGroundHeight = 500;


var keys = {};




$(document).keydown(function(e) {
    console.log(e);

   move(e.keyCode);

    if (keys[38] && keys[37]) {
       kirbyObject.y -=50;
       kirbyObject.x -=50;


    }else if(keys[38] && keys[39]){

      kirbyObject.y -=50;
      kirbyObject.x +=50;


    }else if(keys[40] && keys[39]){

      kirbyObject.y +=50;
      kirbyObject.x +=50;


    }else if(keys[40] && keys[37]){

      kirbyObject.y +=50;
      kirbyObject.x -=50;
    }

    keys[e.keyCode] = true;
}).keyup(function(e) {

   keys[e.keyCode] = false;



});


var kirbyReady = false;
var kirby = new Image();
kirby.onLoad = function() {
  kirbyReady = true;
};

kirbyObject = {};
kirby.src = "https://vignette3.wikia.nocookie.net/spritechronicles/images/5/5c/Kirby.png/revision/latest?cb=20101010225540";




kirbyObject.x = 300;
kirbyObject.y = 100;



var upKey = 38;
var downKey = 40;
var leftKey = 37;
var rightKey = 39;
var attackKey = 32; 



var move = function(key) {

  if (key == upKey) {
    kirbyObject.y -= 50;
  }else if(key == downKey){

      var kGroundHeight = 500;

     if(kirbyObject.y + kirby.height ==  kGroundHeight){

      kirbyObject.y +=0;
    }else{

      kirbyObject.y +=50;

    }


    //console.log("down");
        console.log(kirbyObject.y);


  }else if(key == leftKey){

    kirbyObject.x -=50;
  }else if(key == rightKey ){

    kirbyObject.x +=50;
  }
  // MORE DIRECTIONS!!!
};




var gravity = function() {
    var kGravityScale = 1;
  var kGroundHeight = 500;

  if (kirbyObject.y + kirby.height ==  kGroundHeight) {

    kirbyObject.y += 0;

  }else{
        kirbyObject.y += kGravityScale;

  }
};

Answer 1

Radial perimeter test

Fast almost pixel perfect collision cam be achieved by defining the shape of each sprite with a set of polar coordinated. Each coordinate describes the distance from the center (the center is arbitrary but must be inside the sprite) and direction from the center of the furthest most pixel from the center along that direction. The number of coordinates (n) is determined by the circumference of the outermost pixel. I do not know if this has been described before as i just thought of it now so its actual robustness will need testing.

The concept

The diagram below shows the basic concept.

The sprite (1.) Overlay the polar coordinates and the outer bounding circle (2.) Indexing each coordinate from 0-15 (3.) Extracting information required to check for collision. green (a) is the angular origin of each sprite and the yellow line P is the vector between A and B marked as angles from the angular origin (4.)

To get the coordinates you will need to access the pixel information, this can be done during production and added as code, or during game setup. It will result in a data structure something like

var sprite = {
    ...
    collisionData : {
        maxRadius : 128,
        minRadius : 20,
        coords : [128,30,50, ... ],
    }
}

snippet 1.

Now you have described each sprite as a set of polar coordinates you need to do the testing.

Assuming that the sprite will have a position (x,y in pixels) a rotation (r in radians) and a scale (s with square aspect).

positionData = {  // position data structure
   x : 100,           // x pos
   y : 100,           // y pos
   r : Math.PI * 1.2, // rotation
   s : 1,             // scale
}

snippet 2.

The collision test

For the two sprites where pA, and pB reference the sprite positionData (snippet 2) and cA and cB reference each sprite's collisionData (snippet 1) we first do the distance test, checking both the max radius and min radius. The code will return true if there is a collision.

const TAU = Math.PI * 2; // use this alot so make it a constant
var xd = pA.x - pB.x;          // get x distance
var yd = pA.y - pB.y;          // get y distance
var dist = Math.hypot(xd,yd);  // get the distance between sprites
                               // Please note that legacy browsers will not 
                               // support hypot 
// now scale the max radius of each sprite and test if the distance is less 
// than the sum of both.
if (dist <= cA.maxRadius * pA.s + cB.maxRadius * pB.s){
     // passed first test sprites may be touching
     // now check the min radius scaled
     if (dist <= Math.min(cA.minRadius * pA.s, cB.minRadius * pB.s) * 2 ){
          // the sprites are closer than the smallest of the two's min
          // radius scaled so must be touching
          return true;  // all done return true
     }

snippet 3.

Now you need to do the polar test. You need to get the direction from each sprite to the other and then adjust that direction to match the sprites rotation, then normalise the direction to the number of polar coordinates stored in the collisionData.

    // on from snippet 3.
    var dir = Math.atan2(yd, xd); // get the direction from A to B in radians
                                  // please note that y comes first in atan2

    // now subtract the rotation of each sprite from the directions
    var dirA = dir - pA.r;
    var dirB = dir + Math.PI - pB.r; // B's direction is opposite

    // now normalise the directions so they are in the range 0 - 1;
    dirA = (((dirA % TAU) + TAU) % TAU) / TAU;                  
    dirB = (((dirB % TAU) + TAU) % TAU) / TAU;         

The next step converting the normalised relative direction to the correct index in the polar array needs to account for the angular width of each polar coordinate. See fig 3. in the diagram the flat bit at the top of each polar coordinate is the angular width. To do this we use Math.round when scaling up from 0-1 to the number of coordinates. As values close to 1 will round up to the wrong index you also have to use modulo % to ensure it does not go out of range.

    var indexA = Math.round(dirA * cA.coords.length) % cA.coords.length;
    var indexB = Math.round(dirB * cB.coords.length) % cB.coords.length;

    // now we can get the length of the coordinates.
    // also scale them at the same time
    var la = cA.coords[indexA] * pA.s;
    var lb = cB.coords[indexB] * pB.s;

    // now test if the distance between the sprites is less than the sum
    // of the two length
    if( dist <= la + lb ){
        // yes the two are touching
        return true;
    }
}

Caveats

So that is it. It is relatively fast compared to other methods, though it is not pixel perfect as it only considers the perimeter of the sprites and if the sprites perimeter is not convex you may have situations where the algorithm returns a hit that is not true.

If the sprites are very rough there can be situations where the collision will fail to detect a collision, the same applies for over sampling the number of coordinates. The diagram shows 16 coordinates for a sprite that is near 128 by 128 which seems a good number. Bigger sprites will need more smaller less, But don't go under 8.

Improvement

In the diagram fig 4. shows a miss but if sprite's B coordinate 15 (one clockwise from the direction between them) was a bit longer there would be an undetected hit. To improve the algorithm you can tests the index coordinates on either side against the distance but you need to reduce the polar coord distance to account for the fact that they are not pointing at the center of the other sprite. Do this by multiplying the polar distance by the cos of the offset angle.

 // get the angle step for A and B
 var angleStepA = TAU / cA.coord.length;
 var angleStepB = TAU / cB.coord.length;

 // the number of coordinates to offset 
 var offCount = 1;

 // get next coord clockwise from A and scale it
 var lengOffA = cA.coord[(index + offCount) % cA.coord.length] * pA.s;

 // get next coordinate counter clockwise from B and scale it
 var lengOffB = cB.coord[(index + cB.coord.length - offCount) % cB.coord.length] * pB.s;

 // Now correct for the offest angle
 lengOffA *= Math.cos(offCount * angleStepA);
 lengOffB *= Math.cos(offCount * angleStepB);

 // Note that as you move away the length will end up being negative because
 // the coord will point away.

 if( dist < lengOffA + lengOffB ){
     // yes a hit
     return true;
 }

This adds a little more processing to the algorithm but not that much and should only be as far as half the angular size of A compared to B.

You may also wish to make the area between polar coordinates a linear slope and interpolate the polar distance for the first test.

More

There are many more ways of doing the test and the method you use will depend on the needs. If you have only a few sprites then a more complex algorithm can be used to give better results, if you have many sprites then use a simpler test.

Don't over cook it.

Remember that the pixel perfect test is what you the programmer want but the player can barely discern a pixel (modern displays have pixels that are smaller than the human eye's radial resolution). And if two almost invisible pixels touch for 1/60th of a second who would see that as a hit???

Answer 2

You could do this in two steps.

1. Check the bounding circles overlapping.

2. If the circles overlap, check the (more precise) bounding rectangles overlapping.

If you have two images, then, the center of each of them equals (x + w/2), (y + h/2). And the radius of each of them equals sqrt((w/2)^2 + (h/2)^2).

And two circles overlap when the distance between them (sqrt((x1-x2)^2 + (y1-y2)^2)) less than max(radius1, radius2).

The bounding rectangles collision detection is intuitive, but computationally may be harder (may influence on a large number of objects).

Answer 3

I know this is a pretty old question, but I was having the same problem and found a much simpler solution.

First, we need to write a long if statement to detect if the two images are actually touching. With semi-transparent images, this will be true even if the non-transparent parts aren't actually touching.

 if (/*horizontal*/ (sprite.x + sprite.width >= sprite2.x && sprite.x <= sprite2.x + sprite2.width && sprite2.hidden == false) && /*vertical*/ (sprite.y + sprite.height >= sprite2.y && sprite.y <= sprite2.y + sprite2.height && sprite.hidden == false)) {
}

Since the images are semi-transparent, this alone won't work. My next step was to create two new transparent canvases with the width and height equal to the original canvas.

// draws sprite onto canvas
var spriteCanvas = document.createElement("CANVAS");
var spriteCtx = spriteCanvas.getContext("2d");
spriteCanvas.width = canvas.width;
spriteCanvas.height = canvas.height;

var spriteImage = new Image();
spriteImage.src = sprite.base64Src;
spriteCtx.drawImage(spriteImage, sprite.x, sprite.y, sprite.width, sprite.height);

// draws sprite2 onto canvas
var sprite2Canvas = document.createElement("CANVAS");
var sprite2Ctx = sprite2Canvas.getContext("2d");
sprite2Canvas.width = canvas.width;
sprite2Canvas.height = canvas.height;

var sprite2Image = new Image();
sprite2Image.src = sprite2.base64Src;
sprite2Ctx.drawImage(sprite2Image, sprite2.x, sprite2.y, sprite2.width, sprite2.height);

Now we have two isolated images. We could loop through each pixel on the canvas, check if the pixel isn't transparent, and then check if the same pixel on the other canvas isn't transparent, but that would be very inefficient. Instead, we find the overlap of the two images. We can use context.getImageData() to get the RGBA (red, green, blue, transperancy) color of each pixel. We can check if each A (transperacy) value is greater than 0 to determine if the pixel is transparent. If you feel like this is too low, feel free to increase it.

// gets the overlap of the two
var spriteOverlap;
var sprite2Overlap;
        
var cropX = (sprite.x > sprite2.x) ? [sprite.x, (sprite2.x + sprite2.width) - sprite.x + 1] : [sprite2.x, (sprite.x + sprite.width) - sprite2.x + 1];
        var cropY = (sprite.y + sprite.height > sprite2.y + sprite2.height) ? [sprite.y, (sprite2.y + sprite2.height) - sprite.y + 1] : [sprite2.y, (sprite.y + sprite.height) - sprite2.y + 1];
        
spriteOverlap = spriteCtx.getImageData(cropX[0], cropY[0], cropX[1], cropY[1]).data;
sprite2Overlap = sprite2Ctx.getImageData(cropX[0], cropY[0], cropX[1], cropY[1]).data;
            

Now that we have only the parts that overlap, we can check each pixel on the first image for non-transparency and then check the same pixel on the other image.

pixelOverlap = false;

// loops through every overlaping pixel in sprite2
for(var i = 0; i < (sprite2Overlap.length / 4); i++){
    // checks if the current pixel has an opacity greater than one on both sprite or sprite2
    if(sprite2Overlap[i * 3] > 0 && spriteOverlap[i * 3] > 0){
        pixelOverlap = true;
    }
}

// if a pixel overlap was already found, sprite2 makes the function run faster
if(!pixelOverlap){
    // loops through every overlaping pixel in sprite
    for(var i = 0; i < (spriteOverlap.length / 4); i++){
        // checks if the current pixel has an opacity greater than one on both sprite or sprite2
        if(sprite2Overlap[i * 3] > 0 && spriteOverlap[i * 3] > 0){
            pixelOverlap = true;
        }
    }
}

And finally, don't forget to return pixelOverlap if this is a function.

return pixelOverlap;