Jump to content
  • Advertisement
Sign in to follow this  

Unity How to best organise a world of moving objects.

This topic is 2812 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

I have a 3D scene with a lot of Mobiles (basically world objects that move all the time) and I'm trying to figure out the best way to organise them so as to speed up collision detection.

I'm leaning towards using a kd tree to divide my game world up into a binary tree of nodes, and then adding each mobile to a node.
- If there is an overlap between the mobile's bounding sphere and multiple nodes, then they go in a parent node.
- Every time a mobile moves, a check is required to see if it is still in its current node, and moved to a new node if required.
- A collision detection test with a mobile (mobA), would require a check between mobA and all the mobiles that are in the same node as mobA and all the mobiles that are in parent nodes.

This is as about as good as I can think of, but am really keen to get some advice before I pour some hours into this.

Alternatively I was thinking about using
- Quad trees
- Perhaps not using the kd-tree nodes as 'buckets' of mobiles but instead making each mobile a kd-tree node, so that mobiles have child mobiles. I figured this would get crazy complex when mobiles moved and the kd-tree would have to get entire branches re-added to the tree.

I see there are lots of good articles on collisions between two objects, but I can't find much in the way of better organising a world of moving objects.
I did find:

Cheers for any tips.

Share this post

Link to post
Share on other sites
I'd recommend a Spatial Hash.

It's efficient enough for dynamic and deformable bodies, thus it works well with normal rigid bodies as well.

For mobile objects, you'd have to first clear the spatial hash. Then update each objects bounding volume (like an AABB). Then rehash each object into the Spatial Hash. That may sound kind of bad but it handles the problem of updating the structure positions for fast moving objects and has an algorithm cost of O(N), which is doable. Once everything is in place, asking the game engine "What is by this point," "What is in this volume of space," or "What other objects may collide with this game object?" becomes an easy and efficient thing to answer.

I did an implementation for convex shapes with AABB for bounding volumes and it's been working well for my broad phase collision detection.

Read the paper and if you're interested in discussing implementation details, let me know.

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.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!