每帧检查多个球之间碰撞的快速方法
Fast way to check collisions between multiple balls every frame
假设我在 2D space 中有 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²) 并且我想每一帧都这样做，我想问一下是否有更快的方法。我希望每一帧都能处理每一次碰撞并计算其后果。
您似乎要问的是在模拟（视频游戏）中验证物体之间碰撞的最佳解决方案。 Here 是长答案。
试图有效地找到它实际上是一门完整的学科，而球问题是此类问题的一个简单子集。
通过看到您的算法是 O(N²)，您看到了实际问题，即选择正确的物体来测试碰撞。 Unity 的高效实现并不那么简单 has that built-in 我认为值得一试（我对 Unity 不是很好，所以我不能在这方面帮助你太多）。
此外，如果您非常坚持自己做，我认为一个很好的起点是 to divide your space and check collision only in those small subspaces. There is a C coded version of that algorithm 也许它可以指导您，或者您可以直接使用它。
希望对您有所帮助！
除了vdere的回答，也许你可以修改和改编the closest pair of points algorithm。您可以尝试查找距离小于或等于相应半径之和的所有中心对，而不是使用它来查找彼此最接近的点对。
想到的另一件事是保留和更新 Delaunay triangulation of the centers of the balls, or maybe another version of it, called the weighted Delaunay triangulation of the centers, where the weights are the radii of the balls. There are different algorithms for generating the (weighted) Delaunay triangulation or its dual version, the Voronoi Diagram. See for example Fortune's algorithm。
假设我在 2D space 中有 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²) 并且我想每一帧都这样做，我想问一下是否有更快的方法。我希望每一帧都能处理每一次碰撞并计算其后果。
您似乎要问的是在模拟（视频游戏）中验证物体之间碰撞的最佳解决方案。 Here 是长答案。
试图有效地找到它实际上是一门完整的学科，而球问题是此类问题的一个简单子集。
通过看到您的算法是 O(N²)，您看到了实际问题，即选择正确的物体来测试碰撞。 Unity 的高效实现并不那么简单 has that built-in 我认为值得一试（我对 Unity 不是很好，所以我不能在这方面帮助你太多）。
此外，如果您非常坚持自己做，我认为一个很好的起点是 to divide your space and check collision only in those small subspaces. There is a C coded version of that algorithm 也许它可以指导您，或者您可以直接使用它。
希望对您有所帮助！
除了vdere的回答，也许你可以修改和改编the closest pair of points algorithm。您可以尝试查找距离小于或等于相应半径之和的所有中心对，而不是使用它来查找彼此最接近的点对。
想到的另一件事是保留和更新 Delaunay triangulation of the centers of the balls, or maybe another version of it, called the weighted Delaunay triangulation of the centers, where the weights are the radii of the balls. There are different algorithms for generating the (weighted) Delaunay triangulation or its dual version, the Voronoi Diagram. See for example Fortune's algorithm。