Sign in to follow this  
usbman3

Optimizing collision detection of player and map with some data structures?

Recommended Posts

usbman3    101
Hello!

There is a Z-axis aligned cylinder (the player), and a map, which is made of AABB's.

I have written the collision detection and physics code myself. Currently it just loops through the entire map and tests if the player intersects any AABB.

Here's a screenshot (lighting is messed up):


Google results for "acceleration structure" shows only raytracing articles :(

What's the most efficient and simple data structure to speed up collision detection in this scenario?

Share this post


Link to post
Share on other sites
Liguria    124
Implement some kind of spatial subdivision. An octree would work well for your kind of geometry.

Like that, you'll cut down the amount of geometry to test collision against A LOT (if implemented/configured well, that is)

Just use your internet search-engine of choice to find information about spatial subdivision and octrees in particular. There's a hell of a lot written about it :)

Share this post


Link to post
Share on other sites
rumblesushi    159
Basically you need a broadphase.

That enables you to quickly and efficiently discard large areas of geometry that are completely outside of your vicinity and have no chance of colliding.

Personally I use a uniform grid, as I love the speed, simplicity, and minimal overhead of adding/removing with large amounts of moving objects.

I use the grid for environment collisions too.

Share this post


Link to post
Share on other sites
usbman3    101
I finally got it working.

The algorithm will keep dividing space into smaller and smaller parts until the parts are small enough or they don't contain any objects (=boxes).

But searching the octree sucks too many CPU cycles. Performance is much better with octree disabled.



There are usually 0-17 collision tests done with octree enabled, and without octree its 229 (the number of boxes).

"Dumb" collision testing outperforms octree even when there are 120000+ boxes! (and btw: building octree takes almost 2 minutes with that box count on my cpu)

Pseudocode for my octree search function:
struct Octree
{
int is_leaf;

union {
struct {
float centre[3];
float min[3];
float max[3];
Octree *sub_oc[2][2][2];
} branch;
struct {
int num_boxes;
Box **boxes;
} leaf;
} data;
};

void search_octree_recursive( octree, player_aabb, callback )
{
if octree.is_leaf:
for each box in octree:
if box.has_not_tested:
callback( box )
box.has_not_tested = 0
return

for each subcell:
if player_aabb intersects subcell:
search_octree_recursive( octree, player_aabb, callback )
}

void search_octree( player_aabb, callback )
{
for each box:
box.has_not_tested = 1
search_octree_recursive( octree_root )
}


Testing if player's AABB intersects the subcells of octree is expensive. How can I get rid of those collision tests?


And BTW, the map is 100% static, and the only moving objects are players (and hitscan bullets). I'm not going to need any dynamic data structures.

Share this post


Link to post
Share on other sites
rumblesushi    159
You must be doing something wrong in regards to traversing the octree. There is absolutely no way your brute force method should be outperforming an octree with 120,000 objects.

Incidentally, the main reason I love a broadphase grid compared to an octree is determining position on the grid plus adding/removing items from a grid is incredibly fast, the grid itself basically has no overhead, and with the right size nodes you can cut down the potential collisions almost as low as an octree.

The only problem with a grid is RAM usage, so you have to think about deleting unoccupied nodes etc.

Share this post


Link to post
Share on other sites
usbman3    101
I rewrote the entire octree code. Octree is now faster than brute force. And I also improved rendering performance a bit.

Boxes: 237
Average FPS with octree: 94.979
Average FPS with brute force: 89.521

Boxes: 7009
Average FPS with octree: 21.401
Average FPS with brute force: 20.772

Boxes: 18948
Average FPS with octree: 9.323
Average FPS with brute force: 8.360

EDIT: Octree seems to make some new collisions bugs. Collisions are not tested when they should be, and player can move trough walls in some rare spots.

EDIT:
I made player vs. box collision function 10000x slower with SDL_Delay.

Brute force: 1 frame per 15 seconds
Octree: around 17 FPS


It seems to be that AABB vs AABB test is too fast. Traversing octree needs more time than brute force testing all boxes in the map.


[Edited by - usbman3 on December 6, 2010 7:51:33 AM]

Share this post


Link to post
Share on other sites
Liguria    124
About the collision problems: Make sure you process all nodes that your character intersects between the start position of your move and the requested target position.


About your performance problems I'm not sure. You might want to tweak the minimum size of your octree nodes a bit to get better performance. Making them too small might just choke performance.
Play with your variables a bit (minimum node size vs. max content of node)

Small addition: maybe your collision code wasn't so bad in the first place. Did you run a profiler to see if a lot of time is actually spent in the collision routines?
Also, for better comparison of the numbers you get, try a bigger and more complicated map.

[Edited by - Liguria on December 6, 2010 10:24:43 AM]

Share this post


Link to post
Share on other sites
usbman3    101
Increasing the minimum octree subcell size increased performance too :)

I have made a slightly bigger map, which has 336 boxes.

Today I finally got the collision bug fixed. There was a 'return' instead of a 'continue' in a recursive octree searching loop.

Then I did a quick benchmark in the new map. Seconds spent for collision testing per one game tick:

Brute force: 0.00017
Octree: 0.00004

So octree is about 425% faster than brute-force.

The game spends 0.1% of time for collision testing. The rest is mostly rendering.

Now I'm happy with this. Time to move onto other things.

Thanks for your replies.

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