**0**

# Faster Collisions Circles or Squares? Advice. (Fixed)

Started by EnlightenedOne, Sep 07 2009 02:15 AM

13 replies to this topic

###
#1
Members - Reputation: **142**

Posted 07 September 2009 - 02:15 AM

Hi there I have been looking around trying to create an efficient means of having things in my 2D top down asteroids rebuild colliding. Now the trouble is do I use circles or squares to do the collisions?! I have done some research... as you will soon see. This is quite a long post so I can understand anyone wishing to skim read. Im working with C++ in DX9.
Firstly I dont care where particularly the shapes touch with circle collisions the direction you collide with an object at is going to be the direction your moving in as that is a an angle. With squares im sure it would take more effort I am curious to see if anyone has an effective way of iscolating that as the squares collision is tested.
Circles involve finding the distance between the two shapes and then identifying their combined radius value to see if the two points in 2d space are touching.
Circles Example. -------------------------------------
A = x,y, radius
B = x,y, radius
FIND THE DISTANCE
To find the distance between the two you need too.
Find the smaller of the x and y values.
Take the smaller x and y values away from the larger x and y values.
Square them.
Add them together.
Find the square root of the value you have combined, tada you have the distance.
IDENTIFY COLLISION
Add the radius values of the two objects your testing between.
Take the radius values away from the distance and if you have a negative value your objects are touching!
Squares involve identifying when one border of one side of either of the two objects has overlapped another border of the other square.
Squares Example. -------------------------------------
A = x, y, width, height;
B = x, y, width, height;
This is abit drawn out to describe but basically I think you need. Assuming the square never rotates. My game involves squares so I was wondering if anyone could provide a more flexible or intelligent solution for such collisions which is more efficient!
Here an idealic solution.
if A.Right < B.Left or
A.Left > B.Right or
A.Top < B.Bottom or
A.Bottom > B.Top
Translating in nerdy form to.
if objectA.x + objectA.width < objectB.x or
objectA.x > objectB.x + objectB.width or
objectA.y < objectB.y + objectB.height or
objectA.y + objectA.height > objectB.y
However this idealic solution is flawed. You can be parallel to an object in one direction and yet be on another axes very far away.
So you need to create a logical square at the edge of your shapes borders to identify if one edge has been touched by another, this requires there to be 4 logical statements based on the squares side it varies abit but you just need to pick a side and its easy enough to interpret.
That is one if statement with 4 logical statements in there as and statements. To iscolate every side. If you look up at the simple Right < Left idealic concept then you multiply every time you see a direction by 4 thats 32 logical statements for every single collision detection for none rotating squares that is not pretty. Has anyone got a better way to show me?
Analysis?, corrections? HELP! -------------------------------------------
At the moment I am thinking one or the other but perhaps combining both is although more complicated more ideal for the game. Additionally Orientating a squares collision box based on the direction of my space ship would be nicer than having it be based purely around square the texture is drawn into.
How can I make a circle register being hit by a square? I am going to have to go into overlapping verticies for such collisions is that efficient for a 2D game? I am aware im going to have to play with that stuff anyway in the real world when I go 3D but I was hoping to meet that wall after I am comfortable with particle systems. Advice?
[Edited by - EnlightenedOne on September 10, 2009 4:15:57 PM]

Sponsor:

###
#2
Members - Reputation: **102**

Posted 07 September 2009 - 02:53 AM

Ok there EnlightenedOne :p

What you need in the end sounds like something called SAT (" Separating Axis Theorem").

http://uk.geocities.com/olivier_rebellion/Polycolly.zip

its an actual Tutorial for sat it is what i have been doing latly and since you are doing C++ the tutorial is meant for that iv had to convert my code to C# but it works all the same.

Basically speaking you can do Circle To Polygon Detection as well as Poly to Poly

One thing to note is SAT only really works with Convex objects unless you do a good bit of extra work. The easiest way is to actually break down your object into Convex objects rather then it being concave.

Doing sat now even though it requires the use over a bit of Vector math does seem to be a bit more then what 2D should need but it is well worth it.

On the other hand. If you want to just do a rectangle to Circle Collision response. You could do the same thing you do for two circles but just do it with each point of the square. But even then this still requires to have some sort of tracking of each point of the square. Ether witch way you do want to keep track of each point of the rectangle to ensure a better and more accurate collision detection and response.

