# Quad Tree with a lot of Moving Objects

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?

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
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.

• Wow, this is so weird. I stumbled upon this implementation just moments before you posted this. I just started implementing this version to see if it would speed things up for me, and it does. This is amazing work. Dec 5 '11 at 20:26
• @Jon, Yay, I'm glad I could help. BTW, There was a small bug to do with moving in the DLL up there (r20), I'd download the source (r22). Dec 5 '11 at 20:32
• Oh I downloaded rev22 of the source. I didn't even bother with the DLL. But thanks for pointing that out. Dec 5 '11 at 20:32
• Damn, I'm updating an enormous amount of data on every Update() call, and it is not bogging down at all. You are the man. Dec 5 '11 at 20:40
• Awesome, let me know if you experience any problems with it. Dec 5 '11 at 20:42

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.