Sign in to follow this  
Mogthew

Super fast collision detection

Recommended Posts

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!

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
"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

Share this post


Link to post
Share on other sites
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


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...

Share this post


Link to post
Share on other sites
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).

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Yes, all ships have the same width / height, which makes this work. I'm not entirely sure how you manage to do "one comparison per object if you're lucky", how is this achieved? The sorting doesnt take too long, the memory is initialized at start up and then only modified at a later time, it's not created or deleted.

Again, the code you posted is specific to check for object vs object collisions, there's nothing there that shows how to cull the object collision pairs down.

Could you explain further?

Share this post


Link to post
Share on other sites
You get one comparison if min_x > box.max_x, if not and box.min_x > max_x is true you get two comparisons and so on. So you will most likely get very few comparisons. In the cases where they actually collide they will ofcource check all the if statements and will have 6 comparisons. This is why axis aligned bounding boxes are so fast.

Separating axis theorem in short: They dont collide at all if they dont collide on any axis, ie. they only collide when they collide on all axises.

So in essence if they dont collide in the x axis you dont have to check that they collide in the y axis. That is a bit faster since you save time on most comparison.

Share this post


Link to post
Share on other sites
Quote:
Original post by Net-Ninja
You get one comparison if min_x > box.max_x, if not and box.min_x > max_x is true you get two comparisons and so on. So you will most likely get very few comparisons. In the cases where they actually collide they will ofcource check all the if statements and will have 6 comparisons. This is why axis aligned bounding boxes are so fast.


Circles are faster than AABBs though. If you have a shape that's reasonably covered by a circle better than by an AABB and all you are doing is checking circles against circles, the narrow phase collision detection should be trivial.

This is probably the best way to handle collision in a shmup (what it sounds like you're making). Concentrate more on your broad phase collision detection, and you will likely see the best returns.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this