相关疑难解决方法(0)

我正在尝试使用四叉树进行二维碰撞检测,但我对如何实现它感到有点困惑.首先,我有一个四叉树,其中包含四个子树(一个代表每个象限),以及一个不适合单个子树的对象集合.

当检查对象在树中的碰撞时,我会做这样的事情(感谢QuadTree用于2D碰撞检测):

1. 检查对象是否与当前节点中的任何对象发生冲突.
2. 对于其空间与对象重叠的任何子树,递归.

要查找四叉树中的所有碰撞:

1. 检查当前节点中的每个对象与当前节点中的每个其他对象.
2. 根据每个子树检查当前节点中的每个对象.

要插入四叉树:

1. 如果对象适合多个子树,则将其添加到当前节点,然后返回.
2. 否则,递归到包含它的子树.

要更新四叉树:

1. 递归到每个子树.
2. 如果当前节点中的任何元素不再完全适合当前树,请将其移动到父节点.
3. 如果当前节点中的任何元素适合子树,请将其插入子树中.

这好吗？可以改进吗？

我正在阅读这个答案

用于 2D 碰撞检测的四叉树的高效（并得到很好的解释）实现

并遇到这一段

好吧，实际上四叉树并不是我最喜欢的用于此目的的数据结构。我倾向于更喜欢网格层次结构，例如世界的粗网格，区域的更细的网格，以及子区域的更细的网格（3 个固定级别的密集网格，不涉及树），具有行-基于优化，因此其中没有实体的行将被释放并变成空指针，同样完全空的区域或子区域变成空值。虽然这个在一个线程中运行的四叉树的简单实现可以在我的 i7 上以 60+ FPS 处理 100k 代理，但我已经实现了可以处理几百万个代理在旧硬件（i3）上每帧相互反弹的网格。此外，我一直很喜欢网格如何使预测它们需要多少内存变得非常容易，因为它们不细分单元格。

这种类型的网格看起来很直观，听起来有点像“N 阶”网格，其中每个父节点有 N 个子节点，而不是 4 个子节点。N^3 可以比 4^3 走得更远，这允许更好的精度和潜在的（我猜）更少的分支（因为要分支的节点少得多）。

我有点困惑，因为我会直觉地使用一个或可能是 3 个 std::map< operator()来减少它的内存占用，但我不确定它会这么快，因为查询 AABB 意味着堆叠几次访问都是 O(log n)。

他所说的那些基于行的优化到底是什么？这种类型的网格搜索常见吗？

我对 az 阶曲线有一些了解，而且我对四叉树并不完全满意。

在游戏中使用八叉树进行碰撞检测时,是应该每帧重建一次树还是假设有一半的物体在一帧中移动？