利用Unity实现的碰撞检测 利用Unity实现的碰撞检测 利用Unity实现的碰撞检测

# Unity-FixSystem 利用Unity实现的2D碰撞检测,并添加四叉树优化 ### 使用分离轴算法实现的碰撞检测,模块已经独立出去一份 1.凸多边形与凸多边形 2.凸多边形与圆形 3.圆形与圆形 ### 使用四叉树算法进行场景碰撞优化 ### 在本地模拟的帧同步 ### 四叉树原理 四叉树原理来源文章:https://www.cnblogs.com/vana/p/10948789.html -- 利用四叉树思想分割场景中的所有碰撞器 -- 为整个场景构建一个四叉树,将场景中所有的碰撞器插入到该四叉树中 -- 插入规则:(从根节点开始) 如果当前节点已经分裂(即已经创建了子节点),则向子节点中插入 如果当前节点没有分裂,则插入到当前节点 插入之后: -- 当前节点存储的碰撞器列表大于规定上限:进行分裂,并将所有碰撞器分发给分裂后的子节点 -- 当前节点存储的碰撞器列表小于规定上限,没有操作 分发规则: 根据碰撞器在场景的位置进行分发,可以知道有以下三种情况: 1.完全位于某个象限内部,则将碰撞器插入到该节点中 2.完全位于某两个象限,则将碰撞器插入到这两个节点中 3.位于四个象限,则将碰撞器插入到这四个节点中 此时,某些位于边界的碰撞器则会在多个节点中存在 时间复杂度: 假设有100个物体,原始碰撞检测则需要两层循环(外层循环 0,98)(内层顺换 1,99) 即:99 + 98 + ... + 1 = (99 + 1) * 99 / 2 = 4950 时间复杂度为O(n^2) 使用四叉树检测: 这里只计算一种最优解的情况,只是用于简单的对比,实际情况只会更复杂, 将四叉树分为两层,则叶节点的数量为16个,将100个碰撞器平均的存储到16个节点中,即每个节点最多为7个碰撞器 再对每个节点进行遍历检测,则计算量为 (6 + 1) * 6 / 2 = 21;再计算所有区域,即21 * 16 = 336次 BUG:由于分布规则产生的Bug,当两个碰撞器同时在边界上时,两个碰撞器会加入到两个区间,则会发生两个区间都去检测这两个碰撞器是否发生碰撞,重复判断 修改: 修改分裂规则: 1.完全位于某个象限内部,则将碰撞器插入属于该象限的节点中 2.否则就不插入,仍放在当前节点 修改碰撞检测逻辑,将碰撞逻辑分为相互碰撞和独立碰撞 1.相互碰撞:只有一个碰撞器列表,列表中所有碰撞器两两进行碰撞检测 适用于每个节点存储的碰撞器列表 2.独立碰撞:有两个碰撞器列表,一个列表的碰撞器只去跟另外一个列表的碰撞器进行碰撞检测 适用于每个节点存储的碰撞器列表 和 其所有父节点存储的碰撞器列表