Collision Detection Kit

[skineh]

Hello Kirupians!

Recently I had a need for shape-based collision detection and decided to write up a class to handle it. As the class developed, I discovered other things that would be nice to have but weren't available, so I worked it out and added the functionality to my class.
Long story short, it developed into a small package of code I call the Collision Detection Kit. It's been so useful for me that I've decided to put it under an MIT license and share it with all of you. :D
It uses bitmapdata to find overlapping pixels of display objects. Not a new idea, I realize, but I wrote mine out from scratch anyways to handle things the way I needed them handled. This allowed me to figure out a few other nifty features that I include in the kit. Here are the big ones that me and my beta testers/coworkers have been loving:

- Set an alpha threshold so that any pixels on a display object below that alpha won't be checked for collisions.
- Exclude colors and color ranges from collision detection.
- The kit can approximate the angle of a collision, allowing you to keep your physics convincing when colliding with odd/organic shapes. It took awhile to figure out a good way of doing this. It's my favorite part of the kit.
- Gives you the pixels that overlap in a collision in stage coordinates, making it easier for you to adjust positions or apply off-center rotation convincingly.
- The kit takes nesting into account, so it doesn't matter where your display objects are on the display list.
- Takes transforms into account for individual instances, so things like scaling, rotating, and performing color transforms on your objects are no problem. This includes transformation made to any parent containers!
- Can be used with display objects on or off the display list. Works great alongside blitting engines.
- Works with all display objects: MovieClips, Sprites, TextFields (very cool), FLVs, etc.

I've created pre-compiled examples to show off these features and give you a better idea of what this package is capable of doing. I also have all classes documented, available online and for download (includes some rudimentary source code examples).
Feedback is welcomed! I don't have a discussion list for this yet, but plan on adding that or a forum later this evening (via Google Code). In the meanwhile, post any questions you might have here. I hope this can help some people out, as it's helped me a ton! :D

A new version of the CDK (v1.5) is now available! Links have been updated. I'm thrilled that the CDK has been so useful to so many devs, and I'm glad to finally be pushing out this update based on user feedback. Enjoy!

THE CODE (http://code.google.com/p/collisiondetectionkit)
EXAMPLES (http://www.coreyoneil.com/portfolio/index.php?project=5)
DOCUMENTATION (http://www.coreyoneil.com/Flash/CDK/documentation/index.html)

[rumblesushi]

Wow, nice work bud, I'm impressed. Nasty graphics, but a superb little collision engine ;)

Thanks for sharing it.

[skineh]

Haha, yeah, the graphics were definitely not a focal point. ;)

You're welcome! :D

[johnlouis]

wow that's mighty impressive!

[ChromeDemon]

Nice work dude ... Much appreciated

[skineh]

Thanks, guys. Glad you like it! :D

[TUNCAYS]

wonderful
thanks.i m use it :)

[doridori]

Looks awesome!
Will check it out at once.

[randomagain]

I want your baby!!!!

[skineh]

Hahaha, thanks guys! My babies are in high demand, so might have to put you in a queue. ;) Really, though, glad to hear you all like it! It's been a busy week for me, but I'm going to get a forum put up for it on Google Code soon in case anyone has any questions and so on.

[Esherido]

That's amazing! :thumb2:

[rumblesushi]

I'm surprised this hasn't had even more feedback actually.

It's great. The only thing I would say so far is find ways to optimise performance, for the amount of objects that were active, it seemed a TAD cpu heavy.

When I've got time, I'm going to play around with it, and find ways to implement it.

[skineh]

Thanks for the feedback Esherido, rumblesushi.

Yea, rumblesushi, I agree there's probably room for optimization. It went through several phases of redesign along the way, and a few cheap tricks were incorporated into some of the math to get some small increases in performance. Still, there's always room for improvement! :D If you end up doing anything with the package (especially if you rewrite it and get it to perform faster), I'd love to hear about it!

I should note that performance will also depend heavily on what features you're implementing. Color exclusion is the most CPU-intensive, as the bitmapdata samples taken for comparison have to perform significantly more checks against their pixel information to see if they fall under the color ranges a user has specified.

[Gathan]

