碰撞检测算法

算法介绍

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

ExhaustiveCollisionDetection:

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

PrecisionCollisionDetection:

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

RebuildQuadTreeCollisionDetection:

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

RemoveQuadTreeCollisionDetection:

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

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

• T：地图中所有球的数量

• C：需要修改的球的数量，即碰撞次数

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

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