FIFE forums

Please login or register.

Login with username, password and session length
Advanced search  


FIFE 0.4.0 has been released on 15th of January, 2017!

Author Topic: Quadtree points of interest  (Read 2496 times)


  • Developer
  • Newbie
  • *
  • Posts: 46
    • View Profile
Quadtree points of interest
« on: January 22, 2008, 03:17:58 am »

#1 I'm not sure what all we use it for, but in core/model/structures/instancetree.cpp, we have the following line, which is used when looking for an instance which has been clicked on.

Code: [Select]
m_tree.find_container(point.x, point.y, w, h);
I think maybe find_container is not appropriate for this use, as it will actually create new (empty) subnodes, bypassing those with data, or may stop early if it decides it prefers to be higher up.  The correct approach is probably to use a visitor, as illustrated in the 3 examples visitors on

#2 The current quadtree seems a bit quirky.  It's logic for deciding when to use a subtree seems based on the location of the single element being placed, rather than a desired node density.  In particular, the logic seems to be tied to whether the object fits into its current cell without touching either the right or bottom borders.

Phoku, could you please comment on the above?  I am told you were the implementer of the quadtree, and your thoughts would be appreciated before we go off and do something silly :-).

Note:  The odd behavior shown in this pic: is a combination of the above two effects.  Clicking on a cell with x=15 when the width is set to 1 by instancetree.cpp will decide that it belongs at 32x32 width, since that is the only way it can avoid touching the border of its bounding box on the right.


  • Developer
  • Full Member
  • *
  • Posts: 102
    • View Profile
    • IZ dev blog
Re: Quadtree points of interest
« Reply #1 on: January 22, 2008, 05:15:24 am »

Nice, I just checked the IRC logs but didn't want to log on IRC from the university =)

The Node density is defined by the MinimumSize, defining how far 'down' the quadtree
shall splice. Splicing also happens if you don't intend to insert content to a node,
though it isn't really and issue. (Or hasn't been, you might consider adding a dontSplice argument to the find_container stuff - but I wouldn't bother!)

Another note - the QuadTree::find_container really does guarantee to find a suitable
node, it does never stop early.

There might be an off by one bug considering insertion - though it shouldn't actually show up,
if used correctly.

And here comes the real problem with the current implementation of getInstanceList:

How to really use it:
#1 Fetch best container node via find_container
#2 Apply a visitor to collect matches down from this node.
#3 Walk upwards via while(node= node->parent()) and collect larger instances too.

The actuall example that really used this is in the visualtree.cpp (rev1000) or from the demo
code from my page.

Another problem is of course, that moving instances should trigger a reinsertion, to keep the
tree up to date.

I hope this clarifies the issues. So far the underlying quadtree.h has proven to be bug free and rather robust. The usage isn't really simple though.

I am unsure about the way it is supposed to be used in current trunk, but if it is for picking instances from the cell grid coordinates it it might be better to just use a matrix of lists considering that instances do not cover more than one cell atm ...

The tree was designed for speeding up rendering & picking based on screen coordinates, and it worked fine for that - sorry my documentation was less than usefull again :-(

I'll document it this evening.
« Last Edit: January 22, 2008, 05:56:24 am by phoku »