Hope this helps Regards jouei.

What you need in the end sounds like something called SAT (" Separating Axis Theorem").

http://uk.geocities.com/olivier_rebellion/Polycolly.zip

its an actual Tutorial for sat it is what i have been doing latly and since you are doing C++ the tutorial is meant for that iv had to convert my code to C# but it works all the same.

Basically speaking you can do Circle To Polygon Detection as well as Poly to Poly

One thing to note is SAT only really works with Convex objects unless you do a good bit of extra work. The easiest way is to actually break down your object into Convex objects rather then it being concave.

Doing sat now even though it requires the use over a bit of Vector math does seem to be a bit more then what 2D should need but it is well worth it.

On the other hand. If you want to just do a rectangle to Circle Collision response. You could do the same thing you do for two circles but just do it with each point of the square. But even then this still requires to have some sort of tracking of each point of the square. Ether witch way you do want to keep track of each point of the rectangle to ensure a better and more accurate collision detection and response.

Hope this helps Regards jouei.

###
#3
Members - Reputation: **567**

Posted 07 September 2009 - 02:54 AM

For circles, you don't need the square root. Just compare the square of the distance with the square of the radius. You also don't need to make sure you're subtracting the smaller value from the larger when finding the distance, because if you do it the other way around you'll just end up with a negative, and (-x)^2 = x^2 so it makes no difference after you square it. So you get something like this:

Your idealic (whatever that means) square solution seems fine, for determining that the squares are NOT intersecting. Depending on your coordinate system I suppose, I'm assuming positive right and up. You lost me with the flaw stuff.

As for square (axis aligned box) vs circle tests, it's really just a case of finding the point within the square closest to the centre of the circle. I'll let you think about it.

if (square(a.x - b.x) + square(a.y - b.y) < square(a.radius + b.radius))

Your idealic (whatever that means) square solution seems fine, for determining that the squares are NOT intersecting. Depending on your coordinate system I suppose, I'm assuming positive right and up. You lost me with the flaw stuff.

As for square (axis aligned box) vs circle tests, it's really just a case of finding the point within the square closest to the centre of the circle. I'll let you think about it.

###
#4
Members - Reputation: **142**

Posted 07 September 2009 - 05:50 AM

Thank you both for the responses! the collision tutorials using SAT look very interesting although im certainly not at a stage where I should delve into collision calculations that are so powerful and intricate im not prepared yet, I have downloaded those tutorials and the code and documentation because I am definetely looking into using that stuff, im going to try and apply it in a 3D environment when I am comfortable with all my DX code.

I am going to use simple circles for this asteroids game as its quite simplistic in design and more a test of my games architecture and graphics for the time being. The circle to box corner concept makes sense thank you for the corrections you made to my distance calculation RAZORUNREAL the coordinate system is positive x and y.

The flawwed part is that to test for an intersection you need to define an edge to your shape using an if statement to create a 1 pixel large plane down each edge of the shape, you need to have 4 parts to every edge you define thats 8 sides and if statements with 32 ands and ors between them to confirm that two edges are intersecting between the two squares. Is there a more efficient way than this to do square calculations was my question. Is there a simpler way to identify intersection between the two squares.

I am going to use simple circles for this asteroids game as its quite simplistic in design and more a test of my games architecture and graphics for the time being. The circle to box corner concept makes sense thank you for the corrections you made to my distance calculation RAZORUNREAL the coordinate system is positive x and y.

The flawwed part is that to test for an intersection you need to define an edge to your shape using an if statement to create a 1 pixel large plane down each edge of the shape, you need to have 4 parts to every edge you define thats 8 sides and if statements with 32 ands and ors between them to confirm that two edges are intersecting between the two squares. Is there a more efficient way than this to do square calculations was my question. Is there a simpler way to identify intersection between the two squares.

###
#5
Members - Reputation: **1092**

Posted 07 September 2009 - 08:47 AM

Don't forget that you also need to

Either way, if you haven't read this article yet, then give it a go. It's a very clear explanation of the separating axis theorem, with interactive examples, and a good explanation about box-box and circle-box collision checks (those cases lend themselves for some particular simplifications).

