Jump to content
  • Advertisement
Sign in to follow this  

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

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

If you intended to correct an error in the post then please contact us.

Recommended Posts


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

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

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
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
Yep that's true especially for fast moving objects.

And presumably you're using a bounding radius or box to determine which nodes the player resides in right?

Share this post

Link to post
Share on other sites
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
Sign in to follow this  

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!