移动物体的空间数据结构？

Question

我想知道什么是处理大量移动物体（球体，三角形，盒子，点等）的最佳数据结构？我试图回答两个问题，最近邻居和Collsion检测。

我也知道传统上，用于近邻查询和Oct/KD/BSP如R树数据结构用于处理静态的物体，或者几乎没有任何移动的物体碰撞检测的问题。

我只希望有别的东西在那里，是更好的。

我很感谢所有的帮助。

Answer 1

Bounding Spheres可能会帮助你处理许多运动物体;你计算物体的半径平方，并从它的中心跟踪它。如果两个物体的中心之间的平方距离小于两个物体的平方半径的总和，那么你就有可能发生碰撞。一切都以平方距离完成。没有平方根。

你可以通过你的对象之间的最小平方距离最近的邻居进行排序。当然，碰撞检测可能会变得很复杂，并且对于非球形物体，Bounding Spheres不一定会获得碰撞信息，但它可以很好地修剪需要比较的物体树。

你需要，当然要跟踪对象的中心;理想情况下，您希望每个对象都是刚性的，以避免重新计算边界球尺寸（尽管重新计算并不特别困难，特别是如果您使用一个刚性对象树，每个对象都有自己的边界球）是非刚性的;但它变得复杂）。

基本上，回答你关于数据结构的问题，你可以将所有的主数组中的对象;我有一组“区域”数组，它们是对主数组中的对象的引用，您可以根据对象的笛卡尔坐标快速地对对象进行分类; “区域”阵列应该有一个重叠定义，至少是主对象数组中的最大对象半径的2倍（如果这是可行的话;对象边界球体缩放问题与对象数显然会出现）

一次通过比较一个区域内所有对象之间的距离，可以做一个快速的碰撞测试;再次，这是区域定义变得重要的地方，因为您正在进行区域数量与数量的显着折衷但是，它有点简单，只是因为你的距离比较归结为简单的减法运算（当然也包括abs（）操作）。

当然，那么你必须在你的非球面之间做实际的碰撞检测对象，并且可以不是t rivial，但是在这一点上你已经大大减少了潜在比较的数量。

基本上，这是一个双层系统;第一个是区域数组，您可以在场景中粗略地排序。其次，你有你的区域内距离比较;其中您将对碰撞的物体进行基本碰撞检测和碰撞标记。

有可能是房间里这种算法中使用的动态区域确定，甚至出你的区域大小，以确保您的区域大小不会与“拥挤”的区域增长过快的树木;尽管如此，这种事情并不是微不足道的，因为对于不同大小的对象，对密度的排序变得......复杂，至少可以说。

Answer 2

一个有趣的做冲突检测的方法是使用轴向对齐的边界框（AABB's）组织在一个特殊的八叉树结构中。 AABB的帮助，因为他们使得粗略的碰撞计算非常快速，因为您只需要执行多达6次比较。

这里有几个技巧，你应该用八叉树结构用：

1）一个节点占据应该是两倍大，因为这将是一个正常的八叉树（八叉树分区的位置的边界区域空间不重叠）。由于每个节点应与其相邻节点的一半面积重叠。由于AABB只能属于一个节点，因此这种额外的大小和重叠允许它在较长的时间内保持在一个节点中。

2）同样在每个节点中 - 也许在层次结构的每个级别中 - 都会保留到节点邻居的链接。这将涉及大量额外的代码，但它将允许您在接近O（1）时间而不是O（2logn）时间之间在节点之间移动元素。

如果八叉树占用太多内存，则可以将它改为使用稀疏八叉树结构，只保留实际包含实体的游戏世界各部分的树。然而，这意味着当实体在世界中移动时，你必须对每一帧执行更多的计算。

您可能想尝试的其他想法不是八叉树，而是使用kd-tree（我相信这是正确的名称），或者使用AABB从底层构建结构。

KD树（来自内存）使用轴向对齐的平面分隔空间，因此它们非常适合与AABB一起使用。

另一个想法是，而不是从上而下，迫使八叉树代（从一个盒子envoloping整个世界），你从基础的实体建立起来，构建更大的AABB的是增长，直到最大的一个涵盖整个世界。虽然我不确定它如何与许多快速移动的实体一起工作。

（这已经有一段时间，因为我已经做了这种空间的游戏开发编码。）

Answer 3

1. 您可以在八叉树分区现场，并利用现场的一致性。您正在测试的移动对象将根据其速度，位于树的特定节点中以获取特定数量的帧。这意味着您可以假定它将位于节点中，因此可以快速删除很多不在节点中的对象。当然，棘手的一点是当你的物体接近你的分区的边缘时，你必须确保你更新了该物体所处的那个节点。

2. 移动物体有方向和速度。您可以通过使用与对象移动方向垂直的分割，轻松地将场景分为两部分。不需要检查该分部错误的任何物体。当然补偿其他物体的速度。所以如果另一个对象是合理的缓慢的话，你可以很容易地将它从进一步的检查中删除。

3. 总是使用像轴对齐边界框之类的东西来简化您正在测试的任何形状。初始碰撞测试

4. 您可以将物体与另一个移动物体之间的距离加上速度。如果另一个运动物体以更快的速度以相同的总体方向移动，则可以将其从检查中消除。

5. 根据物体的形状还有很多其他的优化。圆形或正方形或更复杂的形状都可以在移动时做特定的优化。

6. 假设某些物体停止或停止移动，您可以跟踪停止的物体。这些对象可以被视为静态对象，因此检查速度更快，您可以将所有静态优化技术应用于它们。

7. 我知道更多，但想不到任何关闭我的头顶。有一段时间没有这样做。

现在当然这取决于你如何在做碰撞检测。您是否逐渐更新基于速度的对象位置并检查它是否是静态的。或者你是通过挤出形状并找出初始碰撞点来补偿速度。前者需要快速移动物体的一小步。后者更复杂，成本更高，但效果更好。另外，如果你要旋转物体，那么事情会变得更棘手。

Answer 4

扫描剪枝宽泛阶段+ GJK窄相

Answer 5

RDC可以使用的，特别是如果你的对象是稀疏的（未许多交叉点）。