Sign in to follow this  

Spatial Structure for moving objects

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

This topic is 3579 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.

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