It wouldn't hurt to include some source code examples of how to use it, like for the examples or something.
More specifically examples showing how the various features that it has are useful for shaped based collision detection.

[skineh]

There are several source code examples for the CollisionGroup and CollisionList classes in the documentation (as mentioned in my first post). :D

[Gathan]

Ya I already saw those, they aren't well very good examples sorry and completly fail to show how the various features are useful for practical shaped based collision detection.
Which is why I was asking for some better examples.

[skineh]

Ahhh, gotcha. :) Yea, when I wrote those source examples, they were only meant to show rudimentary setup for the classes. As far as how to use the features available, well... that's kind of up to what the programmer requires. Shape-based collision is useful in a lot of different areas, especially game programming. The features included with the package are demonstrated to show what their function does, not what their function is, as that will be different from project to project.

One example I can think of offhand for the alphaThreshold feature would be when a character dies. In many games, the character will come back to life and be slightly transparent for awhile, signifying that they're invincible at that time. If you were to set the alphaThreshold property to the alpha of the character while they're invincible, then any weapons fire or enemies attacking the character would be ignored without having to write further logic to define that condition.

In the end, I think I left out more involved examples like that because I feel it's up to the programmer to decide what tools are right for each job and recognize when that's the case. Still, I agree it could help clarify the kit's usefulness if more complete, practical applications of its features were showcased. I know of a few people working with the kit right now in their own projects, and I am planning to incorporate their examples (along with proper credit given). For that matter, if anyone reading this happens to use the kit, please feel free to contact me and let me know about it. :D

[rondog]

that video one blew me away

[tarwin]

Looks good. Reminds me of http://www.gskinner.com/blog/archives/2005/08/flash_8_shape_b.html

A few quick optimizations I can think of:

* Do an AABB on objects before checking them (a good AABB check will be super super quick)
* Use the BitmapData.getColorBoundsRect() to find if colors exist instead of looping through all pixels

Tarwin

[skineh]

Hi, tarwin! Thanks for the suggestions. :) I agree there may be a boost in performance in most cases doing AABB checks on the objects first. Currently, I do perform a check based on regular bounding boxes before ever going pixel-deep. Going AABB instead may save from a few needless checks.

Good call on the getColorBoundsRect! Clearly a method I overlooked. :D I'll be sure to try that out, thanks!

EDIT - Actually, now that I'm thinking about it, I don't think I could utilize getColorBoundsRect. Two reasons that come to me offhand.
1) Receiving bounds will let me know the excluded color(s) exist, but not if there are other (valid) colors. And finding that out using getColorsBoundRect would still have me doing a ton of looping to account for the rest of the color spectrum.
2) I need those individual pixel locations when finding the angle of collision.
Still, I'll mull it over and see if there's a way I could make use of it to speed things up. And either way, I'll definitely look into doing an AABB check rather than the current standard bounding box check. Thanks again for the suggestions!

[jakattak]

This is great. Thanks for sharing :)

[tarwin]

You could use getColorsBoundRect for some cases. If you're not using the include/exclude colors thing then it at least works as a sweep pass, as a first check. Maybe.

[Flasher777]

Hi. I like you collision detection kit. It's really cool. But I have a problem...I don't understand how to react after collision (may be beacause I forgot math :) Could you please provide me with a simple examble (for example colliding balls like on you site).
BR!

[skineh]

Hey there Flasher, glad you like the kit! :)

I thought I didn't have time to write up a quick example, but looks like I've already done so in another forum awhile back, so I'm copying it over here. In this example, the objects that have hit each other have properties to track their vectors and mass. One object is stationary and immovable, and the other needs to figure out how to bounce off in a convincing way.

This is a pretty straightforward approach, with plenty of room for expansion and change, but should hopefully get you moving in the right direction.



var hits:Array = collisions.checkCollisions();

