Recently I started writing a Quadtree for creature culling in Opendungeons game.

Thing is these are moving points and the 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 that I would need collision detection, so this might be necessary anyway.

Second would be making leafs large enough that the creatures would sure stay inside its 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 to do this except to keep it inside one big leaf. Besides, this brakes 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" shifted?

Before I start playing with this maybe some other space diving structure would suit me better. Unfortunately, the wiki does not compare their execution time.

If the object is still inside the same quad