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.


1 Answer 1


Without knowing the details of your game, I'd say: Keep It Simple. Updating the quadtree whenever something moves is a perfectly acceptable solution. I mention in my answer to a similar question that the simplest way to update the quadtree is to remove the item, then re-add it, but this can cause unnecessary overhead. The way I've done it in the past is like this:

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

It also sounds like you're using points to represent your creatures. If your creatures actually take up space (WxH > 1x1), I would recommend using the creature's bounding rectangle in the quadtree. This will allow you to do more meaningful lookups like collision detection and view culling.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .