利用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.独立碰撞:有两个碰撞器列表,一个列表的碰撞器只去跟另外一个列表的碰撞器进行碰撞检测
适用于每个节点存储的碰撞器列表 和 其所有父节点存储的碰撞器列表