使用四叉树优化碰撞检测
- 2020 年 6 月 18 日
- 筆記
四叉树是干什么的？
百度百科
四元树又称四叉树是一种树状数据结构，在每一个节点上会有四个子区块。四元树常应用于二维空间数据的分析与分类。 它将数据区分成为四个象限。数据范围可以是方形或矩形或其他任意形状。
从定义我们可以看出重点信息：
- 树状结构
- 四个区块
- 分类
- 矩形
图示讲解
讲解之前需要先说明一下四叉树是用来做什么的，明白了原理才好理解它的行为。
使用四叉树就是使用分类的方法，减少碰撞节点的个数，只取出与给定碰撞体相同区域或者压在碰撞体所在区域边上的对象。
- 将游戏屏幕分为四个区域。
- 插入对象
- 插入的对象超过了我们设置的阈值时，划分
- 插入的对象再次超过了我们设置的阈值时，继续分。
分析
插入
从上面的图示我们可以很好理解四叉树的原理。涉及的都是插入操作。
那么插入操作具体都做了什么呢？
从代码中我们可以看出：
- 当插入第一个对象的时候只走了2；这个时候没有子树，所以不会走1，因为objects（管理的对象）的长度还没有超过我们设置的阈值MAX_OBJECTS,所以也不会走3。
- 一直插入，当objects中的数量，超过了我们设置的阈值MAX_OBJECT,就会开始划分，产生子树，有了nodes，划分之后将自己管理的节点插入到子树中。再此之前，都不会走1，因为还没有产生子树。
- 划分之后再次插入新对象，如果对象可以获得对应的象限，就会走1 不会走2和3，如果没有获得对应的象限才会走2，3（没有获得的情况可能是你创建的对象在屏幕外，游戏中很多情况是敌人从屏幕外走进屏幕的，具体可参考我做的《星际迷航》或者《星际战》游戏）。
更新对象
我是把四插入作为了对象管理器使用，要不然对象也需要更新，所以有了这一步操作。如果不这样你需要自己创建对象管理器，一个一个放进去，删除。通过四叉树直接管理省了不少事情。
更新象限信息。
这是一个递归操作，更新象限做的事情比较多了。
-
检查对象是否存活，如果死亡就回收，我这里使用了对象池，所以对象实现了poolAble接口。
-
判断对象的所占区域是否在四叉树的区域内
这里需要说明的是一个四叉树本身的区域是它管理的四个象限这么大。也就是一个四叉树管理四个象限
不在管理区域的话需要判断当前this是否为根节点，如果是说明对象已经出屏了。（这个时候可以通过对象实现的isVisible接口来控制是否回收，因为不是所有在屏幕外的都要回收，比如要进入屏幕的敌人，是不可能回收的，所以需要自己用isVisible接口来控制）。如果不是就将对象放入根节点，重新划分。 -
在管理区域内，就看看在四叉树管理的哪个象限里。更新象限信息。
如果没有变化什么都不过，如果有变化，先判断象限是否为-1，为什么会出现-1，也就是不在四个象限的任何一个象限？因为压线了。此番操作后的结果如下图。
根据给定矩形获取对象列表
- 第一个是步长，用于获取深度，当然深度越长，处理的时间越长，获取的对象也精细。这个可以根据自己游戏的同屏四叉树层级而定了。
- 如果通过obj的rect获得对象所在象限如果获得了对应的象限，用获得的象限的四叉树再获取。如果压线的话就需要将碰撞的两个象限的内容都取出来。
- 返回四叉树中没有分割象限的对象。
怎么用呢？
自然就是把要碰撞的对象传给retrieve函数获得需要碰撞的对象列表进行碰撞检测了。
也就是文章靠头说的：
使用四叉树就目的是为了减少碰撞节点的个数。使用的是分类的方法。
至于用什么样的碰撞检测函数，不是四叉树关心的事情，
至于用几个四叉树管理对象，也不是四叉树关心的事情。
结语
想要demo的同学可以去我的微店或者官方creator商城购买《跨引擎游戏框架》源码，跟demo是一个项目。买过的同学请加我好友，群已经建好，有更新我会群里直接发包。
源码购买入口：
demo展示：
项目截图：
框架的相关模块教程可以到《我的专辑》游戏开发进阶教程中获取。
后续还会推出更多与框架有关的教程：如：战斗框架，教学框架等等。并附带完整的游戏实现（飞行射击游戏为例，学会做飞行射击游戏不是目的，目的是通过这一款游戏，你可以获得做其他所有类型的游戏的思路）。希望可以在不饿死自己的前提下帮助更过的朋友们快速找到开发思路。
长按下方二维码，关注《微笑游戏》公众号，获取更多精彩内容。
欢迎扫码关注公众号《微笑游戏》，浏览更多内容。
