|
Memberlist | Forum Rules | Search | Today's Posts | Mark Forums Read |
Search Forums: | Click here to use Advanced Search |
|
Thread Tools | Display Modes |
11-08-2010, 01:54 PM | #1 | ||
Join Date: Oct 2004
Location: Opole, Poland
Posts: 14,276
|
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; } |
||
|
|
13-08-2010, 06:46 PM | #2 | ||
Join Date: Nov 2007
Location: Etten, Netherlands
Posts: 42
|
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); } 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):
|
||
|
|