碰撞检测算法

总览

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

算法介绍

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

ExhaustiveCollisionDetection:

碰撞检测算法 - 图1

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

PrecisionCollisionDetection:

碰撞检测算法 - 图2

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

RebuildQuadTreeCollisionDetection:

碰撞检测算法 - 图3

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

RemoveQuadTreeCollisionDetection:

碰撞检测算法 - 图4

优化后的重建四叉树解法,增加了对四叉树的删除和维护。其中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

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

../_images/changed_num_3000.png

../_images/query_num_3000.png

../_images/iters_num_3000.png

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