Allegro.cc Forums » Game Design & Concepts » Circular collision detection

 This thread is locked; no one can reply to it. 1   2
 Circular collision detection
 Taiko Keiji Member #8,307 February 2007 I'm making an RPG with a type of battle system that has the character surrounded by a circle showing their attack radius. How can I effectively check to see if another sprite is inside the circle? Life could be better, machines could program themselves.Taiko Keiji-http://lostotaku.net
 Jonatan Hedborg Member #4,886 July 2004 Basic pyth math... ```if( pow(c_x-test_x,2) + pow(c_y-test_y,2) < pow(radius,2) ) { //inside } else { //not inside } ``` You don't actually need to use pow() - just multiply them with them selves, this was faster to write though -------Sweden: Free from the shackles of Democracy since 2008-06-18!
 Onewing Member #6,152 August 2005  Yeah I'm sleepy. ------------Solo-Games.org | My Tech Blog: The Digital Helm
 Jakub Wasilewski Member #3,653 June 2003 Quote: pow(c_x-test_x,2) Argh! He asked how to do this effectively .You shouldn't use pow for integer powers, especially for the second power which is just one *. Well, the compiler could optimise it to * anyway, I guess... But that would be too much to count on.[EDIT] Hm, did you edit, or is it my inability to read an entire post? Sorry either way . ---------------------------[ ChristmasHack! | My games ] :::: One CSS to style them all, One Javascript to script them, / One HTML to bring them all and in the browser bind them / In the Land of Fantasy where Standards mean something.
 Kikaru Member #7,616 August 2006 You can do it pretty effectively with an octagon: ```if ((abs(x1-x2) < d1)&&(abs(y1-y2) < d1)&&(abs(x1-x2)+abs(y1-y2) < d2) return true; ``` Just tweak the values of d1 and d2, and you can make fast, effective, almost-circular collision detection.
 Jakub Wasilewski Member #3,653 June 2003 Hm, that can actually be slower on new hardware, because of the inherent branching in abs. Four "if"s can be worse than three multiplications if branch prediction fails. Well, two multiplications, because you can store the attack radius squared as it's (I think) constant.:'( ---------------------------[ ChristmasHack! | My games ] :::: One CSS to style them all, One Javascript to script them, / One HTML to bring them all and in the browser bind them / In the Land of Fantasy where Standards mean something.
 Dustin Dettmer Member #3,935 October 2003 ```const int dx = c1_x - c2_x; const int dy = c1_y - c2_y; const int dist = c1_radius + c2_radius; if(dx * dx + dy * dy < dist * dist) .. We have a collision! .. ``` Circle collisions are the fastest of the collision detection schemes. Don't use octagons. * fixed a typo having to do with squaring the radius(plural sp?) before adding them.
 Taiko Keiji Member #8,307 February 2007 so c1_x would be for circle 1 and c2_x is for circle two?I understand... sorta. What if you want to do a collision veetween a circle and a rectangle?would you just test the circle against the square? Life could be better, machines could program themselves.Taiko Keiji-http://lostotaku.net
 Jonatan Hedborg Member #4,886 July 2004 It's not really a "collision" test. More like a "overlap" test. But anyway... Quote: would you just test the circle against the square? Uhm, yeah. That's pretty much what you do. Only i have no idea how to do it You probably check against the closest point of the square or test all lines. Dunno. -------Sweden: Free from the shackles of Democracy since 2008-06-18!
 Taiko Keiji Member #8,307 February 2007 It's all the game designers fault. I'm gonna go curse him out now then continue trying to figure it out.:'( Life could be better, machines could program themselves.Taiko Keiji-http://lostotaku.net
Carrus85
Member #2,633
August 2002

Quote:

