1
\$\begingroup\$

I am not sure how to handle situation when out objects (player) is in center (0,0) point of game which is crossing of four quads. How to handle that case? This image shows problem: quadtree

Red rectangle is player BoundingBox, he is at center, he not fully contain in any quad but he partially belongs to four quads, so we should get content of those 4 green quads or whole pranet quad?

\$\endgroup\$
2
\$\begingroup\$

In this case you have to decide what to do. In most cases, this is done automatically for you because your sorting is based upon <=, >=, < or > where you definitely get an answer, either true or false, so it really depends which type of comparison you use.

For example

if(x < middle_of_this_quad)
    add_to_left_subtree
else
    add_to_right_subtree

This comparison already decided that everything smaller than middle_of_this_quad, 0 in this case, will go left and everything else, including 0 will go right.


Apart from that, it is highly unlikely that you'll ever hit exactly 0.0 with floating-point arithmetic, unless you set it yourself, of course.

\$\endgroup\$
  • \$\begingroup\$ Yes but it is based on BoundingBox which represents region not only Points . So conclusion is BoudingBox can belong partialy to two quads, ofcourse 80% of that box can be in one quad and 20% in another but it is still splited between two. And I am talking about retriving items not inserting. In my implementation if object can't fit in to sub node because he belongs to more than one subnode he is added to parent node where he fully belongs. \$\endgroup\$ – Kacper Kleczewski Jul 27 '15 at 13:40
0
\$\begingroup\$

Not sure if this will help (I'm a very old hand at coding, but brand new at helping others with it <.<) but here goes.

I had a similar issue with inserting/retrieving 'uniquified' (?) mesh vertices in my engine, where the vertices must be capable of deforming slightly from their 'origin' yet still be considered to be 'owned' by a particular bounding box even if it deforms outside of it. In the simplest terms, I solved it by tracking the position in a multi-level cache; in your case, that may be as simple as flagging the entity as being in all boxes that bound it (the base children only, and/or all touching parent nodes), then flagging it again (or unflagging it as the case may be) when it has been retrieved from any of those boxes.

I'm happy to provide the (abridged) code from my engine showing how I did it if you need a more concrete example.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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