Lab: Autopsy of Skinner's collision detection in AS3

In this article I'm working out the famous Grant Skinner's collision detection algorithm (yes, I know... I don't have any more interesting things to do at the moment :-) ). I will go through the code, line by line, trying to understand the whole process.

Actually the original class was written is AS2 but good people from labs.boulevar have ported it to AS3.

Original Skinner's version is available here:
http://www.gskinner.com/blog/archives/2005/10/source_code_sha.html

AS3 version is available here:
http://labs.boulevart.be/index.php/2007/06/08/skinner-collision-detection-in-as3/

Before I start, I need to admit that this just an attempt of code interpretation and may not be free of mistakes, so if you see any, please post a comment and let me know.

In my test project I created two MovieClips, circle (the bigger blue circle is actually semitransparent with alpha parameter set to 0.5) and polygon. Their bounding boxes overlap from Flash HitTestObject point of view, but in perfect collision detection algorithm they shouldn't be detected as colliding objects.

Ok, let's look at the code. There are actually three main methods in Skinners' code. The main one is named getCollision and it calls getAlphaMap method to get the alpha channels of the objects. Remainder two methods call the getCollsion method. getCollisionPoint as name indicates, returns an instance of the Point object with coordinates where collision was detected. The last method, named isColliding, returns true or false depending on whether collision was detected or not.

First, let's have a look at the getCollsion method.

Method expects at least two arguments: two Display objects (let's call them targets) and tolerance value which has a default value zero. getCollision will return a Rectangle representing overlapping area (if our targets overlap, otherwise null will be returned).

22

public function getCollision(target1:DisplayObject,target2:DisplayObject,
                                           tollerance:Number=0):Rectangle

The res will be a Rectangle object to return. First thing algorithm checks is to make sure that both targets are on the same level, in example, together on the stage or together within another movie clip - container.

23
24

	var res:Rectangle;
	if (target1.parent==target2.parent) {

Next, the DisplayObjectContainer is being created to hold reference to the parent object of our two targets. We need it in next two lines when using getBound method that will return the Rectangle objects with coordinates relative to this parent.

25
26
27

		var par:DisplayObjectContainer=target1.parent;
		var rect1:Rectangle=target1.getBounds(par);
		var rect2:Rectangle=target2.getBounds(par);

Screen below shows these rectangles representing targets' boundary boxes.

In next two lines, isIntersecting variable is being set to true or false depending on the result of Flash built in intersect method. If they don't intersect, code will end here, returning empty rectangle meaning there is no collision as boundary boxes aren't colliding. But in our case they do.

28
29

		var isIntersecting:Boolean=rect1.intersects(rect2);
		if (isIntersecting) {

Next, another rectangle is being created, it will hold these two rectangles - boundary boxes - together.

30

			var combinedrect:Rectangle=rect1.union(rect2);

Combinedrect looks like on the screenshot below (the box that holds our two target objects):

Next, two BitmapData objects are created to store alpha channel of both target objects. Arguments that are being passed are: our actual target, rectangle holding two boundary boxes of our targets, the constant value indicating which channel to use: red or green and finally, the boundary box of a target object. We expect getAlphaMap to return us the red circle and the green polygon.

31

32

			var alpha1:BitmapData=getAlphaMap(target1,combinedrect,
                                                   BitmapDataChannel.RED,rect1);
			var alpha2:BitmapData=getAlphaMap(target2,combinedrect,
                                                 BitmapDataChannel.GREEN,rect2);

Let's pause here for a moment and have look on the getAlphaMap method.

First it creates a new BidmapData object of size of our combined rectangle and creates matrix that will be needed for translation. Next, calculates x and y offsets - distance between the target objects and their boundary objects. Such situation would happen if our two targets were placed within another object like MovieClip which was in different position than 0,0. In our case offsets are zero as our target objects are both placed directly on the stage. Xpos and Ypos will hold position of the individual boundary boxes within the combined rectangle. In our case circle will have some x value and y equal to zero and polygon will have x equal to zero and some y value (as you can see on the last picture).

55

56
57
58
59
60
61

private function getAlphaMap(target:DisplayObject,rect:Rectangle,
                     channel:uint,myrect:Rectangle):BitmapData {
	var bmd:BitmapData=new BitmapData(rect.width,rect.height,true,0);
	var m:Matrix=new Matrix();
	var offX:Number=target.x-myrect.x;
	var offY:Number=target.y-myrect.y;
	var xpos:Number=myrect.x+offX-rect.x;
	var ypos:Number=myrect.y+offY-rect.y;

Next, m matrix is being translated along the x and y axes and used to draw the target object onto the bmd bitmap object. Matrix is not required when drawing bitmap, but if we didn't use it, our objects would be drawn to position 0,0. With matrix, circle is moved to the right and polygon is moved down (as per the combined rectangle). And finally another bitmapData object of the combined rectangle size is created to hold the alpha channel data.

62
63
64

	m.translate(xpos,ypos);
	bmd.draw(target,m);
	var alphachannel:BitmapData=new BitmapData(rect.width,rect.height,false,0);

CopyChannel method is used to copy the alpha channels of bmp bitmap object (representing our target) and store it as a red or green channel in alpha channel bitmap. Alpha is our source channel - this is what we want to read from the objects and destination is red or green channel - this is what we want to have as a result. Method will copy everything what has some alpha (alpha value different than zero). To test it yourself, you can use trace(bmd.getPixel(x,y).toString(16)) to check the color of the pixels - alpha has only values where are the pixels that create our objects.

65
66

	alphachannel.copyChannel(bmd,bmd.rect,new Point(0,0),BitmapDataChannel.ALPHA,channel);
	return alphachannel;

Calling getAlphaMap twice gives us alpha channels (in form of red and green) of our two targets, still preserving their original locations. Circle's and polygon's alpha channels copied to red / green channels are on the picture below:

Now let's go back to our main method. Draw method is used again and this is actually quite important line. Our red and green figures are blended. I just tried to blend green (#00FF00) and red (#FF0000) in Photoshop (Layer / Layer Style - Blend Mode - Lighten) and what have I got? Yellow (#FFFF00)!

33

			alpha1.draw(alpha2,new Matrix,new ColorTransform(),BlendMode.LIGHTEN);

Let's see what will we get in Flash?

Well, no yellow color as our figures don't overlap. And this is actually the whole cleverness of this algorithm. At this stage regular Flash hitTest would recognise collision, but Skinner's smart piece of code won't indicate anything. Let's move our circle over the polygon and again check the results:

This time our figures do blend together and we can see yellow region indicating where they are overlapping. Ok, but how will algorithm identify collision area? Let's look to the code again...

34
35
36
37
38
39
40
41
42
43
44
45
46

			if (tollerance>1) {
				tollerance=1;
			}
			if (tollerance<0) {
				tollerance=0;
			}
			var colorsearch:uint;
			if (tollerance==0) {
				colorsearch=0x010100;
			} else {
				var tollByte:Number=Math.round(tollerance*255);
				colorsearch=(tollByte<<16)|(tollByte<<8)|0;
			}

What's going on here? First simply tolerance is set to it's maximum or minimum value if it was outside the range. If tolerance was set to zero (default value) then default color is being assigned to colorsearch variable. This is "almost black" but not black as black is 0x000000. Why actually this color? You will understand in a while... Next, if value was greater than zero, then it will be used to generate color with bitwise operators. Let's say we passed .5 as a tolerance. What will we get?

tollByte value will be 0.5*255 = 127.5 which will be rounded up to 128. 128 in binary is 10000000. Colorsearch will be created by using shifting operators. 128 will be shifted to the first and second leftmost octet. Last 8 bits will be zero. So variable will hold "10000000 10000000 00000000" in binary.

If our tolerance would be 1, then we will get 255 which is binary is 11111111 and this would create colorsearch = "11111111 11111111 00000000".

To learn more about bitwise operators, read Bit shifting / Bitwise operators / Bit Masking article.

Ok, but why do we need all of this? Answer is in the next line and in a way how the getColorBoundsRect method works.

47

			res=alpha1.getColorBoundsRect(colorsearch,colorsearch);

As Adobe reference says, getColorBoundsRect: "determines a rectangular region that either fully encloses all pixels of a specified color within the bitmap image(...). The entire image is searched for the bounds of pixels for which (value & mask) == color (where value is the color value of the pixel)". Two values passed as arguments are mask and color. Method will use them to find our yellow region. To understand what's going on, let's try to do it ourselves:

We are going to pick yellow pixel from our bitmap - pixel from the yellow region when figures overlap - this will be our "value". Let's say our tolerance was 0.5 as in our previous example - this will be our "mask". Note that we are passing the same value as our mask and color.

"Value" (yellow pixel):                                         11111111 11111111 00000000

"Mask" (tolerance):                                             10000000 10000000 00000000

Result of bitwise AND operation:                          10000000 10000000 00000000

So the result is equal to our desired "Color" value: 10000000 10000000 00000000

And this means that condition is met, getColorBoundRect will use this pixel position to create a rectangle.

What happens if the pixel color value is different, let's say red?

"Value" (red pixel):                                            11111111 00000000 00000000

"Mask" (tolerance):                                           10000000 10000000 00000000

Result of bitwise AND operation:                        10000000 00000000 00000000

Result is NOT equal to our desired "Color" value: 10000000 10000000 00000000

This means getColorBoundRect will not use this pixel to build rectangle.

Now, let's check how the tolerance works. To do that, we needed to add our circle with alpha=0.5. To illustrate that even better, I'm going to draw the result of getColorBoundsRect - the rectangle - on the figures to show the region of overlapping using this code below:

var testrect:Shape = new Shape();
testrect.graphics.beginFill(0xfffff0, .5);
testrect.graphics.drawRect(res.x, res.y, res.width, res.height);
testrect.graphics.endFill();
addChild(testrect);

The left picture illustrates how the stage looks before compiling - notice the semitransparent element on the circle. The right image shows figures after compilation, just after the line of code where our figures were blended.

I picked up the greeny-yellow value for the screen - this is #87ff00. In example I will test this value with tolerance equal to zero. Remember that when tolerance is zero, default value #010100 is assigned.

"Value" (greeny-yellow):                            10000111 11111111 00000000

"Mask" (tolerance):                                   00000001 00000001 00000000

Result of bitwise AND operation:                00000001 00000001 00000000

Result is equal to our desired "Color" value: 00000001 00000001 00000000

The result indicates that with tolerance zero, algorithm should also accept the greeny-yellow color (our alpha circle) as the one that overlaps. And in fact, this is what's going to happen, take a look at the screenshot below and notice the rectangular area marked by semitransparent white region:

"Value" (greeny-yellow):                                    10000111 11111111 00000000

"Mask" (tolerance):                                           11111111 11111111 00000000

Result of bitwise AND operation:                        10000111 11111111 00000000

Result is NOT equal to our desired "Color" value: 11111111 11111111 00000000

This time the region doesn't contain the alpha part of our circle.

The tolerance value is not very intuitive, most people would say that a higher number will increase the tolerance - allow more transparent parts of the MovieClip to register collisions but it is actually opposite.

Let's go back to the code and have a look on the last lines of the main method. The resulting rectangle is positioned in the correct place and returned.

48
49
50

			res.x+=combinedrect.x;
			res.y+=combinedrect.y;
			return res;

As mentioned already at the beginning of this article, there are two additional simple methods in the class. Both call the main method.

First one, returns the collision point that is in the centre of the returned rectangle box. Basically it adds coordinates of the leftmost and the rightmost points of this rectangle and divides this by two to get the middle point on the x axis. Similar operation for the top and the bottom gives middlepoint for y axis.

72

73
74
75
76
77
78
79
80
81

public function getCollisionPoint(target1:DisplayObject,
                   target2:DisplayObject,tollerance:Number=0):Point {
  var pt:Point;
  var collisionRect:Rectangle=getCollision(target1,target2,tollerance);
  if (collisionRect!=null && collisionRect.size.length>0) {
    var xcoord:Number=(collisionRect.left+collisionRect.right)/2;
    var ycoord:Number=(collisionRect.top+collisionRect.bottom)/2;
    pt=new Point(xcoord,ycoord);
  }
  return pt;
}

Second one just checks if the rectangle was returned from the main method and returns true or false depending whether collision was detected or not.

82
83
84
85
86
87
88
89

public function isColliding(target1:DisplayObject,target2:DisplayObject,tollerance:Number=0):Boolean {
  var collisionRect:Rectangle=getCollision(target1,target2,tollerance);
  if (collisionRect!=null && collisionRect.size.length>0) {
    return true;
  } else {
    return false;
  }
}

So now, after we went through all of this, let's recap everything what we have went through.

Summary

In brief, this is how the getCollsion method works:

1. It takes three arguments, two MovieClips instances to check for colision and tolerance value, which is number between 0 and 1, that specifies the transparency tolerance (allow more transparent parts to register collisions).
2. Checks whether two MovieClips are intersecting, if so it proceeds to the next steps, otherwise there is no collision. Checking intersections is kind of standard HitTestObject method
3. Creates a rectangle of the same size as two movieclips combined
4. Draws alpha channels of one clip into the bitmap in red (#FF0000) and another one in green (#00FF00)
5. Draws another bitmap by blending (lighten) bitmaps in red and green. Blended green and red gives yellow, so intersection will have a yellow color (#FFFF00).
6. Searches for the "yellow" area, which is the collision area (depending on the tollerance parameter, it could be strict or not) and returns the rectangular area. This is done by bit masking every pixel color value with a tolleance value.
7. If a rectangle was returned, it means the colission was deteced.

Although this method is quite efficient and is (was) very popular, it has a major disadvantage. It doesn't work if you do any of transformations on the MovieClips like rotation or resize. It could be fixed by modyfing the transformation matrix when drawing clips to the bitmaps.