碰撞检测算法

总览

为了在游戏的每一帧中检测球体的碰撞，以便更新球体的状态，我们需要设计高效的碰撞检测算法。因此，我们设计了四种碰撞检测算法，并将它们封装成以下四类。下面仅介绍算法相关结果，更多细节请查看源码。

四种算法的介绍和理论时间复杂度如下：

ExhaustiveCollisionDetection:

\(O(n*m)\)

暴力解法，其中 n 表示球的总数，m 表示要询问的球数。

PrecisionCollisionDetection:

\(O(n*log(n)+\Sigma{r}*logn+p)\)

卡精度解法。其中 n 表示球的总数，m 表示要询问的球数，k 表示我们设置的精度，p 表示实际碰撞的球体数量。

RebuildQuadTreeCollisionDetection:

\(O(n*log(n) + m*log(n)+p)\)

重建四叉树解法。其中 n 表示球的总数，m 表示要询问的球数，p 表示实际碰撞的球体数量。

RemoveQuadTreeCollisionDetection:

\(O(r*log(n)+m*log(n)+p)\)

优化后的重建四叉树解法，增加了对四叉树的删除和维护。其中n表示球的总数，m表示要询问的球数，r表示位置状态发生变化的球体数量，p表示实际碰撞的球体数量。

为了测试这些算法的效率，我们修改了球总数、查询数、改变球数、迭代轮数等参数来设置测试场景。下表中的数据来自最具代表性的场景：

	Exhaustive	Precision	Rebuild QuadTree	Remove QuadTree
T=3000 Q=300 C=600	688ms	14ms	47ms	48ms
T=3000 Q=300 C=1500	1067ms	16ms	50ms	178ms
T=10000 Q=1000 C=2000	8384ms	61ms	339ms	497ms
T=10000 Q=2000 C=5000	12426ms	86ms	586ms	2460ms
T=30000 Q=6000 C=3000	127000ms	403ms	5691ms	8419ms

为了更直观的看到每种算法的优劣，我们整合了测试数据，绘制了四种算法和各种参数的图表如下：

根据结果，我们可以认为 PrecisionCollisionDetection 算法在效率和稳定性方面都远远优于其他算法。