每一帧检查多个球之间碰撞的快速方法。

Question

假设我有 N 运动球 r 在一个二维空间中。为了简单起见，。N < 30.

我想知道最快的方法来检查这些球是否每一帧都在碰撞。

很明显，我可以做这样的事情。

for(int i = 0; i < N - 1; i++){
    for(int j = i + 1; j < N; j++){
        if (dist(ball[i], ball[j]) <= r) CollisionList.Add(i, j);
    }
}

但由于这是O(N²)，而且我想每一帧都这样做，我想问是否有更快的方法。我希望每一帧都能处理每一次碰撞并计算其后果。

Answer 1

你似乎在问的是在模拟（视频游戏）中验证机构之间碰撞的最佳解决方案。在这里，我想知道的是，在模拟（视频游戏）中验证身体之间碰撞的最佳解决方案。 是长答案。

其实这是一门完整的学科，试图高效地找到这个问题，而球的问题是这类问题的一个简单子集。

通过看到你的算法是O(N²)，你看到了实际的问题，那就是选择合适的体来测试碰撞。要想高效的实现并不是那么简单，Unity 已内置 我觉得值得一试（我不擅长使用Unity，所以在这方面帮不了你太多）。

另外，如果你很执着于自己做，我认为一个好的起点是 来划分你的空间 并只在这些小的子空间中检查碰撞。有一个 该算法的C编码版本 也许可以指导你，或者你可以直接使用它。

希望对你有所帮助!

Answer 2

除了vdere的回答，也许你可以修改和适应 最近对点算法. 与其用它来寻找彼此最近的一对点，你可以尝试寻找所有距离小于或等于相应半径之和的中心对。

另一个想到的办法是保持和更新的 德劳内三角测量法 的中心，或者它的另一个版本，称为中心的加权Delaunay三角剖面，其中权重是球的半径。有不同的算法用于生成（加权）Delaunay三角剖面或它的双版本，即 伏罗尼图. 例如，见 财富的算法.