Problem Solving: Irregular Hittesting Revisited, Pixel Perfect

Well, now what is the best type of hitTest for irregularly shaped objects that can be convex or not, can be rotated or not, can be scaled or not, can change shape or not, etc or not. Well the simple answer is Pixel Perfect Collision Detection. This is going to test the individual pixels of both images and check for an overlap. The best thing is that is also works for transparency. This code is guaranteed(mostly) to solve all your hit testing problems. Lets get started.

Well, instead of going ahead and making my own collision detection class, I decided to do a bit of research for some that were already made. I could save plenty of time like this. Grant Skinner had one on his blog, but it was in AS2. I decided to stick with this one, since Grant is a reputable kind of guy. Here was his original code:

/**
* GTween by Grant Skinner. Aug 1, 2005
* Visit www.gskinner.com/blog for documentation, updates and more free code.
*
*
* Copyright (c) 2005 Grant Skinner
*
* Permission is hereby granted, free of charge, to any person
* obtaining a copy of this software and associated documentation
* files (the "Software"), to deal in the Software without
* restriction, including without limitation the rights to use,
* copy, modify, merge, publish, distribute, sublicense, and/or sell
* copies of the Software, and to permit persons to whom the
* Software is furnished to do so, subject to the following
* conditions:
*
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
* HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
* WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
* OTHER DEALINGS IN THE SOFTWARE.
**/

import flash.display.BitmapData;
import flash.geom.ColorTransform;
import flash.geom.Matrix;
import flash.geom.Rectangle;

class com.gskinner.sprites.CollisionDetection {
	static public function checkForCollision(p_clip1:MovieClip,p_clip2:MovieClip,p_alphaTolerance:Number):Rectangle {

		// set up default params:
		if (p_alphaTolerance == undefined) { p_alphaTolerance = 255; }

		// get bounds:
		var bounds1:Object = p_clip1.getBounds(_root);
		var bounds2:Object = p_clip2.getBounds(_root);

		// rule out anything that we know can't collide:
		if (((bounds1.xMax < bounds2.xMin) || (bounds2.xMax < bounds1.xMin)) || ((bounds1.yMax < bounds2.yMin) || (bounds2.yMax < bounds1.yMin)) ) {
			return null;
		}

		// determine test area boundaries:
		var bounds:Object = {};
		bounds.xMin = Math.max(bounds1.xMin,bounds2.xMin);
		bounds.xMax = Math.min(bounds1.xMax,bounds2.xMax);
		bounds.yMin = Math.max(bounds1.yMin,bounds2.yMin);
		bounds.yMax = Math.min(bounds1.yMax,bounds2.yMax);

		// set up the image to use:
		var img:BitmapData = new BitmapData(bounds.xMax-bounds.xMin,bounds.yMax-bounds.yMin,false);

		// draw in the first image:
		var mat:Matrix = p_clip1.transform.concatenatedMatrix;
		mat.tx -= bounds.xMin;
		mat.ty -= bounds.yMin;
		img.draw(p_clip1,mat, new ColorTransform(1,1,1,1,255,-255,-255,p_alphaTolerance));

		// overlay the second image:
		mat = p_clip2.transform.concatenatedMatrix;
		mat.tx -= bounds.xMin;
		mat.ty -= bounds.yMin;
		img.draw(p_clip2,mat, new ColorTransform(1,1,1,1,255,255,255,p_alphaTolerance),"difference");

		// find the intersection:
		var intersection:Rectangle = img.getColorBoundsRect(0xFFFFFFFF,0xFF00FFFF);

		// if there is no intersection, return null:
		if (intersection.width == 0) { return null; }

		// adjust the intersection to account for the bounds:
		intersection.x += bounds.xMin;
		intersection.y += bounds.yMin;

		return intersection;
	}
}

Great! However its in AS2…
Time to convert!
And here we are now with the AS3 package.

