一、四叉树的实现原理是什么？

四叉树本身是树结构的一种，如果物体过多的话，先根据物体所处位置划分成四块，如果每个块的中的物体数量还是很多的话，继续划分成四块

检测的时候，就是根据待测试对象的位置，去找属于哪个块，再把这个块中的物体告诉你。如下图中的绿色物体

二、如何实现

1.引入库

GitHub里有一个写好的库，拿过来改改就行

https://github.com/timohausmann/quadtree-js

2.那么怎么检测碰撞呢？

代码如下（示例）：
function testContact(collider1, collider2) {
    // 分组不通过
    if (!cc.director.getCollisionManager()['shouldCollide'](collider1, collider2)) {
        return false;
    }

    let world1 = collider1.world;
    let world2 = collider2.world;
    if (!world1.aabb.intersects(world2.aabb)) {
        return false;
    }

    let isCollider1Polygon = (collider1 instanceof cc.BoxCollider) || (collider1 instanceof cc.PolygonCollider);
    let isCollider2Polygon = (collider2 instanceof cc.BoxCollider) || (collider2 instanceof cc.PolygonCollider);
    let isCollider1Circle = collider1 instanceof cc.CircleCollider;
    let isCollider2Circle = collider2 instanceof cc.CircleCollider;

    if (isCollider1Polygon && isCollider2Polygon) {
        return cc.Intersection.polygonPolygon(world1.points, world2.points);
    } else if (isCollider1Circle && isCollider2Circle) {
        return cc.Intersection.circleCircle(world1, world2);
    } else if (isCollider1Polygon && isCollider2Circle) {
        return cc.Intersection.polygonCircle(world1.points, world2);
    } else if (isCollider1Circle && isCollider2Polygon) {
        return cc.Intersection.polygonCircle(world2.points, world1);
    } else {
        // cc.errorID(6601, cc.js.getClassName(collider1), cc.js.getClassName(collider2));
    }
    return false;
}

最后再结合四叉树碰撞，检测代码如下

check(colliders: cc.Collider[], testCollider: cc.Collider) {
    const ret: { retrieve: cc.Collider[], contacts: cc.Collider[] } = { retrieve: [], contacts: [] };

    // 四叉树清理
    this._tree.clear();
    const collisionManager = cc.director.getCollisionManager();
    collisionManager['updateCollider'](testCollider);
    for (let i = 0, l = colliders.length; i < l; i++) {
        const collider = colliders[i];
        // 更新碰撞体世界aabb
        collisionManager['updateCollider'](collider);
        const aabb = collider['world'].aabb;
        const rect = { x: aabb.x, y: aabb.y, height: aabb.height, width: aabb.width, collider: collider };
        // 四叉树插入
        this._tree.insert(rect)
    }
    // 四叉树抓出待检查的对象(属于那个块的所有节点)
    const retrieveObjects = this._tree.retrieve(testCollider['world'].aabb);
    retrieveObjects.forEach(element => {
        ret.retrieve.push(element.collider);
        // 抓出来后检查碰撞
        if (testContact(element.collider, testCollider)) {
            ret.contacts.push(element.collider);
        }
    });

    return ret;
}

---

总结

其实很简单，就是分块检测 寻找对应的分块去检测  按照这个思路去摸索就好了