为了在游戏的每一帧中检测球体的碰撞，以便更新球体的状态，我们需要设计高效的碰撞检测算法。因此，我们设计了四种碰撞检测算法，并将它们封装成以下四类。下面仅介绍算法相关结果，更多细节请查看源码。
四种算法的介绍和理论时间复杂度如下：
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表示实际碰撞的球体数量。
为了测试这些算法的效率，我们修改了球总数、查询数、改变球数、迭代轮数等参数来设置测试场景。下表中的数据来自最具代表性的场景：
- T：地图中所有球的数量
- Q：查询球的数量，通常表示地图中移动的球
- C：需要修改的球的数量，即碰撞次数
| 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 |
为了更直观的看到每种算法的优劣，我们整合了测试数据，绘制了四种算法和各种参数的图表如下：
.. only:: html
.. figure:: images/changed_num_3000.png
:width: 600
:align: center
.. only:: html
.. figure:: images/query_num_3000.png
:width: 600
:align: center
.. only:: html
.. figure:: images/iters_num_3000.png
:width: 600
:align: center
根据结果，我们可以认为 PrecisionCollisionDetection 算法在效率和稳定性方面都远远优于其他算法。