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