/**
* Some quick modifications and a port to AS3 by UnknownGuardian
* www.kdugames.wordpress.com
*
* All credit is given to Grant Skinner, rights reserved to him, etc.
* Below is a copy of the original copyright/details of the package
*
*
* GTween by Grant Skinner. Aug 1, 2005
* Visit www.gskinner.com/blog for documentation, updates and more free code.
*
*
* Copyright (c) 2005 Grant Skinner
*
* Permission is hereby granted, free of charge, to any person
* obtaining a copy of this software and associated documentation
* files (the "Software"), to deal in the Software without
* restriction, including without limitation the rights to use,
* copy, modify, merge, publish, distribute, sublicense, and/or sell
* copies of the Software, and to permit persons to whom the
* Software is furnished to do so, subject to the following
* conditions:
*
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
* HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
* WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
* OTHER DEALINGS IN THE SOFTWARE.
**/
package com.gskinner.sprites
{
	import flash.display.Sprite;
	import flash.display.Stage;
	import flash.display.BitmapData;
	import flash.geom.ColorTransform;
	import flash.geom.Matrix;
	import flash.geom.Rectangle;

	public class CollisionDetection
	{
		private static var s:Stage;

		static public function registerStage(stage:Stage) : void
		{
			s = stage;
		}
		static public function checkForCollision(p_clip1:Sprite,p_clip2:Sprite,p_alphaTolerance:Number = 255):Rectangle {

			// get bounds:
			var bounds1:Rectangle = p_clip1.getBounds(s);
			var bounds2:Rectangle = p_clip2.getBounds(s);

			// rule out anything that we know can't collide:
			if (((bounds1.right < bounds2.left) || (bounds2.right < bounds1.left)) || ((bounds1.bottom < bounds2.top) || (bounds2.bottom < bounds1.top)) ) {
				return null;
			}

			// determine test area boundaries:
			var bounds:Rectangle = new Rectangle();
			bounds.left = Math.max(bounds1.left,bounds2.left);
			bounds.right = Math.min(bounds1.right,bounds2.right);
			bounds.top = Math.max(bounds1.top,bounds2.top);
			bounds.bottom = Math.min(bounds1.bottom,bounds2.bottom);

			// set up the image to use:
			if (bounds.height < 1 || bounds.width < 1) { return null; }
			var img:BitmapData = new BitmapData(bounds.right-bounds.left,bounds.bottom-bounds.top,false);

			// draw in the first image:
			var mat:Matrix = p_clip1.transform.concatenatedMatrix;
			mat.tx -= bounds.left;
			mat.ty -= bounds.top;
			img.draw(p_clip1,mat, new ColorTransform(1,1,1,1,255,-255,-255,p_alphaTolerance));

			// overlay the second image:
			mat = p_clip2.transform.concatenatedMatrix;
			mat.tx -= bounds.left;
			mat.ty -= bounds.top;
			img.draw(p_clip2,mat, new ColorTransform(1,1,1,1,255,255,255,p_alphaTolerance),"difference");

			// find the intersection:
			var intersection:Rectangle = img.getColorBoundsRect(0xFFFFFFFF,0xFF00FFFF);

			// if there is no intersection, return null:
			if (intersection.width == 0) { return null; }

			// adjust the intersection to account for the bounds:
			intersection.x += bounds.left;
			intersection.y += bounds.top;

			return intersection;
		}
	}

}

If you have read up a little on how is source code works, the AS3 version is a little different.

Before you do anything with this code, we need to call this method, because the stage is no longer accessible from everywhere like it was in AS2 with _root.

CollisionDetection.registerStage(stage);

Then after that, to check the collision of two objects, one can easily just call

if (CollisionDetection.checkForCollision(obj1, obj2, 200))
{
	//do domething...
}

Its really a nice piece of code to have on you at times.

Now, for those of you wondering why I did not do this at first. Because I was arrogant. I thought it would be better if I made completely original code and made it all my self with no external libraries/ideas/etc. Boy was I wrong. This 20 minutes of converting it and testing for errors fixed the problems I was having and showed me that the last week or so that I have been working on the collision problems to be a waste. That is a reuse code that has already been made lesson for you.

Cheers,

UnknownGuardian