Hi,


I'm trying to find the best spatial data structure for storing objects in a very large dynamic world. Dynamic in the sense of objects can move into.

I read some stuff, there are many manners to do that, mostly tree like structures and spatial hashing.
There are many trees designed for static world, some others for dynamic world, and even initially for static worlds with a support for dynamic...

Generally, when a tree is "dynamic", world queries are interpreted in the time (with objects position extrapolated), i don't need this level of accuracy. I just need a structure to update objects and query for NN as fast as possible.

This structure is maintained server side and the number of objects and accesses may be very big. I don't want my threads blocked on a locked node for long time (time to remove/add in my current rtree...).

After read documents, i think the spatial hash is good. Am i wrong?

Can anyone put me on the right way?

Thanks,

Sorry, but I'm having a hard time understanding what you're saying. What exactly do you mean by "Dynamic in the sense of objects can move into?"

_________________
Worlds at War (Current Project) - http://www.awkward-games.com
Ganadu'r, The Eternal Sage (Other Current Project) - http://rpg.naget.com
Programming tutorials and web-design services: http://www.wyrmmage.com

Sorry, my english is so bad ...



It is because "dynamic" may be interpreted for lot of thing in a data structure..
Here i just want a structure with moving objects (AABB), without having to rebuild a big part of the structure for each object i want to move (like for a typical static tree).

Globally, for updating an object:
- in a spatial hash, i have to rehash the new AABB and update my indexes.
- in a quad tree, i have to remove the object, and reinsert it from the root node.

But some trees are supporting an improved "update" system.

So, i'm asking which way i should investigate, tree, spatial hash or may be another.
There is a lot of theory for this kind of problem and i just want to start on the right way).


I hope this is a better explanation ...

Thank you.

A quad tree or an oct tree is a nice simple start. If you want to get fancier, you can look into R trees (or R-trees, or R+trees, or R*trees, which I think are all slightly different ).

However, quad/oct-trees are probably good just because they are simple.

_________________
Trying is the first step towards failure
b