优化碰撞检测

Question

我正在寻找有关碰撞检测优化的信息。

有一个物体（圆形）从点a移动到点b。该物体具有半径r，并且场中还有许多障碍物（圆形）。

我有一个算法（函数），用于检查圆形和胶囊体之间的碰撞，我目前为每个障碍物调用此函数：

for-each (o : obstacles)
  if collide(o, Capsule(a,b,r))
    return true;

return false;

许多障碍物与运动物体非常遥远，可以忽略使用碰撞检测功能进行检查。

我的问题是：

是否有一种解决方案可以忽略使用碰撞检测功能检查所有障碍物？例如最近邻搜索或KD树？

编辑：所有障碍物半径相同。

- masoud

---

你遇到了多少障碍？它们有多密集？碰撞经常发生还是很少发生？ - Björn Pollex

想象一下有100个障碍物，它们分布得很稀疏。算法每10毫秒调用一次。 - masoud

你应该尝试对程序进行分析以确保找到了瓶颈。此外，kd树似乎适合你的问题，你是否尝试过它是否有帮助？ - Björn Pollex

我以前用kd-tree来寻找给定点的最近点。但在这种情况下，我不知道如何使用kd-tree！ - masoud

这有什么不清楚的？碰撞只能发生在最近的障碍物。 - Björn Pollex

Answer 1

作为第一步，您可以忽略所有不在某个框架/盒子中的障碍物。例如，所有y坐标（障碍物形状的y最低点）大于a和b的最大y坐标加上移动对象半径的相同距离的障碍物可以被忽略。类似地，对于下边界和x边界也是如此。您还可以将一个框架进一步分成两个（或更多）框架。例如，将a-b的距离分成两个距离，并对(a，(b-a)/2)，/(b-a)/2，b)的每个进行以上过程。但这完全取决于您能够将这些值与您的碰撞程序进行有效比较的效率。

- Martin

Answer 2

您可以简单地使用一个网格，其中每个单元格都持有与该单元格接触的所有障碍物。现在只需检查您的胶囊球接触的单元格是否发生碰撞。 此外，您还可以使用四叉树，但是从我的经验来看，通常网格就足够了，并且具有易于快速更新障碍物移动的优点。

- stryba

Answer 3

关于马丁的回答的评论:

我创建了一个类似于Box(a.x-R, a.y-R, b.x+R, b.y+R)的框，其中R是ObjectRadius + ObstacleRadius，然后删除不在此框内的每个障碍物。在图中，只有带有黄点的障碍物将被检查：

- masoud

---

这看起来非常不错。不过你可能需要稍微扩大一下方框，以便将所有的粉色路径（+ 安全 R）都包含在内（上面我假设 a 和 b 通过一条线连接）。那些较小的黑线表示什么？ - Martin

这是没有R保护的盒子。它运行良好，但我不得不在几个地方编辑我的代码。 - masoud

Answer 4

我可以推荐一个怪兽曲线，例如希尔伯特曲线。它是一种四叉树或kd树类似的数据结构，它将2D复杂性降低为1D问题。在每个帧中，您只需从开始构建怪物曲线，这样就可以节省在四叉树或kd树中删除或插入的操作。它还具有一些更好的2D平铺属性，但这可能在您的情况下不需要。

- Micromega

Answer 5

你可以尝试在你的代码中实现空间划分。通过将每个物体/障碍物划分到覆盖整个空间或地图的方格中。这样做可以将障碍物分组到各个部分中。因此，您可以通过仅在一个小区域内检查碰撞来大大减少碰撞检查的数量。如果您的障碍物不移动，则每个障碍物只需要进行一次分区即可。如果它们在移动，则必须每次更新每个障碍物的分区[重新分组]。

空间划分技术已经存在相当长的时间了，这里是一个链接帮助你进行实现。

http://gameprogrammingpatterns.com/spatial-partition.html

- NiTuRen

Answer 6

1. 将障碍物的中心放入KD树中。
2. 找到最近的中心。
3. 检查它是否比ObstacleRadius更接近。

- maxim1000