for(i = 0; i < hits.length; i++)
{
var item1 = hits[i].object1; // Let's assume I know this is the moving object
var item2 = hits[i].object2; // Our static object. Assume I set its X/Y vectors to 0 and mass to something super high

var angle:Number = hits[i].angle;
var sin:Number = Math.sin(angle);
var cos:Number = Math.cos(angle);

var vx0:Number = item1.vx * cos + item1.vy * sin;
var vy0:Number = item1.vy * cos - item1.vx * sin;


mass = item2.mass;
vx1 = item2.vx * cos + item2.vy * sin;
vy1 = item2.vy * cos - item2.vx * sin;


vx0 = ((item1.mass - mass) * vx0 + 2 * mass * vx1) / (item1.mass + mass);
item1.vx = vx0 * cos - vy0 * sin; // New vectors
item1.vy = vy0 * cos + vx0 * sin;

item1.x += -cos * hits[i].overlap / (item1.width / 2); // Push object out so it's no longer overlapping
item1.y += -sin * hits[i].overlap / (item1.width / 2);
}


If you're interested in learning how to do animations like this in Flash, I'd strongly recommend Making Things Move! (http://www.amazon.com/Foundation-Actionscript-3-0-Animation-Making/dp/1590597915/ref=sr_1_1?ie=UTF8&s=books&qid=1224679749&sr=8-1) by Keith Peters. It's a great introduction to the math behind many fun topics and a handy reference book.

[Flasher777]

Cool! Thank you very much!

[Flasher777]

Hi. I found 1 problem:
If we set scale for the container != 1, collision detection doesn't work correctly.

[lukasyno]

great stuff !!!!!!

[skineh]

Glad you like it, lukasyno. :)

You're right, Flasher. If you perform a transform on a container clip it jacks things up a bit. If I get a chance, I'll take a look and see if I can account for it. Currently, the CDK handles transforms done to the objects themselves, and does account for objects nested inside containers. Looks like it won't handle transforms such as scaling on the containers, though. :/

[SAEC-KV]

Just started figuring this out yesterday, it's pretty awesome :) Question - where can I find syntax/examples for how to actually bounce objects off a "colliding" surface? You have it in all of your examples on the website, but unless I'm missing something it's not listed in the code samples.


Thanks!

[skineh]

Hey SAEC-KV, happy to hear you like it. :D

The physics stuff I just wrote up to show how well the angle of collision found by the CDK is since you need an angle of collision to know how to bounce off of something. The CDK handles collisions and can evaluate the area of the collision to approximate the angle at which the two objects hit, but the physics is up to the person using it. If you scroll up a couple of posts, though, you'll see I provided a quick example of how you might go about it. :)

[vega]

It looks great. I am thinking of using it on the next project and will post the feedback if I come across anything interesting.

Thanks for sharing and good job :)

[Iamthejuggler]

Nice work mate. Always nice to see people sharing their source for stuff, especially when it's this impressive and useful to a lot of people. Especially liked the video example, although it was pretty laggy. Maybe that was my PC.

Haven't had a chance to look at the code yet, but i'm looking forward to doing so as soon as i get back from holiday.

Kudos to you sir!

[djnorthyy]

Very cool!

[johnlouis]

