0
\$\begingroup\$

A lot of games store object positions as floats and have a closed ball for the game area (eg. a rectangle and objects are allowed to have position coordinates on all 4 edges).

However, this becomes problematic when partitioning the game area (eg. gridding/quadtrees). The edge cases would have to be added in so that 2 edges of the game area are included in rectangles that touch them or objects on 2 edges would have to be missed out in the partition.


Is there another solution to this or do games (and other programs this applies to) usually go with one of the above 2?

(One solution is to use integer coordinates, but what if using floats is unavoidable?)

\$\endgroup\$
  • \$\begingroup\$ Seeing this is not getting any attention, is there a better stack website I can ask on? \$\endgroup\$ – Shuri2060 Sep 8 at 9:43
  • 1
    \$\begingroup\$ I don't think so. Give it some time. It's been 2 hours. Most people don't have time to continuously check the board, and it's not the most trivial question around. \$\endgroup\$ – Peethor Sep 8 at 12:30
  • \$\begingroup\$ The way I have dealt with the edge scenario is when traversing the quad tree and bounding box test (to test the position is within the node), I pass the radius through of the object I'm testing with and expand each bounding box by that radius, ensuring that the position of object is in the potential set for more detailed tests within that bounded area. This covers the edge case (pardon the pun) where your object could in theory straddle 8 different nodes. \$\endgroup\$ – ErnieDingo Sep 8 at 22:11
2
\$\begingroup\$

The simple answer would be to add the object's pointer to both cells. As it exists in both cells, to not include it in both cells would be to circumvent the purpose of having the tree to begin with.

The more complicated answer would be to reexamine the purpose for which you're using the spatial partitioning. If this is for graphics and culling, the answer could go both ways. If you don't cull the object, it's not that big of a deal. If this is for broadphase collision detection, obviously not including the object in both cells will almost certainly produce missed collisions.

The best answer would be to use something like a dynamic AABB tree such as an R-tree or R*-tree in which the cells are not limited to simple volume-based binary subdivision.


I run my school's physics club, and I recently spoke with Erin Catto when he came to give his 2019 GDC presentation on dynamic bounding-volume hierarchies to our club. The main takeaway is that the data structure you use and the heuristics employed will be dependent on the scale and purpose of the implementation. I suggest visiting the GDC vault and watching his presentation as he delivers excellent anecdotal information that you may be able to relate to your current problem.

\$\endgroup\$
0
\$\begingroup\$

Another way to slice this is to modify your collision checks so you check each object against everything after it in its own cell and also everything in the cells bellow or to the left but not above. (This pattern ensures that each pair is still checked only once: for the remaining neighbouring cells we didn't check, this current cell will be one of their checked neighbours)

Handling it this way, each object can "belong" to only one cell, even if it touches or straddles the border between two cells. You can make your cells smaller to keep the overall number of pairs checked similar, as long as the largest single object is less than two cells wide (so its center can be just on the edge of one cell, without reaching past its immediate neighbouring cell).

\$\endgroup\$
  • \$\begingroup\$ 'as long as the largest single object is less than two cells wide' --- not something I can guarantee, I'm afraid \$\endgroup\$ – Shuri2060 Sep 10 at 13:26
  • \$\begingroup\$ If you need a very wide range of object sizes, you can handle this by breaking the object colliders into smaller primitives that fit in your cells. (This can be beneficial for efficiency, since each piece can limit its collision checks to a smaller region, excluding more potential collision pairs. If we have to consider a giant object all as one, then the region it could potentially collide with can be huge — even if most of the objects in that volume have no chance of actually touching its surface) \$\endgroup\$ – DMGregory Sep 10 at 13:31

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.