本文来自 Cocos 中文社区第 6 期征稿活动 Cocos AIGC Creators Award，征稿持续进行中，丰富奖品等你来拿～
前言
大家好我是 98k, 好久没更新作品了，是时候为大家作贡献了。
新作品体验链接:
https://store.cocos.com/app/detail/4843
最近弹幕，割草非常的火爆，从独立开发吸血鬼幸存者大火，到大赚 10 亿的弹壳特工，还有后起的成绩喜人的通神榜，土豆兄弟，黎明前 20 分钟…相信没人能会拒绝，满屏小怪被弹雨突突的击杀的快感，还有超武的爽快激动。这次在 ChatGPT AI 的加持下，为大家提供一个支持 2000 怪同屏，通用高性能 2D/3D 动态碰撞检测方案。
技术要点
碰撞系统分为动态和静态两种，不同的情形会使用不同策略。
动态碰撞检测
主要针对运动物体，例如角色，子弹，技能等。基于智能分轴扫掠优化方案，使用了(优化版 SAP + OBB 等…)适用各种 2D/3D，运动物体检测，如角色，弹幕，子弹，攻击。
体验地址：
https://store.cocos.com/app/detail/4843
静态碰撞检测
主要针对静止物体，例如场景 , 物品 , 障碍等。基于空间静态分割优化方案，使用了(octree + kdtree + gjk + epa 等算法)适用于 3D 世界行走，3D 表面行走和 3D 边界检测(FPS, MMO, RPG 等类型的游戏)。
体验地址：
https://store.cocos.com/app/detail/4035
动态碰撞检测系统组成
1、AABB 包围盒更新
2、粗略碰撞算法筛选
3、最后形状精确碰撞
ChatGPT 能力加持
最近 AI 很火，听说它要来抢我们饭碗，看能不能交个朋友，助我实现三件套。
先科普一下，这次为什么会挑选 SAP，作为动态碰撞检测的核心筛选算法呢，因为各大物理引擎都能看它的身影，存在即是理由。SAP 全名(sweep and prune) , 是一种对轴向排序扫掠算法(有种 SAT 剪枝的味道)。
对 X 轴投影可以快速分离排除相交
优点
1、物体更新快 (物体实时更新位置)
由于要对分轴排序，你可能会想到用快排 nlogn ,但是 SAP 有个真正灵魂地方，由于运动物体相邻帧情况下排序是相对稳定，所以实际中使用插入排序会更快，大部分情况接近 o(n) 的性能，整体上会比 nlogn 快很多。其他树状如四叉，八叉，BVH ，更新物体需要调整树结构是消耗成本不低的。
2、物体间相互检测快 (常说的 trigger)
由于使用的顺序存取结构，读写性能比其他形树结构能高，同时轻易进行相互 trigger 检测，而且这顺序结构天生就带去重检测功能（例如：四叉树，八叉树，格子，这一类多次分割，还要进行去重标记检测，无形增加性能消耗）
3、支持 2D/3D 无范围限制 (兼容性)
由于是对轴向排序分割检测，所以不存空间大小限制，也不受维度的限制，很好的支持全范围的 2D/3D 空间检测。（像四叉，八叉，格子，可能会受到空间范围大小限制）
本着人生第一信条，谁提出问题就让谁来解决问题。我决定让 AI 它解决自己抛出的问题。
好家伙，一声音不哼的，啪啪啪打起代码来了，感觉流程可以但是还是缺少点灵魂，武功心法掌握的是十足，打起功夫来还是差了点。兄弟这不太行，老哥只能循循诱导，提起优化建议来。
经过一轮交谈，也收集差不多，本着个人第二信条对技术负责，在 AI 编写的框架上进行自己的精准的改造，同时结合自己的优化方式，对 SAP 算法进行了深入的改造，为后面碰撞检测提供最大的效力。
AABB 与 Shape
粗略筛选完成了，成功了一大半，还有两个环节(AABB , Shape)，如何实现？
本着个人第三信条，能不动手坚决不动手，于是再次唤醒 AI 起来啪啪啪写代码。
1、AABB 包围盒更新？
求算旋转后的 AABB，提供给 SAP 筛选
What? 打住，你给我整 8 个顶点的来算运动中的 AABB，老板看到不得血压爆表，行行再好好规劝一下。
好家伙，你是知道得挺多的就是不给我，AI 兄弟你这不厚道啊，行行赶紧给我写出代码。
兄弟(看样快成形了，我心里暗喜，再求求它)，再帮忙优化一下，游戏优化飞起，老板看到一开心，就发我薪水了。
行吧，这代码算是到点子上，本着个人第二信条对技术负责，最后优化细节简化由我再进行处理。这样 AABB 旋转更新完成，可以交付到 SAP 进行粗略碰撞筛选。
2、Shape 形状精确碰撞？
目前暂时支持 Box ,Sphere 检测(后续会支持其他常用)，支持 3D 旋转操作的碰撞。
所以我们要实现 OBB vs OBB 和 OBB vs Sphere 的检测。
本着个人第三信条，厚着脸皮再次唤醒了 AI。
1、Sphere vs Sphere 的碰撞检测，不为难它了
2、OBB vs Sphere （旋转方体与球体 精确碰撞）
有这个检测，只需要把 Sphere 转到 OBB 旋转坐标系下，就可以转化为 AABB 求交。
3、OBB vs OBB (旋转方体之间精确碰撞)
本着个人第三信条，再次让 AI 啪啪啪的工作起来。
本着个人第二信条原则，最后优化细节简化由我再进行处理。
自此，三大件在 AI 的协助下，得到了很好解决。最后在我的组装修改下，碰撞系统终于运行了起来，AI 是可以写代码，但是它不一定完美，需要从业者有一定知识储备，才能更好的发挥它效力。假以时日，在不断的训练下，和全球广大的知识网库的加持下，它终究会成为那个巨人。
最后成品，来跑个分呗
2D 测试配置：
2000 个 AABB
方格大小 20x20
范围大小 900x600
小米 10 浏览器：2000 个 ,2D AABB 碰撞测试
小米 10 浏览器：2000 个 ,3D AABB 碰撞测试
小米 10 浏览器: 简单使用示范 demo 测试
实际实测数据
测试设备：小米 10 骁龙 865 , 自带浏览器
2000 个运动 2D AABB : 平均 5ms 左右
2000 个运动 3D AABB : 平均 8ms 左右
更多的测试体验，可以行运行下面体验连接。
体验地址：
https://store.cocos.com/app/detail/4843
未来展望计划
1、增加实用 Shape
2、支持群聚的优化
3、增加高性能查询
待续…
最后，送点福利，点赞最高的五个评论（截止4月27日 12:00）可获赠《98K 高性能割草框架》（支持 2D/3D ）一套。
点击文末【阅读原文】查看原贴
往期精彩
