Quad Tree with a lot of Moving Objects

Question

I have a Quad Tree implementation that is very useful for what I am trying to do. My problem is that when my viewport has a lot of objects, the Update for the Quad Tree takes a very long time.

It is a known fact that Quad Trees are slow for non-static objects. I tried a few methods to try to speed things up, but the fact is, I need to update a large number of objects very often.

Is there a better algorithm I should be looking at instead? Are there some derived Quad Tree implementations you know about that might be useful to me?

Answer 1

How are you moving Quad Tree objects? The simplest (and slowest) method is to remove the object and re-insert it. The open-source XNA Quad Tree me and a friend made does a little bit of logic when an object moves:

If the object is still inside the same quad
    if the object fits into a child quad
        Add to child
Else
    move the object to the parent(s) until it fits, and optionally going back down into children

If you're already doing something like that, it could be worth looking into other spatial index methods like Spatial Hashing.

Answer 2

I use bounds for objects, and insert them in the deepest quad that contains them. (I've never been comfortable with treating things as points)

For fast-moving objects, which are also typically small e.g. bullets, I compute the bounds of their path for some number of timesteps or maximum size, so I'd bound a bullet by a larger rectangle rather than a smaller square and not need to move them nearly as often.

Also, you can optimise the moving code itself to move the object intelligently rather than removing it and reinserting it.