Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

In my game I have a tree of objects in 3D space, to which new objects are frequently added.

Over time, the binary tree becomes unbalanced which is a big problem for efficiency as the tree can become quite large. It might even be at risk of stack overflows from deep recursion.

At the same time, it is important to keep branches of the tree close together in 3D space. So I can't arbitrarily swap tree nodes around to balance the tree.

Is there an efficient algorithm that will do the following:

  • Allow efficient additions to the tree (O(log n) max)
  • Keep the tree approximately balanced as additions are made
  • Ensure that branches of the tree contain objects that are close to each other in 3D space (i.e. it works at least approximately as a spatial subdivision tree)
share|improve this question
add comment

2 Answers

It sounds like you need an octree, binary trees really only work for sorting stuff in one dimension. Note that you still will have to travel down multiple branches to find all objects within an arbitrary zone, no data structure can prevent that.

Of course, it would be possible to store items in a standard search tree according to their position on a 3D Hilbert curve, that would be kinda the same thing as an octree, just more convoluted to implement.

share|improve this answer
add comment

The need for nodes to be close to each other just rules out any efficient remodelling of your tree structure (otherwise you could use a Red Black Tree which is 'self balancing for example).

If you want a binary tree structure you can use a BSP structure or a KD-Tree.

Otherwise check out the Octree, the Loose Octree or why not the R-Tree

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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