• 10
• 12
• 12
• 14
• 18

# Super fast collision detection

This topic is 2689 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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 on other sites
I think you would realize large gains by partitioning your space before collision detection. I suggest a BSP tree.

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

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 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 on other sites
Presumably, it will be under the vsynch limit once AI, rendering, etc. is added.

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