Jump to content

  • Log In with Google      Sign In   
  • Create Account


How to implement better Collision detection


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
16 replies to this topic

#1 warnexus   Prime Members   -  Reputation: 1370

Like
0Likes
Like

Posted 28 March 2013 - 10:58 PM

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, 28 March 2013 - 11:02 PM.


Sponsor:

#2 Ludus   Members   -  Reputation: 949

Like
1Likes
Like

Posted 28 March 2013 - 11:31 PM

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, 28 March 2013 - 11:35 PM.


#3 slicer4ever   Crossbones+   -  Reputation: 3087

Like
1Likes
Like

Posted 29 March 2013 - 12:03 AM

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.
Check out https://www.facebook.com/LiquidGames for some great games made by me on the Playstation Mobile market.

#4 EarthBanana   Members   -  Reputation: 786

Like
0Likes
Like

Posted 29 March 2013 - 12:19 AM

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



#5 warnexus   Prime Members   -  Reputation: 1370

Like
0Likes
Like

Posted 29 March 2013 - 02:50 AM

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, 29 March 2013 - 02:55 AM.


#6 hannesnisula   Members   -  Reputation: 957

Like
0Likes
Like

Posted 29 March 2013 - 03:03 AM

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).



#7 EarthBanana   Members   -  Reputation: 786

Like
0Likes
Like

Posted 29 March 2013 - 04:38 AM

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, 29 March 2013 - 04:41 AM.


#8 warnexus   Prime Members   -  Reputation: 1370

Like
0Likes
Like

Posted 29 March 2013 - 09:19 AM

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.



#9 Lightness1024   Members   -  Reputation: 677

Like
0Likes
Like

Posted 29 March 2013 - 09:20 AM

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.



#10 EarthBanana   Members   -  Reputation: 786

Like
0Likes
Like

Posted 29 March 2013 - 09:29 AM

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



#11 Paradigm Shifter   Crossbones+   -  Reputation: 5094

Like
0Likes
Like

Posted 29 March 2013 - 10:21 AM

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.


"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley

#12 franklyn   Members   -  Reputation: 124

Like
0Likes
Like

Posted 29 March 2013 - 01:24 PM

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 .

#13 hannesnisula   Members   -  Reputation: 957

Like
0Likes
Like

Posted 29 March 2013 - 01:25 PM

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

 

I've had the post up on a tab for some hours and didn't refresh it so only saw 1 reply, my bad.



#14 Khatharr   Crossbones+   -  Reputation: 2772

Like
0Likes
Like

Posted 29 March 2013 - 04:53 PM

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?
void hurrrrrrrr() {__asm sub [ebp+4],5;}

There are ten kinds of people in this world: those who understand binary and those who don't.

#15 Paradigm Shifter   Crossbones+   -  Reputation: 5094

Like
0Likes
Like

Posted 29 March 2013 - 05:10 PM

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.


"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley

#16 metsfan   Members   -  Reputation: 652

Like
0Likes
Like

Posted 29 March 2013 - 05:52 PM

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, 29 March 2013 - 05:53 PM.


#17 Khatharr   Crossbones+   -  Reputation: 2772

Like
0Likes
Like

Posted 29 March 2013 - 06:46 PM

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.
void hurrrrrrrr() {__asm sub [ebp+4],5;}

There are ten kinds of people in this world: those who understand binary and those who don't.




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS