• Create Account

FREE SOFTWARE GIVEAWAY

We have 4 x Pro Licences (valued at \$59 each) for 2d modular animation software Spriter to give away in this Thursday's GDNet Direct email newsletter.

Read more in this forum topic or make sure you're signed up (from the right-hand sidebar on the homepage) and read Thursday's newsletter to get in the running!

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

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.

13 replies to this topic

### #1EnlightenedOne  Members   -  Reputation: 142

Like
0Likes
Like

Posted 07 September 2009 - 02:15 AM

### #2XainFaith  Members   -  Reputation: 102

Like
0Likes
Like

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.

### #3RAZORUNREAL  Members   -  Reputation: 567

Like
0Likes
Like

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

### #4EnlightenedOne  Members   -  Reputation: 142

Like
0Likes
Like

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.

### #5Captain P  Members   -  Reputation: 1092

Like
0Likes
Like

Posted 07 September 2009 - 08:47 AM

Don't forget that you also need to 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).

### #6shaolinspin  Members   -  Reputation: 202

Like
0Likes
Like

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.

### #7RAZORUNREAL  Members   -  Reputation: 567

Like
0Likes
Like

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.

### #8EnlightenedOne  Members   -  Reputation: 142

Like
0Likes
Like

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.

### #9EnlightenedOne  Members   -  Reputation: 142

Like
0Likes
Like

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.

### #10Captain P  Members   -  Reputation: 1092

Like
0Likes
Like

Posted 09 September 2009 - 11:06 AM

Quote:
 Original post by EnlightenedOneNow 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.

### #11Aezon  Members   -  Reputation: 106

Like
0Likes
Like

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.

### #12EnlightenedOne  Members   -  Reputation: 142

Like
0Likes
Like

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

### #13EnlightenedOne  Members   -  Reputation: 142

Like
0Likes
Like

Posted 10 September 2009 - 08:52 AM

Out of curiosity what does AABB stand for?

### #14Atrix256  Members   -  Reputation: 510

Like
0Likes
Like

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! (:

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