Allegro.cc - Online Community

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

This thread is locked; no one can reply to it. rss feed Print
 1   2 
Circular collision detection
Taiko Keiji
Member #8,307
February 2007
avatar

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
avatar

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
avatar

[edit] Yeah I'm sleepy. :P

------------
Solo-Games.org | My Tech Blog: The Digital Helm

Jakub Wasilewski
Member #3,653
June 2003
avatar

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
avatar

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
avatar

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
avatar

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
avatar

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
avatar

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 :D
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
avatar

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
avatar

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 <cmath>
2#include <iostream>
3 
4using namespace std;
5 
6namespace {
7 template<class T>
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 
14int 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
avatar

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
avatar

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
avatar

*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
avatar

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:

1struct SPHERE {
2 float x;
3 float y;
4 float r;
5};
6 
7#define noboxtest false; // set to true to benchmark without box test
8bool 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 
13template<class T> sqr(T a) { return a * a; }
14 
15bool 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 
19bool 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
avatar

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
avatar

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
avatar

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
avatar

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
avatar

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
avatar

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
avatar

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
avatar

Heh yea, noticed that afterwards... thanks (sorry Tobias!) ;)

Ben Delacob
Member #6,141
August 2005
avatar


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: