碰撞检测的圈数很多

检查大量圈子的碰撞的最佳方法是什么？
检测两个圆之间的碰撞非常容易，但是如果我们检查每个组合，那么它就是O（n ² ） ，这绝对不是最优解。

我们可以假设圆对象具有以下属性：

• 坐标
• 半径
• 速度
• 方向

速度是不变的，但方向可以改变。

我已经提出了两个解决scheme，但也许有一些更好的解决scheme。

解决scheme1
把整个空间分成重叠的方格，只检查同一方格中的圆。 方格需要重叠，所以当一个圆从一个方格移动到另一个方格时不会有问题。

解决scheme2
开始时需要计算每对圆之间的距离。
如果距离很小，那么这些对存储在一个列表中，每次更新都需要检查是否有冲突。
如果距离很大，那么在更新之后我们会存储一个碰撞（可以计算出来，因为我们知道距离和速度）。 它需要存储在某种优先级队列中。 之前计算的更新距离数量需要再次检查后，然后我们执行相同的程序 – 把它放在列表中或再次在优先级队列中。

马克·拜尔斯问题的答案

1. 这是一款游戏吗？
   这是为了模拟，但它也可以被视为一个游戏
2. 你是否想每n毫秒重新计算一次新的位置，此时还要检查碰撞情况？
   是的，更新之间的时间是恒定的。
3. 你想find发生第一次/每次碰撞的时间？
   不，我想find每一个碰撞，并发生“事情”发生。
4. 准确度有多重要？
   这取决于你的准确性是什么。 我需要检测所有的碰撞。
5. 如果很小的快速移动的圈子偶尔可以相互传递，这是一个大问题吗？
   可以认为速度很小，不会发生。

Answer 1

我假设你正在做简单的硬球分子动力学模拟，对吗？ 我在Monte Carlo和分子动力学模拟中多次提到过同样的问题。 有关模拟的文献经常提到您的两种解决scheme。 Personaly我更喜欢解决scheme1 ，但略有修改。

解决scheme1
把你的空间分成不重叠的矩形单元。 所以当你检查一个圆的碰撞情况时，你需要寻找第一个圆的单元格内的所有圆，然后在每个方向上寻找X单元。 我已经尝试了X的许多值，发现X = 1是最快的解决scheme。 所以你必须把空间划分成每个方向的单元大小等于：

Divisor = SimulationBoxSize / MaximumCircleDiameter; CellSize = SimulationBoxSize / Divisor; 

除数应大于3，否则会造成错误（如果太小，则应放大模拟盒）。
那么你的algorithm将如下所示：

1. 把所有的圈子放在箱子里面
2. 创build单元格结构并在单元格内（数组或列表中）存储索引或指向圆的指针
3. 一步一步（移动所有内容）并更新单元格内的圆圈位置
4. 环顾四周寻找碰撞。 你应该检查每个方向的一个单元格
5. 如果有碰撞 – 做一些事情
6. 去3。

如果你会正确地写出来，那么你会有一些关于O（N）的复杂性，因为9个单元格（2D）或27个单元格（3D）内的圆圈的最大数目对于任何总数的圆圈是恒定的。

解决scheme2
Ususaly这样做是这样的：

1. 对于每个圆圈，创build距离R < R_max圆的列表，计算时间之后，我们应该更新列表（有关T_update = R_max / V_max ;其中V_max是最大当前速度）
2. 迈出一步
3. 检查每个圆圈与列表上的圆圈的距离
4. 如果有碰撞 – 做一些事情
5. 如果当前时间大于T_update ，则转到1。
6. 否则去2。

带有列表的这种解决scheme经常通过添加具有R_max_2 > R_max和其自己的T_2过期时间的另一列表来改进。 在这个解决scheme中，第二个列表用于更新第一个列表。 当然在T_2之后，你必须更新所有O（N ^ 2）的列表 。 还要小心这个T和T_2次，因为如果碰撞可以改变速度，那么这些时间就会改变。 同样，如果你在系统中引入了一些前沿，那么它也会导致速度变化。

解决scheme1 ​​+ 2您可以使用列表进行冲突检测和单元格更新列表。 在一本书中写道，这是最好的解决scheme，但我认为如果你创build小型单元格（比如我的例子），那么解决scheme1更好。 但这是我的意见。

其他的东西
您还可以做其他事情来提高模拟速度：

1. 当你计算距离r = sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) + ...)您不必做平方根运算。 你可以比较r^2某些值 – 没关系。 你也不需要做所有的(x1-x2)*(x1-x2)运算（我的意思是所有维数），因为如果x*x大于某个r_collision^2那么所有其他y*y等总结起来，会更大。
2. 分子动力学方法很容易并行化。 你可以用线程或甚至在GPU上完成。 你可以在不同的线程中计算每个距离。 在GPU上，你可以简单地创build线程几乎没有代价的线索。

对于硬球体来说，也有一种有效的algorithm，它不会按时间步进，而是在时间上寻找最近​​的碰撞，跳到这个时间并更新所有的位置。 对于不太可能发生碰撞的密度不高的系统来说，这可能是件好事。

Answer 2

有“ 空间索引 ”数据结构存储你的圈子以便后来快速比较; 四叉树，r树和kd树是例子。

解决scheme1似乎是一个空间索引，每当您重新计算您的配对时，解决scheme2将从空间索引中受益。

使事情复杂化，你的物体在移动 – 它们有速度。

在游戏和模拟中使用物体的空间索引是正常的，但大多数情况下是用于静止的物体，通常是通过移动不会对碰撞作出反应的物体。

