Jump to content
  • Advertisement
Sign in to follow this  
wegrata

Spatial Structure for moving objects

This topic is 3791 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 wanted to find out what spatial structure is best suited for moving objects. I currently have an octree implemented for static objects, but it seems that the tree will degrade too much with constantly moving objects around. Would it be better to go with a kd tree or is there some other type of structure better suited for this. Additional info on the project. A FPS being coded in C# using XNA.

Share this post


Link to post
Share on other sites
Advertisement
You didn't say the size of the maps so a uniform grid is a good solution for smaller maps. Moving objects and bullets like in an FPS can use grid transversal for ray casting or moving lines. (look into 3DDDA). Also insertion and removal is usually very quick for tons of moving objects. Also it can hold static objects so you only need one system.

(if size is an issue and you are good with theory, a nested grid unlike an octree will allow for easy grid transversal, but it's harder to code)

Share this post


Link to post
Share on other sites
Try any of the following:

- Loose Octrees
- Uniform grids (if you do it smartly you can have O(1) lookup for broad phase collision detection), look at the book Real-Time collision detection
- Fixed size quadtrees
- Sphere trees
- Plain old manual section partition (Divide your level on sections manually placed, and traverse the sections one by one at runtime)

Adaptive methods are not a good choice for dynamic object space partitioning, kd-trees are probably not a good bet either, they are really not better than fixed size octrees for this type of problem, they would be good for static geometry though

Share this post


Link to post
Share on other sites
I'd suggest looking at a proximity map (hierarchial grid that is offset at each level to prevent the "plane of death" scenario where an object bubbles to the root of the structure when it crossed a plane common to multiple levels). I think it was presented at GDC 2005 by one of the guys at Ready at Dawn (ex Blizzard I believe). It is exremely fast for both query and updating.

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!