假设我有一个四叉树。 假设我里面有一个移动的物体。
我知道当您添加和删除节点时，四叉树会自动排序，但是当一个节点(假设在他的更新函数中)移动到另一个不相关的节点的左侧时会发生什么？ 或者基本上是这个节点传送？
四叉树会发生什么？ 我需要重建它吗？
我只是无法理解当您只更新节点数据时四叉树是否会自动自我排序，或者我是否需要在更新节点时重建整个树。
我见过人们通过多种方式为移动每一帧的对象实现四叉树，包括为此目的使用松散的四叉树，其中节点甚至允许具有重叠的 AABB，这些 AABB 随着存储在叶子中的对象四处移动而扩展和收缩。
也就是说，我发现它很简单，可以相当便宜地更新非松散版本(但是，不像空间哈希或网格那么便宜，但足够便宜，可以保持稳定的帧速率，因为大量实体通过碰撞检测四处移动)。
简单的方法是在移动元素之前将其从树中删除，移动它，然后将其重新插入树中。删除元素时，请检查它所属的节点。如果它们变为空(未存储任何元素，没有子元素)，则从父项中删除它们。如果父节点变为空(该节点中不存储任何子节点，如果将元素存储在分支中，则该节点中没有元素)，则从祖父节点中删除父节点，然后重复此操作。
加快速度的诀窍是避免过多的内存分配。如果您为节点使用空闲列表，它会有所帮助，例如，另一种可能加快速度的方法是检测对象何时不会从一个节点移动到另一个节点。
例如，您可以将实体的边界框或球体展开时间步长乘以其速度，并测试扩展的边界框/球体是否与新节点重叠。如果没有，则无需从树中删除元素、移动元素并重新插入。您可以继续简单地移动它。或者你可以存储它之前的位置，移动它，然后看看它是否属于不同的节点。如果是这样，请删除该元素，就好像它具有先前的位置一样，然后使用新位置重新插入。我并没有真正发现这是必要的，尽管我可以通过索引操作和没有堆分配/释放来完成大部分工作。