Dynamic quadrees
- by paul424
recently I come out writing Quadtree for creatures culling in Opendungeons game.
Thing is those are moving points and bounding hierarchy will quickly get lost if the quadtree is not rebuild very often.
I have several variants, first is to upgrade the leaf position , every time creature move is requested. ( note if I would need collision detection anyway, so this might be necessery anyway).
Second would be making leafs enough large , that the creature would sure stay inside it's bounding box ( due to its speed limit). The partition of a plane in quadtree is always fixed ( modulo the hierarchical unions of some parts) . For creatures close to the center of the plane , there would be no way of keeping it but inside one big leaf, besides this brokes the invariant that each point can be put into any small area as desired. So on the second thought could I use several quadrees ? Each would have its "coordinate axis XY" somwhere shifted ?
Before I start playing with this maybe some other space diving structure would suit me better, unfortunetly wiki does not compare it's execution time :
http://en.wikipedia.org/wiki/Grid_%28spatial_index%29#See_also