在游戏中这是正常的 ，所以你可以按照设定的时间间隔（离散的）计算一切，所以可能是两个对象相互通过，但是由于移动得太快而没有注意到。 许多游戏实际上甚至没有按照严格的时间顺序评估碰撞。 他们有一个固定的物体（如墙壁）的空间索引，以及所有移动物体的列表，他们详尽地检查（尽pipe如我所概述，放松的离散检查）。

精确的连续碰撞检测和物体在模拟中对碰撞的反应通常要求更高。

你所概述的对方法听起来很有希望。 您可以保留这些对，并在下一次碰撞时进行sorting，并在碰撞到相应的新位置时重新插入。 您只需对两个对象的新生成的碰撞列表（O（n lg n））进行sorting，然后合并两个列表（每个对象的新的碰撞和现有的碰撞列表;插入新的碰撞，陈列碰撞的两个对象的陈旧的碰撞）是O（n）。

解决这个问题的另一个办法就是调整你的空间索引，将对象不是严格地存储在一个扇区中，而是存储在自上一次计算以来所经过的每一个扇区中，并且分离地执行。 这意味着将快速移动的对象存储在空间结构中，并且您需要针对这种情况进行优化。

请记住，链接列表或指针列表对于在现代处理器上caching非常不利 。 我build议您将任何空间索引的每个扇区中的数组（顺序存储器）或上面列出的对中存储的所有圆的副本（它们的重要属性用于碰撞检测）。

正如Mark在评论中所说的那样，计算并行可能相当简单。

Answer 3

一种可能的技术是在你的圈子的中心使用Delaunay三angular测量 。

考虑每个圆的中心，并应用delaunay三angular测量。 这将tesselate你的表面成三angular形。 这允许你build立一个graphics ，每个节点存储一个三angular形的中心，每条边连接到一个邻居圆的中心。 上面运行的tesselation将邻居的数量限制在一个合理的值（平均6个邻居）

现在，当一个圆圈移动，你有一个有限的圈子来考虑碰撞。 那么您必须再次将tesselation应用于受移动影响的一组圆，但是此操作只涉及一小部分圆（移动圆的邻居和邻居的邻居）

关键部分是第一个tesselation，这将需要一些时间来执行，后来tesselations是没有问题的。 当然你需要在时间和空间方面有效地实现graphics…

Answer 4

将您的空间分成多个区域，并保留每个区域中居中的圆圈列表。

即使你使用了一个非常简单的scheme，例如把所有的圆圈放在一个列表中，按centre.xsorting，那么你可以大幅度地加快速度。 为了testing一个给定的圆，你只需要对它在列表中任何一边的圆进行testing，直到到达一个x坐标大于半径的圆 。

Answer 5

你可以制作一个“球形树”的二维版本，这是一个特别的（而且很容易实现）的情况下，将提出的“空间索引”。 这个想法是把圆圈“组合”成一个“包含”的圆圈，直到你有一个“包含”“圆圈数量很多”的圆圈。

只是为了表示计算一个“包含圆”（头顶）的简单性：1）添加两个圆（作为向量）的中心位置和1/2的比例，即包含的中心圆2）减去两个圆的中心位置（作为vector），将半径和比例加1/2，即包含圆的半径

Answer 6

什么答案最有效率取决于圈子的密度。 如果密度较低，那么在地图上放置一个低分辨率的网格，并标记那些包含圆的网格元素可能是最有效的。 每个更新需要大约O(N*m*k) ，其中N是圆的总数， m是每个网格点的平均圆数， k是一个圆所覆盖的网格点的平均数。 如果一个圆每回合移动一个以上的网格点，则必须修改m以包含扫描的网格点的数量。

另一方面，如果密度非常高，那么最好使用graphics走路方法。 让每个圆包含距离R内的所有邻居（对于每个圆半径r_i R > r_i ）。 然后，如果你移动，你查询所有的“前进”的方向为他们的邻居，并抓住任何将在D内; 那么你就会忘记所有现在比D更远的方向。现在一个完整的更新将需要O(N*n^2) ，其中n是半径R内圆的平均数。 对于像一个紧密间隔的六边形格子的东西，这会给你比上面的格子方法好得多的结果。

Answer 7

一个build议 – 我不是游戏开发者

为什么不预先计算碰撞发生的时间

如你所述

我们可以假设圆对象具有以下属性：

坐标 –

-半径

-速度

-方向

速度是不变的，但方向可以改变。

然后，随着一个对象的方向改变，重新计算那些受影响的对。 如果方向不经常改变，这个方法是有效的。

Answer 8

正如Will在他的回答中提到的那样，空间分割树是解决这个问题的常用方法。 这些algorithm有时需要一些调整，以有效地处理移动对象。 你会想要使用一个松散的桶assembly规则，以便大部分的移动步骤不需要一个对象来改变桶。

我之前已经看到了你的“解决scheme1”，并被称为“碰撞散列”。 如果你处理的空间足够小，可以pipe理，并且你希望你的对象至less隐约地接近均匀分布，那么它可以很好地工作。 如果你的对象可能是聚集的，那很明显是如何引起问题的。 在每个散列框中使用某种types的分区树的混合方法可以帮助解决这个问题，并且可以将纯树方法转换成更容易并发扩展的方法。

重叠区域是处理横跨树桶或哈希框边界的对象的一种方式。 更常见的解决scheme是testing任何跨过边缘的对象，与相邻框中的所有对象相交，或者将对象插入到两个框中（尽pipe这需要一些额外的处理以避免突破遍历）。