Pixel accurate collision detection with Javascript and Canvas

May 18, 2013

I’m currently building a game where I need yet again collision detection. I usually go with the easy and somewhat efficient box-model collision detection. The main principle of the box model is that all objects are treated as squares, and if one square overlaps another, it’s treated as a collision. This is usually all that you need in a simple game. But because I’ve implemented this model so many times before, I decided to go a bit deeper and more accurate.

I opted to go down on the pixel level to decide if something is colliding or not. The first thing I needed to decide was “What constitutes a pixel?” I went with anything that has an opacity above 0, in other words, all pixels that are visible are treated as a possible collision point. To improve the efficiency in my algorithm I pre-built a pixelmap of the images, in other words, an array that contains objects about all the pixels that are visible on the screen.

/* Pseudo code to illustrate pixel mapping */
var pixelMap = [];
for( var y = 0; y < image.width; y++ ) {
	for( var x = 0; x < image.height; x++ ) {
		// Fetch pixel at current position
		var pixel = ctx.getImageData( x, y, 1, 1 );
		// Check that opacity is above zero
		if( pixel.data[3] != 0 ) {
			pixelMap.push( { x:x, y:y } );
		}
	}
}
return pixelMap;

A seemingly small image will grow quite large with this approach, a 40 * 40 square would generate 1600 pixels, everything would slow down to a halt if I decided to check every object against each other on a potentially huge canvas. So I mixed in the box model as a pre-detection of possible collision, if the hit test would return true, I’d dig deeper into the colliding images to see if they’ve actually touched pixels. This means that we’ll only use the heavy lifting once needed.

/* Box model detection, return true on collision */
function hitBox( source, target ) {
	/* Source and target objects contain x, y and width, height */
	return !(
		( ( source.y + source.height ) < ( target.y ) ) ||
		( source.y > ( target.y + target.height ) ) ||
		( ( source.x + source.width ) < target.x ) ||
		( source.x > ( target.x + target.width ) )
	);
}

Once the hitBox function returns true between two objects, we need to compare the two objects pre-rendered pixel maps with each other. What we basically do is we go through each pixel on the source object and see if it overlaps with any of the pixels on the target object. This is a very time consuming and processing expensive function. In essence every pixel from the source is matched against every pixel in the target, n*x possible checks, if we’re matching two 40 * 40 pixel squares we’d, in the worst case scenario, go through 2560000 computations without getting a match.

Box and pixel hit detection models

/* Pixel collision detection pseudo code */
function pixelHitTest( source, target ) {
	// Loop through all the pixels in the source image
	for( var s = 0; s < source.pixelMap.length; s++ ) {
		var sourcePixel = source.pixelMap[s];
		// Add positioning offset
		var sourceArea = {
			x: sourcePixel.x + source.x,
			y: sourcePixel.y + source.y,
			width: 1,
			height: 1
		};

		// Loop through all the pixels in the target image
		for( var t = 0; t < target.pixelMap.length; t++ ) {
			var targetPixel = target.pixelMap[t];
			// Add positioning offset
			var targetArea = {
				x: targetPixel.x + target.x,
				y: targetPixel.y + target.y,
				width: 1,
				height: 1
			};

			/* Use the earlier aforementioned hitbox function */
			if( hitBox( sourceArea, targetArea ) ) {
				return true;
			}
		}
	}
}

But as I draw out the objects, I only have a limited time frame to decide if something’s colliding. If we want to keep a butter smooth 60 fps animation (Which I believe most browsers aim for with the function requestAnimationFrame) we’d only have a theoretical 16.66ms of processing time between frames, excluding browser processing and frame rendering (I.e. we’re dealing with far lower figures in reality).

To combat this, we can work with a larger resolution, instead of working through each individual pixel, we can work through a cluster of pixels. So if we add a new flag, resolution, to our pixel map renderer and our pixel collision test, we should be able to bring down the computations to a more reasonable figure.

Pixel precision

/* Pseudo code to illustrate pixel mapping with resolution */
function generateRenderMap( image, resolution ) {
	var pixelMap = [];
	for( var y = 0; y < image.width; y=y+resolution ) {
		for( var x = 0; x < image.height; x=x+resolution ) {
			// Fetch cluster of pixels at current position
			var pixel = ctx.getImageData( x, y, resolution, resolution );

			// Check that opacity is above zero on the cluster
			if( pixel.data[3] != 0 ) {
				pixelMap.push( { x:x, y:y } );
			}
		}
	}
	return {
		data: pixelMap,
		resolution: resolution
	};
}

/* Pixel collision detection pseudo code */
function pixelHitTest( source, target ) {

	// Source and target object contain two properties
	// { data: a render-map, resolution: The precision of the render-map}

	// Loop through all the pixels in the source image
	for( var s = 0; s < source.pixelMap.data.length; s++ ) {
		var sourcePixel = source.data.pixelMap[s];
		// Add positioning offset
		var sourceArea = {
			x: sourcePixel.x + source.x,
			y: sourcePixel.y + source.y,
			width: target.pixelMap.resolution,
			height: target.pixelMap.resolution
		};

		// Loop through all the pixels in the target image
		for( var t = 0; t < target.pixelMap.data.length; t++ ) {
			var targetPixel = target.pixelMap.data[t];
			// Add positioning offset
			var targetArea = {
				x: targetPixel.x + target.x,
				y: targetPixel.y + target.y,
				width: target.pixelMap.resolution,
				height: target.pixelMap.resolution
			};

			/* Use the earlier aforementioned hitbox function */
			if( hitBox( sourceArea, targetArea ) ) {
				return true;
			}
		}
	}
}

The same 40 * 40 pixel square will now only generate a 100 pieces, which is quite the gain from over previous 1600 piece render map. And from going over 2560000 computations we are down at 10000 computations, which is 0,39% of the original computations. You could potentially build out this system further with higher accuracy, where you have multiple render maps with different resolutions, and checking large clusters first and going downwards from there, though the complexity of the system would grow quite a lot. With the current implementation it takes about 1-2ms to calculate a worst-case scenario collision when using a resolution of 3 on two 40*40px circular objects.

Here’s a gist of the complete class. (edit: 9 Aug. 2013, Updated the gist with a more efficient algorithm)

An example of the code in action will come later as I progress with the game. Though a lot of things might change in the approach I’ll use for the real version.

Update 2014-07-14

I started working on an improved and more thorough example last winter, but never got it finished. But if you want to check out the source, here it is. It also has object picking, so things are draggable.

Tags