碰撞检测算法

总览

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

算法介绍

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

ExhaustiveCollisionDetection:

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

PrecisionCollisionDetection:

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

RebuildQuadTreeCollisionDetection:

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

RemoveQuadTreeCollisionDetection:

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

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

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

• Q：查询球的数量，通常表示地图中移动的球

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

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

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