四叉树原理本人就不赘述了，很多前辈都有详细的讲解
首先说明下四叉树并不是一个碰撞引擎，它只是一种减少碰撞候选者的算法，所以在利用四叉树得到碰撞候选元素后，还需要去检测这些候选元素与目标元素是否发生碰撞
2D中是四叉树，3D中则对应的为八叉树
项目（微信小游戏《宇宙少女》）中实测：
同屏极限情况下，可碰撞元素为：
200左右子弹+70左右怪物+若干buff+玩家
碰撞关系为：
子弹和怪物碰撞
特定怪物和其他怪物碰撞反弹
玩家和怪物碰撞
玩家和buff碰撞
使用cocos的碰撞系统，在H5表现良好，微信小游戏的Android平台也还可以，但是在ios平台上，FPS只有20+
使用四叉树做空间规划，对子弹做进一步的优化，减少碰撞元素
碰撞检测使用圆圆碰撞和圆矩碰撞，放弃了pow()和sqrt()方法， 其相对于加减乘除会消耗更多的CPU（之前在QQ群讨论过）
改良后的碰撞检测在微信小游戏的Android平台性能良好，IOS平台的FPS也达到了50+
项目中使用每帧重建四叉树，当然也可以自己维护四叉树中碰撞元素的位置
1四叉树概念
四叉树（quad-tree）是一种数据结构，是一种每个节点最多有四个子树的数据结构。四叉树是在二维图片中定位像素的唯一适合的算法。因为二维空间（图经常被描述的方式）中，平面像素可以重复的被分为四部分，树的深度由图片、计算机内存和图形的复杂度决定。四叉树可以用来在数据库中放置和定位文件（称作记录或键）。这一算法通过不停的把要查找的记录分成4部分来进行匹配查找直到仅剩下一条记录为止。
2空间规划
游戏编程模式-空间分区
将对象存储在根据位置组织的数据结构中来高效地定位它们。 你有一组对象（可能还挺多），将对象存储在一个根据对象位置来组织的数据结构中，该数据结构可以让你高效查询位于或靠近某处的对象。当对象位置改变时，更新并继续维护该空间数据对象。用更复杂的数据结构（空间）来换取大量查询时的性能优化（时间）。
博客园中一篇讲解详细的blog
https://www.cnblogs.com/xin-lover/p/12216053.html
3
quadtree-js
在GitHub上找到的一个前辈实现的四叉树：
https://github.com/timohausmann/quadtree-js
并提供了两个在线演示的demo，其中红色为四叉树节点，空白方块为四叉树中的元素，灰色方块为鼠标的位置，即目标元素，绿色方块为碰撞候选元素
1.手动添加静态对象并查看四叉树拆分：
https://timohausmann.de/quadtree.js/simple.html
2.在持续运动的对象中查看四叉树拆分：
https://timohausmann.de/quadtree.js/dynamic.html
4使用方法
1.引入quadtree.js
①通过代码引入：
import * as Quadtree from “…/R-framework/quadtree.js”;
②插件引入：
将quadtree.js文件导入编辑器的时候选择为插件
2.创建四叉树
区域为整个屏幕
let myTree = new Quadtree({
x: -cc.winSize.width / 2,
y: -cc.winSize.height / 2,
width: cc.winSize.width / 2,
height: cc.winSize.height / 2
});
3.插入元素
参数为元素的左下角坐标及其宽高
myTree.insert({
x: 200,
y: 150,
width: 20,
height: 20
});
4.检索元素
参数为目标元素的左下角坐标及其宽高
返回值为碰撞候选元素数组
let elements = myTree.retrieve({
x: 150,
y: 100,
width: 20,
height: 20
});
5.碰撞检测
在得到碰撞候选元素后，需要检测是否与目标元素发生碰撞，检测的方法可以用cocos的碰撞组件，也可以根据项目需求定制碰撞检测
6.清除四叉树
检测完毕后，需要清除四叉树中的元素，以方便下次继续检测
myTree.clear();
或者维护四叉树空间中碰撞元素的位置
