Hey people,
Currently, I'm working on a space scroller shoot-em-up and need some really fast collision detection algorithms.
Basically, it needs to be able to handle about 1,000 ships and 1,000 bullets. Currently, my code offers only 50fps when this is happening, and I'd like it to be closer to 100 at least.
The algorithm I'm using at the moment gets a ship and does a binary search to find all bullets within the range of colliding with the ship. By itself, it takes ~15ms(by itself it seems to run in 8ms, not sure why there's so much difference. Probably cache or something?) to run, then there's the updating of ships and the AI and other stuff to do.
Basically, I just want to know if there's anything out there right now I can use to increase the throughput?
Thanks!
Super fast collision detection
I think you would realize large gains by partitioning your space before collision detection. I suggest a BSP tree.
Author
I probably should've mentioned, but it's for a 2d game. Can you still use a binary space partition for 2d stuff?
My knowledge of BSP tree's is veery limited, but if it's the next step I guess I don't have much choice.
EDIT: In this game, there's no closed areas. It's totally open, basically a gigantic flat area. Are BSP tree's still applicable?
My knowledge of BSP tree's is veery limited, but if it's the next step I guess I don't have much choice.
EDIT: In this game, there's no closed areas. It's totally open, basically a gigantic flat area. Are BSP tree's still applicable?
Yeah bsp's work in 2d but probably overkill and inappropriate for your game.
Grids, quad trees, spatial hashing and scene graphs also work in 2d though, you probably want one of them.
Basically you just need some algorithm that breaks apart your game universe into sections (either 1 level as with a grid or recursively as with a tree) so that when you are querying for objects in an area for collision detection, it only checks against objects that are reasonably close.
Check out "sweep and prune" too, that might help you out.
That ought to get you where you want to be for collision detection. For rendering and logic, if you can, only update the guys that are close to the screen's position. Or if you must do logic on all ships even if they are far away, try to do logic on them less often (ie once every 4 frames instead of every frame... and stagger them out so you do 1/4th of them each frame).
Also, question.. why do you want 100fps? Do you know that vsync will cap you out at 60fps?
Hope this info is helpful to you!
-Atrix
Grids, quad trees, spatial hashing and scene graphs also work in 2d though, you probably want one of them.
Basically you just need some algorithm that breaks apart your game universe into sections (either 1 level as with a grid or recursively as with a tree) so that when you are querying for objects in an area for collision detection, it only checks against objects that are reasonably close.
Check out "sweep and prune" too, that might help you out.
That ought to get you where you want to be for collision detection. For rendering and logic, if you can, only update the guys that are close to the screen's position. Or if you must do logic on all ships even if they are far away, try to do logic on them less often (ie once every 4 frames instead of every frame... and stagger them out so you do 1/4th of them each frame).
Also, question.. why do you want 100fps? Do you know that vsync will cap you out at 60fps?
Hope this info is helpful to you!
-Atrix
Author
Hmm, alot of excellent suggestions. I'll definitely go and look at either setting up a grid or making some sort of tree.
As for the vsync, that's a good point, i'd not thought of that. Most systems these days use LCD's so yeah. Maybe 60fps should be my goal.
I've considered grids and spatial hashing, but haven't tried to implement. That'll be my goal now I think.
Thanks for all the suggestions, I should be able to get where I want to go now :D
As for the vsync, that's a good point, i'd not thought of that. Most systems these days use LCD's so yeah. Maybe 60fps should be my goal.
I've considered grids and spatial hashing, but haven't tried to implement. That'll be my goal now I think.
Thanks for all the suggestions, I should be able to get where I want to go now :D
"As for the vsync, that's a good point, i'd not thought of that. Most systems these days use LCD's so yeah. Maybe 60fps should be my goal. "
For the record vsync existed before LCD's, there's nothing special about LCD's and vsync... it was on CRT's too :P
For the record vsync existed before LCD's, there's nothing special about LCD's and vsync... it was on CRT's too :P
What algorithm do you use for collision detection?
Using the separating axis theorem you can gain a few cycles when things aren't colliding. Also with collision spheres you shouldn't use sqrt() instead square the combined radius.
Don't know if you already know this, so don't be offended if you think its obvious.
Some of my code
Not sure how optimal sphere on box collision is though...
Using the separating axis theorem you can gain a few cycles when things aren't colliding. Also with collision spheres you shouldn't use sqrt() instead square the combined radius.
Don't know if you already know this, so don't be offended if you think its obvious.
Some of my code
static inline float Abs(float value){ if(value < 0) return -value; return value;}static inline float clamp(float min, float max, float value){ if(value < min) return min; if(value > max) return max; return value;}bool AxisAlignedBox::Intersect(const AxisAlignedBox& box)const{ if( min_x > box.max_x ) return false; if( box.min_x > max_x ) return false; if( min_y > box.max_y ) return false; if( box.min_y > max_y ) return false; if( min_z > box.max_z ) return false; if( box.min_z > max_z ) return false; return true;}bool Sphere::Intersect(const Sphere& sphere)const{ float both_radius = radius + sphere.radius; if( Abs(position_x - sphere.position_x) > both_radius ) return false; else if( Abs(position_y - sphere.position_y) > both_radius ) return false; else if( Abs(position_z - sphere.position_z) > both_radius ) return false; float distance_x = position_x - sphere.position_x; float distance_y = position_y - sphere.position_y; float distance_z = position_z - sphere.position_z; float distance_squared = distance_x * distance_x + distance_y * distance_y + distance_z * distance_z; if( distance_squared > both_radius * both_radius ) return false; return true;}bool Sphere::Intersect(const AxisAlignedBox& box)const{ if( box.min_x > position_x + radius ) return false; else if( box.max_x < position_x - radius ) return false; else if( box.min_y > position_y + radius ) return false; else if( box.max_y < position_y - radius ) return false; else if( box.min_z > position_z + radius ) return false; else if( box.max_z < position_z - radius ) return false; float closest_point_on_box_x = clamp(box.min_x, box.max_x, position_x); float closest_point_on_box_y = clamp(box.min_y, box.max_y, position_y); float closest_point_on_box_z = clamp(box.min_z, box.max_z, position_z); float distance_x = closest_point_on_box_x - position_x; float distance_y = closest_point_on_box_y - position_y; float distance_z = closest_point_on_box_z - position_z; float distance_squared = distance_x * distance_x + distance_y * distance_y + distance_z * distance_z; if( distance_squared > radius * radius ) return false; return true;}Not sure how optimal sphere on box collision is though...
Author
Quote:Original post by Atrix256
"As for the vsync, that's a good point, i'd not thought of that. Most systems these days use LCD's so yeah. Maybe 60fps should be my goal. "
For the record vsync existed before LCD's, there's nothing special about LCD's and vsync... it was on CRT's too :P
Haha, I know that :p My point was simply that LCD's have a default VSYNC of 60. whereas CRT's where higher, and therefore 60fps should be perfectly sufficient.
@Net-Ninja,
I didn't realise you could do that (with the sqrt) but I've been using the separate axis idea for a bit.
The current operation works like this:
Sort the list of ships by their X values.
Get a bullet.
Get the index of the minimum X value, using a binary search, that will collide with the bullet
Get the index of the maximum X value, using a binary search, that will collide with the bullet
Using the two indices in the array, do a brute force comparison between the two array indices
Code looks like this:
double width = baddies[0].getClipBoundsWidth(); double height = baddies[1].getClipBoundsHeight(); int xMinIndex = BSearch.min(xSort, (int)locationX, (int)width); int xMaxIndex = BSearch.max(xSort, (int)locationX, (int)width); if(xMinIndex == -1) return null; if(xMaxIndex < 0) xMaxIndex = xMinIndex; //System.out.println("Searching between " + xMinIndex + " and " + xMaxIndex); for(int x = xMinIndex;x <= xMaxIndex;++x) { if(baddies[xPtrs[x]].dgetY() + width > locationY && baddies[xPtrs[x]].dgetY() - width < locationY) { return baddies[xPtrs[x]]; } } return null;FYI: I use java to do spikes, if they look promising I port them into my game. I have a simple framework set up to do tests on multiple different collisions detection schemes and report the results.
Also, I found that the collision detection like this was bound by calls to getX() and getY(), so I extracted the xvalues into an array (which is what the bsearch operates on).
Does that mean that the ships only have a point in them? since you can sort them by their x value. If this works it only works because all ships have the same width.
Not to sure about how good it is to be sorting it all the time though, memory management can be costly. It is more common for things not to collide which is why the code that I posted is fast. If your lucky you only need one comparison per object. If you still need more speed you could always do a BSP, quadtree or occtree to divide the objects into different spaces and only check collision with objects in the same space.
Not to sure about how good it is to be sorting it all the time though, memory management can be costly. It is more common for things not to collide which is why the code that I posted is fast. If your lucky you only need one comparison per object. If you still need more speed you could always do a BSP, quadtree or occtree to divide the objects into different spaces and only check collision with objects in the same space.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
