我想知道处理大量移动对象（球体、三角形、盒子、点等）的最佳数据结构是什么？我试图回答两个问题，最近邻和碰撞检测。
我知道传统上，类似R树的数据结构用于最近邻查询，Oct/Kd/BSP用于处理静态对象或极少数移动对象的碰撞检测问题。
我希望能找到更好的解决方案。
非常感谢您的帮助。
5个回答
7
您可以将场景分割成八叉树并利用场景的一致性。您正在测试的移动对象将在树的特定节点中停留一段时间，具体取决于其速度。这意味着您可以假定它会在该节点中，因此可以快速剔除不在该节点中的许多对象。当然，棘手的问题是当您的对象靠近分区边缘时，您需要确保更新对象所在的节点。
移动对象有方向和速度。您可以通过使用垂直于对象运动方向的垂直划分将场景轻松分为两个部分。错误面的任何对象都不需要检查。当然要考虑其他对象的速度，如果其他对象移动得很慢，可以轻松将其从进一步检查中剔除。
始终使用诸如轴对齐边界框之类的东西简化测试的形状。首次碰撞测试
您可以计算您的对象与另一个移动对象之间的距离加上速度。如果其他移动对象以更快的速度朝着相同的一般方向移动，则可以从检查中排除它。
根据对象的形状，还有许多其他优化方法。圆形或正方形或更复杂的形状都可以进行特定的优化。
假设某些对象会停止移动，您可以跟踪停止的对象。这些对象可以像静态对象一样处理，因此检查速度更快，而且您可以将所有静态优化技术应用于它们。
我还知道其他的方法，但目前无法想出来。一段时间没做了。
当然，这取决于您如何执行碰撞检测。您是否根据速度逐步更新对象的位置并按照静态方式检查。还是通过外推形状并计算初始碰撞点来补偿速度。前者需要小步骤处理快速移动的对象。后者更加复杂和昂贵，但效果更好。另外，如果您要有旋转的对象，那么事情就会变得有点棘手。
移动对象有方向和速度。您可以通过使用垂直于对象运动方向的垂直划分将场景轻松分为两个部分。错误面的任何对象都不需要检查。当然要考虑其他对象的速度，如果其他对象移动得很慢，可以轻松将其从进一步检查中剔除。
始终使用诸如轴对齐边界框之类的东西简化测试的形状。首次碰撞测试
您可以计算您的对象与另一个移动对象之间的距离加上速度。如果其他移动对象以更快的速度朝着相同的一般方向移动，则可以从检查中排除它。
根据对象的形状，还有许多其他优化方法。圆形或正方形或更复杂的形状都可以进行特定的优化。
假设某些对象会停止移动，您可以跟踪停止的对象。这些对象可以像静态对象一样处理，因此检查速度更快，而且您可以将所有静态优化技术应用于它们。
我还知道其他的方法，但目前无法想出来。一段时间没做了。
当然，这取决于您如何执行碰撞检测。您是否根据速度逐步更新对象的位置并按照静态方式检查。还是通过外推形状并计算初始碰撞点来补偿速度。前者需要小步骤处理快速移动的对象。后者更加复杂和昂贵，但效果更好。另外，如果您要有旋转的对象，那么事情就会变得有点棘手。
- mempko
3
边界球可能会帮助你处理许多移动物体；你需要计算对象的半径平方，并从其中心跟踪它。如果两个对象中心之间的平方距离小于两个对象半径平方之和，则可能发生碰撞。所有操作都是基于平方距离，没有平方根。
你可以通过对象之间最小平方距离来排序最近的邻居。当然，碰撞检测可能变得复杂，并且对于非球形物体，边界球不一定能为您提供碰撞信息，但它可以很好地修剪需要比较碰撞的物体树。
当然，您需要跟踪对象的中心；理想情况下，每个对象都应该是刚性的，以避免重新计算边界球大小（虽然重新计算并不特别困难，特别是如果您使用具有自己边界球的刚性对象树来表示非刚性对象，但这会变得复杂）。
基本上，要回答关于数据结构的问题，您可以将所有对象保存在主数组中；我会有一组“区域”数组，其中包含对主数组中的对象的引用，您可以根据它们的笛卡尔坐标快速将对象分类；“区域”数组的重叠定义应该至少是主对象数组中最大物体半径的2倍（如果可行；显然，对象边界球缩放与对象数量之间的问题会出现）。
一旦您做到了这一点，您就可以通过比较区域内所有对象之间的距离来进行快速碰撞测试；同样，这就是区域定义变得重要的地方，因为您正在权衡区域数量和比较数量。但是，这有点简单，因为您的距离比较归结为简单的减法（当然还有abs()操作）。
当然，然后你必须在非球形对象之间进行实际的碰撞检测，这可能并不容易，但此时你已经大大减少了潜在的比较数量。
基本上，这是一个两层系统；第一层是区域数组，通过对场景进行粗略排序。其次，您有您的区域内距离比较；其中，您将在已发生碰撞的对象上执行基本的碰撞检测和碰撞标记。
在这种算法中，可能存在使用动态区域确定的树以平衡区域大小，以确保您的区域大小不会随着“拥挤”区域的增长而快速增长的空间；然而，这种事情并不容易，因为对于不同大小的物体，您在密度上的排序变得非常复杂。
你可以通过对象之间最小平方距离来排序最近的邻居。当然，碰撞检测可能变得复杂，并且对于非球形物体，边界球不一定能为您提供碰撞信息，但它可以很好地修剪需要比较碰撞的物体树。
当然，您需要跟踪对象的中心；理想情况下，每个对象都应该是刚性的，以避免重新计算边界球大小（虽然重新计算并不特别困难，特别是如果您使用具有自己边界球的刚性对象树来表示非刚性对象，但这会变得复杂）。
基本上，要回答关于数据结构的问题，您可以将所有对象保存在主数组中；我会有一组“区域”数组，其中包含对主数组中的对象的引用，您可以根据它们的笛卡尔坐标快速将对象分类；“区域”数组的重叠定义应该至少是主对象数组中最大物体半径的2倍（如果可行；显然，对象边界球缩放与对象数量之间的问题会出现）。
一旦您做到了这一点，您就可以通过比较区域内所有对象之间的距离来进行快速碰撞测试；同样，这就是区域定义变得重要的地方，因为您正在权衡区域数量和比较数量。但是，这有点简单，因为您的距离比较归结为简单的减法（当然还有abs()操作）。
当然，然后你必须在非球形对象之间进行实际的碰撞检测，这可能并不容易，但此时你已经大大减少了潜在的比较数量。
基本上，这是一个两层系统；第一层是区域数组，通过对场景进行粗略排序。其次，您有您的区域内距离比较；其中，您将在已发生碰撞的对象上执行基本的碰撞检测和碰撞标记。
在这种算法中，可能存在使用动态区域确定的树以平衡区域大小，以确保您的区域大小不会随着“拥挤”区域的增长而快速增长的空间；然而，这种事情并不容易，因为对于不同大小的物体，您在密度上的排序变得非常复杂。
- McWafflestix
1
我知道使用球体可以使碰撞测试变得更快，而使用区域则可以划分空间并限制比较的数量，但是你必须重新计算这些“区域”，这会很慢？我正在寻找一种数据结构，可以快速更新其“区域”。 - esiegel
3
一种有趣的碰撞检测方法是使用轴对齐边界框（AABB）组织在特殊的八叉树结构中。AABB很有用，因为它们使粗略的碰撞计算非常快速，因为您只需要执行最多6次比较。
以下是一些应该使用的八叉树结构技巧：
1）节点占据的边界区域应该是普通八叉树的两倍大（其中八叉树将空间分割而不重叠）。由于每个节点应该重叠其相邻节点的一半区域。由于AABB只能属于一个节点，因此这种额外的大小和重叠允许它在一个节点中保持更长时间。
2）在每个节点中 - 可能在层次结构的每个级别中 - 您还应该保留与节点相邻的链接。这将涉及大量额外的代码，但它将允许您在接近O（1）时间而不是O（2logn）时间内在节点之间移动元素。
如果八叉树占用太多内存，您可以将其更改为使用稀疏八叉树结构，仅保留实际包含实体的游戏世界部分的树。但是，这意味着当实体穿过世界时，您将不得不执行更多的每帧计算。
您可能想尝试的其他想法是使用kd树（我相信这是正确的名称），或者使用AABB从下往上构建结构。
KD树（从记忆中）使用轴对齐平面分割空间，因此它们非常适合与AABB一起使用。
另一个想法是，而不是从顶部强制进行八叉树生成（从包围整个世界的框开始），您可以从基础实体构建它，并构建越来越大的AABB，直到最大的AABB包含整个世界。虽然我不确定它在许多快速移动的实体方面如何运作。
（我已经有一段时间没有做这种空间游戏开发编码了。）
以下是一些应该使用的八叉树结构技巧：
1）节点占据的边界区域应该是普通八叉树的两倍大（其中八叉树将空间分割而不重叠）。由于每个节点应该重叠其相邻节点的一半区域。由于AABB只能属于一个节点，因此这种额外的大小和重叠允许它在一个节点中保持更长时间。
2）在每个节点中 - 可能在层次结构的每个级别中 - 您还应该保留与节点相邻的链接。这将涉及大量额外的代码，但它将允许您在接近O（1）时间而不是O（2logn）时间内在节点之间移动元素。
如果八叉树占用太多内存，您可以将其更改为使用稀疏八叉树结构，仅保留实际包含实体的游戏世界部分的树。但是，这意味着当实体穿过世界时，您将不得不执行更多的每帧计算。
您可能想尝试的其他想法是使用kd树（我相信这是正确的名称），或者使用AABB从下往上构建结构。
KD树（从记忆中）使用轴对齐平面分割空间，因此它们非常适合与AABB一起使用。
另一个想法是，而不是从顶部强制进行八叉树生成（从包围整个世界的框开始），您可以从基础实体构建它，并构建越来越大的AABB，直到最大的AABB包含整个世界。虽然我不确定它在许多快速移动的实体方面如何运作。
（我已经有一段时间没有做这种空间游戏开发编码了。）
- Daemin
2
我非常喜欢保留所有相邻节点列表的想法，但这是否假定所有节点大小相等？使用稀疏八叉树，我认为会有问题，特别是如果我没有重新计算节点的分割。 - esiegel
其实有两种方法可供选择，一种是计算一个稀疏树并在执行期间保持更新，另一种是生成一个完整的八叉树并将对象移动到它周围。你只需要考虑你想要承担哪种代价。 - Dominik Grabiec
-1
扫描和修剪广域 + GJK 狭域
- Jeff
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接