|
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- |
Jonatan Hedborg
Member #4,886
July 2004
|
Onewing
Member #6,152
August 2005
|
[edit] Yeah I'm sleepy. ------------ |
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 . --------------------------- |
Kikaru
Member #7,616
August 2006
|
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.:'( --------------------------- |
ImLeftFooted
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. |
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. Life could be better, machines could program themselves. Taiko Keiji- |
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
|
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- |
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)...
Output 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. --------------------------- |
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* -- |
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:
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. --- |
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" |
ImLeftFooted
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. _______________________________ |
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 )
__________________________________ |
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
|