Sign in to follow this  
Nicholas Kong

How to implement better Collision detection

Recommended Posts

I have experience implementing basic collision detection using bounding box collision with the help of the rectangle objects from the Java API.

 

The bounding box collision is fine for objects like rectangle shaped objects(ie: rows of bricks in a game). But things got more complex when I start adding objects that are not shaped like a rectangle (ie: a circle or even more complex object: a bird).

 

Seeing as my game uses images to depict non-rectangular shaped creatures, bounding boxes will not look right on these creatures. With bounding box collision detection, there will be a situation like the one below when an intersection will happen between both rectangles(the monster bounded by a rectangular collision box and a laser projectile also bounded by a rectangular collision box. From a visual standpoint, it is a game immersion breaking problem. 

 

collbox_zpscbf88de3.png

 

What type of programming techniques or perhaps I need to learn or apply some new math concepts for this problem?

Edited by warnexus

Share this post


Link to post
Share on other sites

You should always make the collision box smaller than the actual graphic of the entity, which will avoid a lot of situations like the one you described, even if occasionally it will cause entities' graphics to overlap without collision. That being said, there are methods for using circles instead of rectangles for collision detection, as well as per pixel collision - though both methods are more costly than rectangle collision. A tutorial for circle collision can be found here,  though this one is written in C++.

Edited by Ludus

Share this post


Link to post
Share on other sites
circle collision is extremely cheap(it's simply (distance between center points)<=(sum of both radius)). Although not as cheap as AABB, it's pretty much a non performance issue for general collisions detection. remember that you can also use AABB's to surround the entire object for initial collision checking, then use finer collision checking.

for shapes that don't conform to circles or rectangles, you could use a several smaller aabb's/circles that better represent the shape of the object's.

Share this post


Link to post
Share on other sites

Well you could switch to bounding spheres instead of boxes - to check if objects collide just give them each a radius then find the distance between the two center points

( distance = sqrt( xDistance2 + yDistance2) ) and if it is less than the two objects' radius' added together then there has been a collision

 

 

also you can define a bouding ellipse so that the y radius is different than the x radius - the math is a bit more complicated but the bounding ellipse would most likely match your object pretty well.. you can define an x radius for the object and a y radius for the object - then find the angle between the two objects and determine if there was a collision for the objects' radius length at that angle.. You can do that in the following way..

 

first find the angle between the two objects' center points by using..

 

 

float angle = atan( yDistanceApart / xDistanceApart )

 

then you can find each objects radius using this angle...

 

to do that consider the ellipse formula

 

( x2 / xRadius2 ) + ( y2 / yRadius2 ) = 1

 

now consider

 

x = radius * cosf(angle)    and   y = radius * sinf(angle)

 

substituting in the ellipse equation and solving for the radius you get

 

radius  =  sqrtf(   (xRadius2 * yRadius2) / ( cosf2(angle) * yRadius2 + sinf2(angle) * xRadius2) )

 

so you find the radius at that angle for both objects and then you can again see if the distance between them is less then their radi added together.. if it is less then there is a collision

Share this post


Link to post
Share on other sites

You should always make the collision box smaller than the actual graphic of the entity, which will avoid a lot of situations like the one you described, even if occasionally it will cause entities' graphics to overlap without collision. That being said, there are methods for using circles instead of rectangles for collision detection, as well as per pixel collision - though both methods are more costly than rectangle collision. A tutorial for circle collision can be found here,  though this one is written in C++.

Make the collision box smaller. Hmm...I will try that. I guess that means I need to make my own custom collision box instead of the Rectangle object from the Java API. Thanks for the advice. smile.png

Edited by warnexus

Share this post


Link to post
Share on other sites

You could have an ellipse shaped bound on the ellipse shaped smiley monster. It's a bit complicated but this article explains a very simple way of converting this into a sphere box text which are quite simple and cheap. This way you could have a perfect bound for the ellipse smiley monster.

 

I'm not sure if this is true or not but it doesn't help with any ellipse - ellipse testing nor sphere - ellipse testing (except they're both have the same axes and orientation, I guess).

Share this post


Link to post
Share on other sites

You could have an ellipse shaped bound on the ellipse shaped smiley monster. It's a bit complicated but this article explains a very simple way of converting this into a sphere box text which are quite simple and cheap. This way you could have a perfect bound for the ellipse smiley monster.

 

I'm not sure if this is true or not but it doesn't help with any ellipse - ellipse testing nor sphere - ellipse testing (except they're both have the same axes and orientation, I guess).

 

 

The post I made earlier literally walks through how to do ellipse collision detection step by step

 

Make the collision box smaller. Hmm...I will try that. I guess that means I need to make my own custom collision box instead of the Rectangle object from the Java API. Thanks for the advice.

 

You don't need to make your own rectangle - just use the center point of the sprite ( width / 2 and height / 2) and use either bounding sphere or ellipse. Both are very quick and easy to implement - especially bounding sphere.

Edited by EarthBanana

Share this post


Link to post
Share on other sites

You don't need to make your own rectangle - just use the center point of the sprite ( width / 2 and height / 2) and use either bounding sphere or ellipse. Both are very quick and easy to implement - especially bounding sphere.

 

I can't find an equivalent class that resembles a bounding sphere or ellipse in the Java API. The thing that came close was Ellipse2D but that was an abstract class which would mean it cannot be instantiated.

Share this post


Link to post
Share on other sites

irst find the angle between the two objects' center points by using..
 
 
float angle = atan( yDistanceApart / xDistanceApart )
 
then you can find each objects radius using this angle...

 

Never use atan in this situation, when it is so goddamn simple to just write:

 

float angle = atan2( yDistanceApart, xDistanceApart )

And so much more correct.

Share this post


Link to post
Share on other sites

I can't find an equivalent class that resembles a bounding sphere or ellipse in the Java API. The thing that came close was Ellipse2D but that was an abstract class which would mean it cannot be instantiated.

 

You don't need a class to represent it - just store the radius length you want for the object - if the distance between the two objects center points is less than the two objects radi added together then collision has happened.

 

and yes - use the ever so much more correct atan2 instead of atan

Share this post


Link to post
Share on other sites

You don't even need trig to do ellipse vs. point collision. If the ellipse is axis aligned (i.e. not rotated), just transform the ellipse into a circle by scaling the x and y offsets of the distance between the ellipse centre and the point, then do circle vs. point collision.

 

It's only slightly more complicated if the ellipse isn't axis aligned.

Share this post


Link to post
Share on other sites
so what you're really asking for and what nobody seems to be suggesting is using SAT tests to determine collision and the minimum separation vector required to separate the two objects after a collision.

it's quite complicated and math heavy but theres a great tutorial about it here http://www.metanetsoftware.com/technique/tutorialA.html from the creaters of N .

Share this post


Link to post
Share on other sites

You don't even need trig to do ellipse vs. point collision. If the ellipse is axis aligned (i.e. not rotated), just transform the ellipse into a circle by scaling the x and y offsets of the distance between the ellipse centre and the point, then do circle vs. point collision.
 
It's only slightly more complicated if the ellipse isn't axis aligned.

How do you do CvP without trig?

Share this post


Link to post
Share on other sites

Another option, which may or may not have been mentioned, is that you can use the stencil buffer to perform collision detection.  If more than one object occupies the same pixel, then you can be sure there is collision between them.  Then, once you examine the stencil buffer and determine the places where more than one fragment was rendered, you can then determine which objects are located at these positions, and then the collision will be known.  Not saying this is the only way, but is ONE way if you are looking for an absolutely exact collision (which you will not get when using 2D sprites with AABB approximations).

 

A second option, is tesselate your objects into triangles and create a convex hull.  A convex hull is a much tighter approximation than a simple AABB.  This will give you also, a better approximation.  Convex hull collision is a well studied area, you should be able to find an algorithm for collision.   If you go with this method however, you should first cull out results which do not pass the AABB test, as convex hull tests are much more expensive.

Edited by metsfan

Share this post


Link to post
Share on other sites

Well you need Pythagoras but not sin/cos/tan, which is what I was talking about. Just transform the coordinate space so that the ellipse is circular, then do a squared distance test.

Ah, for some reason when I thought CvP I thought of atan2. Ignore me. I'm not right in the head.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this