Jump to content


Radius Based Collision Detection Algorithms


4 replies to this topic

#1 the_fifth_horseman

the_fifth_horseman

    Member Munchkin

  • Members
  • PipPipPip
  • 59 posts

Posted 11 August 2010 - 10:42 AM

Hey, everyone.
I'm assisting another guy with making a 2d action game, but there is a small disagreement as to how we should be handling collision detections. One of us has his approach, the other has his, both of us think theirs is faster.
Assuming the collision detection runs for all objects on the map (because it does).
Which of these solutions is more effective? Is there a better way to do it?
  bool check_collision(int x1, int y1, int x2, int y2, int r1, int r2) { 
float d_x=x1-x2, d_y=y1-y2;
if &#40;sqrt&#40;d_x*d_x+d_y*d_y&#41;<r1+r2&#41; return true;
else return false; }
bool check_collision&#40;int x1, int y1, int x2, int y2, int r1, int r2&#41;{
		  int d_x=abs&#40;x1-x2&#41;, r_t=r1+r2;
		  if &#40;d_x<r_t&#41; { int d_y=abs&#40;y1-y2&#41;;
						 if &#40;d_y<r_t&#41; { if &#40;d_x*d_x+d_y*d_y<r_t*r_t&#41; return true;
										else return false; } 
						 else return false; } } 
		  else return false; }


#2 Qbix

Qbix

    AR-coholic

  • Members
  • PipPipPipPipPipPip
  • 605 posts

Posted 11 August 2010 - 06:52 PM

why convert to floats and take the sqrt ?
bool check_collision&#40;int x1, int y1, int x2, int y2, int r1, int r2&#41; {
   signed int d_x=x1-x2, d_y=y1-y2, r=r1+r2;
   if &#40;&#40;d_x*d_x+d_y*d_y&#41;<r*r&#41; return true;
   else return false; 
}
Aside from the question which is faster.

#3 the_fifth_horseman

the_fifth_horseman

    Member Munchkin

  • Members
  • PipPipPip
  • 59 posts

Posted 12 August 2010 - 08:15 AM

To be honest, both of us are - to a lesser or greater extent - improvising as we go along. It looked like a solution at the time.

#4 Japofran

Japofran

    A Usual Suspect

  • Members
  • PipPipPipPipPip
  • 412 posts

Posted 12 August 2010 - 06:56 PM

AFAIK the only correct answer to the "which is faster" questions is "test"; and the result may change depending on the platform.
..oO Mustached Crusader of the PEEKOCKSWOOZZLE Order Oo..
"STFU and show me your screenies!!"

#5 Japofran

Japofran

    A Usual Suspect

  • Members
  • PipPipPipPipPip
  • 412 posts

Posted 13 August 2010 - 04:50 PM

Anyway IMO--and I'm NO expert in programming--there's little chance that this is a performance bottleneck for the game (compared for example to graphical output), that is there may be no noticeable performance gain overall even if you double performance for this step.

Anyway... I agree that taking the square root will always be slower than squaring, AFAIK.

About the "which" question, for a game I'd bet for the first approach, for a purely calculator program I'd bet for the second one. In principle, unless the case of a collision changes momentarily or permanently the routine, so you have more leeway until the next check. The second approach tries to minimize the load along the whole time, which is good. But in a game it's no good being faster if it gets slower in any particular situation (a collision in this case). I a player sees a responsive program that gets jaggy at any particular critical time, the game will be as bad as if it were jaggy all the time. And since the second option needs of additional light-duty checks to decide whether to perform the heavy-duty one, in this critical situation the first one will be slightly slower actually.

By the way, this kind of game could benefit from object orientation... But that's another story and you have already made that design decision.

Also nowadays you can run tasks in parallel (multi-thread).
..oO Mustached Crusader of the PEEKOCKSWOOZZLE Order Oo..
"STFU and show me your screenies!!"




Reply to this topic



  


Skin Designed By Evanescence at IBSkin.com