Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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?

share|improve this question
    
You can also look here: gamedev.stackexchange.com/questions/20011/… –  zacharmarz Dec 5 '11 at 20:12
add comment

2 Answers

up vote 11 down vote accepted

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.

share|improve this answer
    
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. –  Jon Dec 5 '11 at 20:26
1  
@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). –  John McDonald 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. –  Jon 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. –  Jon Dec 5 '11 at 20:40
    
Awesome, let me know if you experience any problems with it. –  John McDonald Dec 5 '11 at 20:42
show 2 more comments

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.