Hm, that can actually be slower on new hardware, because of the inherent branching in abs. Four "if"s can be worse than three multiplications if branch prediction fails. Well, two multiplications, because you can store the attack radius squared as it's (I think) constant.:'(

Really? Because abs can be written without any branches at all (provided your system has a CMP instruction)...

 1 #include 2 #include 3 4 using namespace std; 5 6 namespace { 7 template 8 T myabs(T x) { 9 // !! makes sure this value is either zero or one for weird-behaving systems 10 return x - 2 * !!(x < 0) * x; 11 } 12 } 13 14 int main() { 15 cout << "abs(-31) " << abs(-31) << endl; 16 cout << "myabs(-31) " << myabs(-31) << endl; 17 cout << "abs(-3.1) " << abs(-3.1) << endl; 18 cout << "myabs(-3.1) " << myabs(-3.1) << endl; 19 return 0; 20 }

Output

```abs(-31)    31
myabs(-31)  31
abs(-3.1)   3.1
myabs(-3.1) 3.1
```

Whether or not that is more efficient is yet to be determined, though...

 Jakub Wasilewski Member #3,653 June 2003 Quote: provided your system has a CMP instruction CMP usually doesn't work that way. It doesn't give you a 0 or 1 to store in a register and multiply by, it just sets some flags in a special flags register - which usually can't be the source/target of any computation. The conventional way to use the flags register is conditional jumps, aka branches.But I admit, on modern architectures you can do it without branches in a multitude of ways. On newer x86, one way that immediately comes to mind is CMOV (however, CMOV might internally behave like a branch, with prediction, prediction misses and all). And for floating point, there is always FABS which is there from way back to the times of 8087 I think.So, my bad. I didn't think it through properly (like the majority of my posts lately... something's wrong with me).Anyway, there is no reason to sacrifice accuracy for an improbable speed-up (I don't think even FABS is faster than FMUL, but I might be wrong again), at least not until it becomes a bottleneck. ---------------------------[ ChristmasHack! | My games ] :::: One CSS to style them all, One Javascript to script them, / One HTML to bring them all and in the browser bind them / In the Land of Fantasy where Standards mean something.
 Carrus85 Member #2,633 August 2002 Quote: CMP usually doesn't work that way. It doesn't give you a 0 or 1 to store in a register and multiply by, it just sets some flags in a special flags register - which usually can't be the source/target of any computation. The conventional way to use the flags register is conditional jumps, aka branches. This is understood; although, it really depends on the system in question. The point was that there are other ways to calculate abs that doesn't require branching, and therefore cannot suffer from branch prediction problems.
 Kitty Cat Member #2,815 October 2002 *cough*Floats, as far as IEEE-whatever non-two's-compliment, as PCs are, can also be abs'd by simply clearing the top bit (AFAIK). -- "Do not meddle in the affairs of cats, for they are subtle and will pee on your computer." -- Bruce Graham
Tobias Dammers
Member #2,604
August 2002

Quote:

Circle collisions are the fastest of the collision detection schemes. Don't use octagons.

Depends. Octagons; no. But a bounding box before the actual circle may prove faster, especially since most box tests fail (so branch misprediction is not THAT big of a deal). I'd say give it a try:

 1 struct SPHERE { 2 float x; 3 float y; 4 float r; 5 }; 6 7 #define noboxtest false; // set to true to benchmark without box test 8 bool boxtest(const SPHERE& a, const SPHERE& b) { 9 return (a.x + a.r > b.x - b.r) && (a.x - a.r < b.x + b.r) && 10 (a.y + a.r > b.y - b.r) && (a.y - a.r < b.y + b.r); 11 } 12 13 template sqr(T a) { return a * a; } 14 15 bool spheretest(const SPHERE& a, const SPHERE& b) { 16 return sqr(a.x - b.x) + sqr(a.y - b.x) < sqr(a.r + b.r); 17 } 18 19 bool collision_test(const SPHERE& a, const SPHERE& b) { 20 if (noboxtest || boxtest(a, b)) 21 return spheretest(a, b); 22 return false; 23 }

Now go and benchmark this thing, once with box test enabled and once without. See which one is faster with data that resembles what you expect.

---
Me make music: Triofobie
---
"We need Tobias and his awesome trombone, too." - Johan HalmÃ©n

 Neil Black Member #7,867 October 2006 Collision detection is the hardest thing I've done (using math) in programming to date. I don't know how to check collision with a circle, and all the code on this site is just a jumble of variables and numbers! When asked how to collide a circle with a rectangle the answer was to check collision with the closest part of the recatangle, but I don't even know how to find that! I'm fairly good at math, but I haven't had the opportunity to learn any of this stuff yet. I'M IGNORANT!!!!! Is there any website out there that goes over this kind of math in a simple, easy to understand way?
 GullRaDriel Member #3,861 September 2003 www.google.com "Code is like shit - it only smells if it is not yours"Allegro Wiki, full of examples and articles !!
 Dustin Dettmer Member #3,935 October 2003 I'd recommend buying a math textbook that is just past the last level you finished and reading.Then repeat the operation (with higher-level textbooks) until you can fully understand what we're all talking about.
 Paul Pridham Member #250 April 2000 Quote: ```bool spheretest(const SPHERE& a, const SPHERE& b) { return sqr(a.x - b.x) + sqr(a.y - b.x) < sqr(a.r + b.r); } ``` Don't use sqr() (as Dustin already pointed out above).```bool spheretest(const SPHERE& a, const SPHERE& b) { return (a.x - b.x) * (a.x - b.x) + (a.y - b.x) * (a.y - b.x) < (a.r + b.r) * (a.r + b.r); } ```
 Neil Black Member #7,867 October 2006 Buy? A textbook? Those things are like, \$40-60! I don't have that kind of money! I don't have any kind of money! I've even lost all my Monopoly money!As for using google, I'm not even sure what this kind of math is called! Is it geometry or trigonometry? Or some wierd kind of quasipsychometry? Yes, I invented a word! Look, a whole post without a single period!
 James Stanley Member #7,275 May 2006 Quote: It's all the game designers fault As programmer, you have the hardest job. Therefore, you should design the game to make it easier on yourself.
 Indeterminatus Member #737 November 2000 Quote: Don't use sqrt() (as Dustin already pointed out above). Fixed it for you. Tobias' example is perfectly fine. _______________________________Indeterminatus. [Atomic Butcher]si tacuisses, philosophus mansisses
 Paul Pridham Member #250 April 2000 Heh yea, noticed that afterwards... thanks (sorry Tobias!)
 Ben Delacob Member #6,141 August 2005 ``` Beginners, look for information on the Pythagoran theorem. In a right triangle (one with a 90 degree angle), side lengths a, b, and c (where c is the long side called the hypotenuse) a^2 + b^2= c^2 1 |\ | \ | \ | \ | c\ |a \ | \ |___b___\2 So if you can figure out the lengths of a and b, you know c. This is actually the central concept in circular collision detection. The distance from point 1 to point 2 is: the square root of (x distance squared + y distance squared): sqrt( (2.x- 1.x)^2 + (2.x- 1.x)^2 ) ``` __________________________________Allegro html mockup code thread -website-"two to the fighting eighth power"
 orz Member #565 August 2000 Quote: Buy? A textbook? Those things are like, \$40-60! I don't have that kind of money! I don't have any kind of money! I've even lost all my Monopoly money!As for using google, I'm not even sure what this kind of math is called! Is it geometry or trigonometry? Or some wierd kind of quasipsychometry? Yes, I invented a word! Look, a whole post without a single period! According to wikipedia, the Pythagorean Theorem is euclidean geometry. In practice, I think I learned it in algebra class, though it was more important in trig class. There's lots of free resources on the web, but finding ones that are actually understandable, particularly for your level of knowledge, may take quite a bit of work. I generally have the best results with programmer oriented sites and wikipedia. Things that come up when I search for "tutorial" are also often useful. A brief googling for online math textbook turned up a site with free PDFs of math textbooks (http://www.math.gatech.edu/~cain/textbooks/onlinebooks.html), but none looked appropriate for you.
 1   2  Go to: Allegro Development Installation, Setup & Configuration Allegro.cc Comments Off-Topic Ordeals The Depot Game Design & Concepts Programming Questions Recent Threads