QuadTrees - how to update when internal items are moving

Posted by egarcia on Stack Overflow See other posts from Stack Overflow or by egarcia
Published on 2010-05-23T00:52:04Z Indexed on 2010/05/23 10:40 UTC
Read the original article Hit count: 277

Filed under:
|
|
|

I've implemented a working QuadTree. It subdivides 2-d space in order to accomodate items, identified by their bounding box (x,y,width,height) on the smallest possible quad (up to a minimum area).

My code is based on this implementation (mine is in Lua instead of C#) : http://www.codeproject.com/KB/recipes/QuadTree.aspx

I've been able to successfully implement insertions and deletions successfully. I've turn now my attention to the update() function, since my items' position and dimensions change over time.

My first implementation works, but it is quite naïve:

function QuadTree:update(item)
  self:remove(item)
  return self.root:insert(item)
end

Yup, I basically remove and reinsert every item every time they move.

This works, but I'd like to optimize it a bit more; after all, most of the time, moving items still remain on the same quadTree node most of the iterations.

Is there any standard way to deal with this kind of update?

In case it helps, my code is here: http://github.com/kikito/passion/blob/master/ai/QuadTree.lua

I'm not looking for someone to implement it for me; pointers to an existing working implementation (even in other languages) would suffice.

© Stack Overflow or respective owner

Related posts about game-development

Related posts about update