Go Back   Forums > Community Chatterbox > Tech Corner > Programming
Memberlist Forum Rules Search Today's Posts Mark Forums Read
Search Forums:
Click here to use Advanced Search

Reply
 
Thread Tools Display Modes
Old 11-08-2010, 01:54 PM   #1
The Fifth Horseman
FUTURE SCIENCE BASTARD
 
The Fifth Horseman's Avatar


 
Join Date: Oct 2004
Location: Opole, Poland
Posts: 14,276
Default Collision detection algorithms

Assuming the collision detection runs for all objects on the map (because it does; neither programmer has much of an idea how to optimize that).
Which of these solutions is more effective? Is there a better way to do it?
Code:
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 (sqrt(d_x*d_x+d_y*d_y)<r1+r2) return true;
else return false; }
Code:
bool check_collision(int x1, int y1, int x2, int y2, int r1, int r2){
          int d_x=abs(x1-x2), r_t=r1+r2;
          if (d_x<r_t) { int d_y=abs(y1-y2);
                         if (d_y<r_t) { if (d_x*d_x+d_y*d_y<r_t*r_t) return true;
                                        else return false; }
                         else return false; }
__________________

"God. Can't you people see I'm trying to commit a crime against science and nature here?"
-- Reed Richards
The Fifth Horseman is offline                         Send a private message to The Fifth Horseman
Reply With Quote
Old 13-08-2010, 06:46 PM   #2
Kippesoep
Forum hobbit
 
Kippesoep's Avatar


 
Join Date: Nov 2007
Location: Etten, Netherlands
Posts: 42
Default

Well, eliminating the square root is a good idea, but you're doing it rather inefficiently. This would be a lot easier. Note that there's no need for floating point math (if your coordinates remain under 32768).
Code:
bool check_collision (int x1, int y1, int x2, int y2, int r1, int r2)
{
    int dx = x2 - x1;
    int dy = y2 - y1;
    int sr = r1 + r2;
    return (dx * dx + dy * dy) < (sr * sr);
}
BUT! You're optimising the wrong thing here...

Sure, there are some small gains to be made this way, but the more important thing is to reduce the amount of checks done in the first place. You said to assume that the collision check always runs, but that's a bad premise, especially if that means you're checking every single object against every other object. That has a big-O of n², which is bad. For 1000 objects, the amount of checks would be over half a million, which is ridiculous

Here's some a tip for an method to get that number down, assuming a 2D map (though extendable to 3D):
  1. create a collision grid the same size of your map, just coarser, so that each cell in the collision grid is larger than the largest object
  2. keep a reference to each object in the cell on the collision grid
  3. keep track of which objects have moved
  4. do a collision check only on other objects in the same cell on the collision grid and in directly neighbouring cells
Kippesoep is offline                         Send a private message to Kippesoep
Reply With Quote
Reply


Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Forum Jump
 


The current time is 10:53 AM (GMT)

 
Powered by vBulletin® Version 3.7.1
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.