*react*to collisions - detecting them alone is often not enough, so going for the simplest collision check possible may not be what you really need.Either way, if you haven't read this article yet, then give it a go. It's a very clear explanation of the separating axis theorem, with interactive examples, and a good explanation about box-box and circle-box collision checks (those cases lend themselves for some particular simplifications).

Create-ivity - a game development blog Mouseover for more information.

###
#6
Members - Reputation: **202**

Posted 07 September 2009 - 11:26 PM

If it's a simple asteroids game then the efficiency might not matter too much - modern computers are fast enough that for a 2-D asteroids game you can implement the test that fits the game best or that you understand the best rather than simply the most efficient. Of course, you should always have efficiency in the back of your mind somewhere but unless you have hundreds or thousands of colliding objects (in which case you'd have to look into broad-phase collision checking anyhow) it's not really going to matter if you save a few CPU cycles.

For my 2D asteroids-ish shooter I used concave polygon tests because it allowed me to define simple but close-fitting polygons so I could have irregularly-shaped objects with accurate collision detection.

For my 2D asteroids-ish shooter I used concave polygon tests because it allowed me to define simple but close-fitting polygons so I could have irregularly-shaped objects with accurate collision detection.

###
#7
Members - Reputation: **567**

Posted 08 September 2009 - 12:56 AM

Ah, you want to test between hollow squares rather than solid boxes? I don't see why you need that for asteroids. Anyway, lets look at determining that they don't intersect. There are only a few options:

1. The squares are separated on the x or y axes (you know how to check this already)

2. Square a is entirely inside square b

3. Square b is entirely inside square a

If none of those are true, then the squares are intersecting.

1. The squares are separated on the x or y axes (you know how to check this already)

2. Square a is entirely inside square b

3. Square b is entirely inside square a

If none of those are true, then the squares are intersecting.

###
#8
Members - Reputation: **142**

Posted 09 September 2009 - 04:45 AM

Thanks again for the responses.

The squares are solid not hollow you create a group of if statements offset from the point the square is drawn too in order to detect collisions, there isn't a simpler way of detecting if two square sprites that arn't drawn to a polygon are intersecting. Loading models comes later.

I am thinking if I scan through all the objects that are asteroids and ships detect the shapes in a circle radius around them and cycle through those to see if they are intersecting with a tighter circle or square (based on the object) it would be faster than cycling through everything to see if its intersecting something else its still got the potential to cycle on every object n to the power of n times but it should reduce the amount of effort happening when lots of bullets are flying around, abit rustic but it will get the job done well enough! :) Thank you again for the links to SAT.

The squares are solid not hollow you create a group of if statements offset from the point the square is drawn too in order to detect collisions, there isn't a simpler way of detecting if two square sprites that arn't drawn to a polygon are intersecting. Loading models comes later.

I am thinking if I scan through all the objects that are asteroids and ships detect the shapes in a circle radius around them and cycle through those to see if they are intersecting with a tighter circle or square (based on the object) it would be faster than cycling through everything to see if its intersecting something else its still got the potential to cycle on every object n to the power of n times but it should reduce the amount of effort happening when lots of bullets are flying around, abit rustic but it will get the job done well enough! :) Thank you again for the links to SAT.

###
#9
Members - Reputation: **142**

Posted 09 September 2009 - 08:36 AM

Thank you all for giving me a better idea about how to do collision detection and a more realistic idea of how its done in 3d by people not plugging in other peoples physics engines.

I do not know why I got such heavy programmers block over such a simple concept but im writing down how to check for an intersection between two squares in a function just so I dont ever overlook such simple code again. It only identifies if two squares are intersecting it tells you nothing of what parts of the square have intersected the other but as my space ship works off of a direction angle I can just invert the angle to reflect the ship off of an asteroid.

Now I have this simple code figured out I can use it to identify quickly what objects are local to other objects by expanding the size of the square beyond the size of the sprite and if thay are local put them through better collision detection to see if they are intersecting such as circles :p. So long as the squares are equal size being parallel to the other square should not allow the condition to reach a state of being true. Its very rustic but I am not in 3D yet and so rustic is for the moment good. I sense SAT in my distant future.

In my function where two objects are passed

int totalTrue = 0;

if (objectA.x + objectA.width < objectB.x)

totalTrue++;

if (objectA.x > objectB.x + objectB.width)

totalTrue++;

if (objectA.y < objectB.y + objectB.height)

totalTrue++;