just curious, is this similar to APE (http://www.cove.org/ape/), or is this strictly a collision detection kit?

[skineh]

just curious, is this similar to APE (http://www.cove.org/ape/), or is this strictly a collision detection kit?

Strictly for collision detection. There are plenty of great physics/collision libraries out there for box/circle scenarios, and I wasn't looking to reinvent the wheel. I had created the kit to fill a specific need I had, which was detecting collisions and determining the angle of the collision when I don't know anything about the objects' properties such as their magnitudes or if they're simple shapes. Since what you'd want to do AFTER you've gotten this information can vary greatly from project to project, I didn't include any physics, leaving it to the user to do what they want from that point on.

EDIT: Also worth mentioning that with that in mind, it's possible to incorporate the kit's collision detection with other libraries' physics. Of course, how much tweaking would be required to get them to play along would vary, but the option is there.

[Wotuer]

Ahh man, i'm so thankfull, i started working on colision detection like this, implementing physics. I didn't even know where to start, i started working on it and the basic physics were fixed but i wouldn't even know how to do any accurate angle-detection, let alone adjusting my physics to them. I would never had taught of bitmap tracing and if i would i'd still wouldn't know how to implement them. Anyway, I didn't know what i was getting in to and thank god i found your script because if i knew from the beginning i was getting in to an 600+ lines script i'd never would've started, so im prrrreetty glad i found out at about line 60 rather then line 300. So I'm way gratefull, very nice work.

[PsuFan]

I just started using the CDK, its absolutely amazing. Props to the creator.

[skineh]

I just started using the CDK, its absolutely amazing. Props to the creator.


Thanks! :) Glad to hear you're enjoying it. Did you attend PSU? I was at the Berks campus for 2 years.

[skineh]

Ladies and gents, a new version of the CDK is now available!

I've just released version 1.5 of the Collision Detection Kit. I'm floored that it's been as popular as it is, and very happy that it could be of so much use to fellow devs out there. It's for that reason that I finally put some time aside and made some changes that were long overdue. They're mostly user requests, but also includes an overall optimization of the code. Here's what's new:



Instead of just getting the number of overlapping pixels in a collision, the CDK now gives you those pixels in stage coordinates in an array. Real, real handy when wanting to do off-center rotation or adjust an object's position to get it back onto a surface.
You no longer need to have your display objects on the stage for the CDK to use them! This is great, because now you can use the CDK completely off the stage. Works beautifully alongside a blitting engine.
Parent/container display objects now have their transformations taken into account. So if you're detecting collisions with a bunch of stuff inside a parent container, and you scale that parent container on the fly, the CDK will adjust for it no problem.
Code optimizations made throughout, leading to an average 15% improvement in speed.


Some new examples are available on my site. More importantly, however, is that I'll soon be writing up full step-by-step tutorials for these examples. This should be helpful for anyone needing a jump start on how to incorporate physics with the CDK.
I'll be sure to announce here, on my site, and on Google Code once the examples are available.

I've given this new release out to a few people in the past month or so to test drive it, and they're loving it. I strongly recommend anyone who already uses the CDK to grab the new version and start using it. Enjoy!

THE CODE (http://code.google.com/p/collisiondetectionkit)
THE EXAMPLES (http://www.coreyoneil.com/portfolio/index.php?project=5)
THE DOCUMENTATION (http://www.coreyoneil.com/Flash/CDK/documentation)

[Dom_]

pretty nice demo with the text :)

[ChromeDemon]

Can't wait for sum In-Depth Tutorials

[skineh]

Thanks, Dom_. :) Incidentally, I don't know if it's all that obvious or not, but it's a slideshow of examples. You can click the white arrow to move through them.

You and many others, ChromeDemon! It's a request I've gotten many times since I first released the CDK, but I've had work and other outside projects hogging up my time (I still have an isometric/3d engine to document and release that's been done for ages). Still, I'm holding myself to writing up some tutorials within the next fortnight. It seems the most requested tutorial is on implementing physics with the information the CDK gives you, so I'll be sure to start with that.

[Dom_]

yep, the other examples are all very good.
Tutorials would be a cool idea
Good work skineh!

[ChromeDemon]

Easy Skineh ... I appreciate your exciting work :)

[saxx]

Wow this is very impressive skineh, i hope i get to use this sometime it's all pretty cool

[BoppreH]

I can't wait for a good bouncing code with this thing.

Mine always show some quirks here and there, accelerating targets on the wrong direction and making them shake.

[marnix]

damn nice, thanks man.

[skineh]

damn nice, thanks man.

You bet! :)

Okay, no tutorials yet, as life enjoys keeping me busy. I did throw together the source files for the examples, however, and they are now available up on Google Code.

http://code.google.com/p/collisiondetectionkit/downloads/list

[Creature]

http://code.google.com/p/collisiondetectionkit/downloads/list
Thanks thanks thanks thanks! :D

[_Etienne_]

So, I have no problem using the overlapping, but I'm trying to get a percentage of overlapping points versus total points. Been working on it for a few hours now and can't seem to make it work :S

Shouldn't be hard to do, yet I can't figure it out. Just need to create another array with total points. There's already one with overlapping points which means we should be able to get every single points, no?

e.g: collisions[0].overlapping.length / collisions[0].total <---is what I'm trying to get. Any ideas?

Thanks :D

[skineh]

So, I have no problem using the overlapping, but I'm trying to get a percentage of overlapping points versus total points. Been working on it for a few hours now and can't seem to make it work :S

Shouldn't be hard to do, yet I can't figure it out. Just need to create another array with total points. There's already one with overlapping points which means we should be able to get every single points, no?

e.g: collisions[0].overlapping.length / collisions[0].total <---is what I'm trying to get. Any ideas?

Thanks :D

Total points for what, exactly? You mean all pixels in the image(s) as opposed to only the overlapping pixels? You can get that by multiplying their dimensions...


var numPixelsImage1:int = image1.width * image1.height;
var numPixelsImage2:int = image2.width * image2.height;

[skineh]

So, I have no problem using the overlapping, but I'm trying to get a percentage of overlapping points versus total points. Been working on it for a few hours now and can't seem to make it work :S

Shouldn't be hard to do, yet I can't figure it out. Just need to create another array with total points. There's already one with overlapping points which means we should be able to get every single points, no?

e.g: collisions[0].overlapping.length / collisions[0].total <---is what I'm trying to get. Any ideas?

Thanks :D

...otherwise, if you're looking for the total number of visible pixels, or the total number of pixels that meet any alphaThreshold or colorExclusion requirements regardless of overlap, then no, the CDK doesn't track those totals.

[flashmxboy]

Hi

I started using CDK to do pixel perfect collision detection between a bitmap(inside a movieClip) and a movieClip. It seems like CDK is the only way to do this perfectly:D
But i have noticed some performance differenses between hitTestPoint and CDK. Im running collision detection inside a loop and when using the CDK i have to put this line in the end of every loop:
collisionArray = collisionList.checkCollisions();
Is this the correct way to do it? When I do this I notice fps drops from 40 to 25 when the loop runs:-/ And it runs smooth with hitTestPoint(but then it trace hits on the trasparent pixels) :(

Any help here?

[skineh]

What are you looping through? Chances are good you don't need to be doing it at the end of your loop.

Assuming you added all objects you're detecting for collisions to that single instance (collisionList), then you only need to run checkCollisions() one time whenever you want to check for collisions. That checkCollisions() method checks for collisions against ALL the objects you have in the list, and returns all collisions found in the array you're capturing. You can then loop through THAT array and handle all of the collisions.

In pseudo code, your procedure may look like this:


var collisionArray:Array = collisionList.checkCollisions();

for(i = 0; i < collisionArray.length; i++)
{
var collision:Object = collisionArray[i];
Handle whatever needs to be handled between the two objects in this collision.
}

Apply whatever physics or other such fun stuff to my objects.


So if you were handling your collisions in an enterFrame handler or with a timer, you'd do the above one time in the handler. Hope that clears things up a bit for you.

[Flasher777]

Hi again!
Is it possible to increase collision detection performance reducing collision quality somehow?
Br!

For example not to check collision with each pixel of colliding object

[eddmosphere]

sweeeet! thanks!

[digivid-pro]

I've just discovered this wonderful kit, but I'm having trouble with multiple moving items. Your examples in the documentation for the CollisionGroup only show dragging one item into another. Are there any examples anywhere of several items moving toward their own targets (my project has them "floating up" from below the stage), getting bumped by others moving toward their own targets? I'm not great at physics so I'm having trouble relaying the returned values, as well as extending your drag-one, bump-one example. If this is one of the tutorial's you have in mind, I'd greatly appreciate your movinjg it up the todo list... or pointing me toward some similar example elsewhere. So far, haven't found anything.

[MakotoNinja]

Hopefully this thread isn't dead and that Corey is still around...

I am trying to use CDK to keep a user controlled item from penetrating other items without the use of a physics simulation, picture a top down game where the main character has walls and other obstacles that it shouldn't be able to penetrate.
I am using the 'CollisionList' class to check for collisions and my collision resolution script works but I fear it is way too CPU heavy:


var collisions:Array = cl.checkCollisions();
if(collisions.length){
var angle:Number = collision.angle;
var sin:Number = Math.sin(angle);
var cos:Number = Math.cos(angle);
var offset:Number = 1;
while(collisions.length){
hero.x -= cos*(offset);
hero.y -= sin*(offset);
collisions = cl.checkCollisions();
}
}
as you can see the while loop moves the hero back along the vector created by the angle of the collision until it is no longer colliding. Like I said, this works but is a little CPU heavy and visually a little jittery.

My question is, is there a way to calculate the exact overlap in x and y pixels so that I would only need to move the hero once per collision?

Oh, and I guess I should mention that I am trying to implement this collision system as opposed to SAT or AABB as I want the most freedom in designing and dont want to be limited to circles and squares.

[ChaoSXDemon]

The classic answer to reduce CPU consumption is to increase memory usage! If you know you are going to call lots of sin, cos, you can always physically store the sin and cos values.

What you can also do is to use Vector based calculation. The dot product is extremely useful since you can find the angle between any two vector by simply multiplying!

U.dot(V) = |U|*|V|*Cos(angle), where angle is the angle in radians from U to V;
|U| is vector length of U and |V| is the vector length of V. You may also use unit vector (vector with total length = 1), then angle = arcos(u.v), where u, v are unit vector of U and V. Finally once you have found cos, you can use the property that sin^2 = 1 - cos^2 to find sin.

However, depending on the nature of your problem, the above method may not be optimal.

Additionally you can also use Taylor Series to approximate your sin/cos functions. A good thing about this is that you can control the degree of accuracy.

[MakotoNinja]

Wow, after looking up 'dot product' and 'Taylor Series' on wikipedia, my head exploded.
Thanks for the help but that level of math is a bit over my head without some explanation.

[saxx]

Wow, after looking up 'dot product' and 'Taylor Series' on wikipedia, my head exploded.
Thanks for the help but that level of math is a bit over my head without some explanation.

I'm with you there man.

[ChaoSXDemon]

Wow, after looking up 'dot product' and 'Taylor Series' on wikipedia, my head exploded.
Thanks for the help but that level of math is a bit over my head without some explanation.

Well, Wiki always gives you a too much detail explanation. It is nevertheless, very formal. For a video game, dot product is vital, especially in 3D (also Cross product is vital too in 3D). They are not very difficult to understand if you don't look at all the symbols in wiki.

Basically dot product is:
suppose vector u = (0, 2)
suppose vector v = (2, -1)
then u.v = 0*2 + 2*(-1) = 0-2 = -2
So you always take the x components (0 and 2 here for u and v) and multiply together, and then add the y components (2 and -1 here for u and v).

That's it! But in order to make them useful, (ie finding the angel between them) you need to also find the length of a vector. This is also very simple:

length of u = |u| = sqrt(0*0 + 2*2) = 2
length of v = |v| = sqrt(2*2 + (-1)*(-1)) = sqrt(5) = 2.236

I hope you recognize this, because this is simply the Pythagoras theorem.

Now, if you take the dot product, and divide by their length times together, you have:

cos(theta) = (u.v) / (|u|*|v|) = (-2) / (2*2.236) = -0.44723
so if:
cos(theta) = -0.44723
then:
theta = 2.03446 (in radians)
if you want degrees, divide that by pi, and times 180 you get: 116.57 degrees :)


As for Taylor series, you need to understand Calculus :) (derivatives specifically)

[fjordside]

Hi, - wow - thanks for a great set of classes - really appreciate them.

Would it be possible to have the CDK calculate a balls rotation as it collides with other objects, like f.ex. having a smilie-face rolling down the ramp in the terrainExample.

Anything that might shed some light on this would be much appreciated.

Thanks again for this great resource.

[su8888]

I have used array of display objects to and adding them the the CollisionList as follows

myCLCowTarget = new CollisionList(target1);

for ( var sz:int=0; sz < mooArray.length; sz++ )
{
addChildAt(mooArray[sz], sz);
myCLCowTarget.addItem(mooArray[sz]);
var collisionData:Array = myCLCowTarget.checkCollisions();
if(collisionData.length>0)
{
removeChild(mooArray[sz]);
myCLCowTarget.removeItem(mooArray[sz]);
mooArray.splice(sz,1);
}
}
collision is detected, but multiple cows are removed from the arrayDisplay Object.. what am I doing wrong??

If I add the Objects in the CollisionGroup, is there any way to assign one object as target check all others in the group against each other and removeChild from the scene if it collides with the target.. ???

Help...!!!

Thanks