Cocos Creator 开源技术方案详解：使用四叉树优化碰撞检测

方案应用效果

四叉树（quad-tree）又称四元数，是一种树状数据结构，在每一个节点上会有四个子区块。四叉树常应用于二维空间数据的分析与分类，如果是在三维空间中，则就是八叉树。

简单来说，四叉树就是一种优化方法，能够帮助我们对元素按照区域进行划分，减少检测数量。需要说明的是，四叉树只是一种「减少碰撞候选者」的算法，在利用四叉树得到碰撞候选元素后，还需要检测这些候选元素与目标元素是否发生碰撞。

四叉树被广泛应用于游戏开发中的游戏内大地图检测、子弹碰撞检测等方面。

想象一下，假如在我们要在游戏中对200个物体进行碰撞检测，按照常规的碰撞检测方式，每帧每个物体都要对其他199个物体进行物理碰撞检测，则需要进行200*199=39800次检测。这样的检测效率，很容易对低端手机的性能造成一定的影响。

而使用四叉树则能够大大减少检测次数，那么，它又是怎么做到的呢？

我们把游戏屏幕看做一个区域，不断放置圆点进去。假设我们设定每个区域只能容纳4个物体，只要超过这个数量，就分割该区域。如下图，当区域内的圆点数达到4个，这个时候再想加入第5个，就必须先将当前区域分割为4个区域，再将第5个放入左上区域：

以此类推，当要放入第9个圆点时，我们发现黑色圆点所在的左上区域也满了，那么就需要再对左上区域再次进行分割。如下图：

最后，我们就可以得出下图这样的树状结构，这也是为什么会叫做四叉树的原因。

GitHub 用户「xjz1994」提供了一个四叉树碰撞检测优化开源方案，官方技术团队已将其升级至 Cocos Creator 3.4.1 版本。使用核心代码如下。

通过代码引入：

import { Quadtree } from "./QuadTree";

创建四叉树，区域为整个屏幕，并将树保存为全局变量：

  private tree: Quadtree = null;
    start() {
         const bounds = {
            x: 0,
            y:0,
            width: screen.width,
            height: screen.height
        }
        this.tree = new Quadtree(bounds);
    }

插入需要做碰撞检测的目标元素：

  for (let i = 0; i < 250; i++) {
            let newNode = instantiate(this.nodePrefab);
            this.node.addChild(newNode);
            this.nodes.push(newNode);
             this.tree.insert(newNode);
        }
    }

检索目标元素的待检测碰撞对象，返回碰撞候选元素组：

  //  node 为目标元素，targetNodes 为碰撞候选元素组
  let targetNodes = this.tree.retrieve(node)
  //进行碰撞检测 这个部分可以调用自己写的碰撞检测，也可以调用引擎自带的检测，这里选用自己写的
  let isCollision: any = this.isCollision(targetNode,node)

清除四叉树中的元素，以方便下次继续检测：

this.tree.clear();

https://github.com/cocos/cocos-awesome-tech-solutions/tree/3.4.0-release/demo/Creator3.4.1_2D_QuadtreeCollision

https://forum.cocos.org/t/topic/128862

四叉树或许不是最好的多物体检测算法，但是它适用于大部分情况，并且能够无缝的插入到你的项目当中。完整代码请下载方案查看，我们对四叉树算法做了详细注释，感兴趣的同学可以进行更深入的学习与优化。