if (objectA.y + objectA.height > objectB.y)

totalTrue++;

if (totalTrue >= 2)

return intersected //Now I need to use a radius to guage if they are touching :D

return none intersected shapes.

Thanks again everyone im deeming this problem solved.

I do not know why I got such heavy programmers block over such a simple concept but im writing down how to check for an intersection between two squares in a function just so I dont ever overlook such simple code again. It only identifies if two squares are intersecting it tells you nothing of what parts of the square have intersected the other but as my space ship works off of a direction angle I can just invert the angle to reflect the ship off of an asteroid.

Now I have this simple code figured out I can use it to identify quickly what objects are local to other objects by expanding the size of the square beyond the size of the sprite and if thay are local put them through better collision detection to see if they are intersecting such as circles :p. So long as the squares are equal size being parallel to the other square should not allow the condition to reach a state of being true. Its very rustic but I am not in 3D yet and so rustic is for the moment good. I sense SAT in my distant future.

In my function where two objects are passed

int totalTrue = 0;

if (objectA.x + objectA.width < objectB.x)

totalTrue++;

if (objectA.x > objectB.x + objectB.width)

totalTrue++;

if (objectA.y < objectB.y + objectB.height)

totalTrue++;

if (objectA.y + objectA.height > objectB.y)

totalTrue++;

if (totalTrue >= 2)

return intersected //Now I need to use a radius to guage if they are touching :D

return none intersected shapes.

Thanks again everyone im deeming this problem solved.

###
#10
Members - Reputation: **1092**

Posted 09 September 2009 - 11:06 AM

Quote:

Original post by EnlightenedOne

Now I have this simple code figured out I can use it to identify quickly what objects are local to other objects by expanding the size of the square beyond the size of the sprite and if thay are local put them through better collision detection to see if they are intersecting such as circles :p.

You might as well use circle-circle checks in the first place then. Both AABB-AABB and circle-circle tests are fairly simple and are roughly similar in terms of accuracy.

AABB-AABB tests allow you to break out early bytheway (I'm not sure why you're keeping a counter around, and why you think that 'counter >= 2' would indicate a collision):

return a.x + a.width > b.x && a.x < b.x + b.width && a.y + a.height > b.y && a.y < b.y + b.height;

Which is the slightly obfuscated version of:

return a.right > b.left and a.left < b.right and a.top > b.bottom and a.bottom < b.top;

If any of these statements is false, there is no collision, and the function will bail out, returning false. Your original code used or's instead of and's, which is why it fails. The boxes need to overlap on both the x

*and*y axis (their projections), not the x

*or*y axis.

Create-ivity - a game development blog Mouseover for more information.

###
#11
Members - Reputation: **106**

Posted 09 September 2009 - 11:10 AM

Now that the question is resolved, I would like to make a comment:

When you were describing the distance formula, I actually was momentarily lost. You won't have to worry about losing most of the people on here if you simply state the formula, because most people on here know what it is.(square root((x2-x1)^2+(y2-y1)^2) is a good way to do it.)

Thank you.

When you were describing the distance formula, I actually was momentarily lost. You won't have to worry about losing most of the people on here if you simply state the formula, because most people on here know what it is.(square root((x2-x1)^2+(y2-y1)^2) is a good way to do it.)

Thank you.

###
#12
Members - Reputation: **142**

Posted 10 September 2009 - 08:29 AM

Well I started looking over your code Captain P thinking it would not work for some reason I seem to have a terrible time getting to grips with a relatively simple concept and im not entirely sure why myself. I had the preconception that the code would only meet all the conditions if one square was ontop of the other I had to do example to get it through my head. But yes thank you for pointing out how terribly unnecessary that would have been.

I will include a formula representation of anything I am going over in the future calculations Aezon :)

I will include a formula representation of anything I am going over in the future calculations Aezon :)

###
#14
Members - Reputation: **535**

Posted 10 September 2009 - 08:55 AM

it stands for "Axis aligned bounding box". An AABB is made up of a minimum point and a maximum point and the walls of the box are all paralel with an axis but it doesn't have to be square.

you might also see another term "OBB" which stands for "Oriented bounding box" which is just a rotated AABB.

HTH! (:

you might also see another term "OBB" which stands for "Oriented bounding box" which is just a rotated AABB.

HTH! (: