bit-quadtree：碰撞检测从 O(n²) 降下来，靠的是空间分割

它解决什么问题

场景里有 200 个单位，最朴素的碰撞检测写法是每个单位跟其他所有单位两两比较一遍，这是 O(n²) 的复杂度——单位数翻一倍，计算量翻四倍。数量少的时候感觉不出来，一旦到弹幕游戏、塔防、RTS 这种同屏单位数量上百的场景，帧率立马就能感受到差距。

四叉树是经典的空间分割结构：把整个场景按空间位置分成若干个小区域，查询一个物体的碰撞时，只需要跟它所在区域附近的物体比较，不用跟场景里所有物体比较一遍。bit-quadtree 就是这个结构的 TypeScript 实现，专门给 2D 游戏用。

安装

npm install @gongxh/bit-quadtree

核心用法

创建四叉树

import { QuadTree, createBox, createCircle } from '@gongxh/bit-quadtree';

// x, y 是根节点位置，width/height 是覆盖区域大小
// maxDepth 建议 4~6，maxShapes 建议 10~20
const tree = new QuadTree(0, 0, 2000, 2000, 5, 15);

maxDepth 和 maxShapes 是两个需要按场景实际情况调的参数：树分得越深，单个节点里的物体越少，查询越精确但树本身的维护开销越大；maxShapes 是触发继续往下分裂的阈值，值太小会分裂出很多几乎是空的子节点，值太大又会退化成”一个大区域里塞了一堆物体”，跟不用四叉树没什么区别。

插入形状

const enemy = createBox(100, 100, 50, 50); // 矩形碰撞体
const bullet = createCircle(5);             // 圆形碰撞体

tree.insert(enemy);
tree.insert(bullet);

也支持凸多边形 createPolygon(vertices)，用来表示不规则形状的碰撞区域。

查询碰撞

const nearby = tree.query(bullet);
for (const shape of nearby) {
    // 处理碰撞逻辑
}

binaryMask 参数可以用来做分组过滤，比如子弹只想检测”敌人”分组的物体，不想检测”友方”分组：

const nearby = tree.query(bullet, ENEMY_MASK);

要注意这个掩码只是简单的按位相交判断（binaryMask & shape.mask 非零就返回），它不是”分组自动互斥”的碰撞分组系统——具体两个物体该不该碰撞的业务逻辑，还是要在查询结果的基础上自己判断。

物体移动之后

场景里的物体位置会变，四叉树需要跟着更新，不然查询结果还是基于旧位置算出来的：

// 每帧或者物体移动后调用
tree.update();

清理

tree.clear(); // 退出场景时清空，释放所有节点

性能特点

内部用了对象池管理节点和形状对象，频繁的插入删除不会带来太多 GC 压力，这点在移动端尤其重要——GC 卡顿在手机上比 PC 上明显得多。Vec2 向量类提供了距离、归一化这些常用运算，配合形状创建函数基本不需要自己再手写一套向量数学。

避坑提醒

  • maxDepth/maxShapes 没有放之四海皆准的最优值，需要根据你场景里物体的数量和分布密度实测调整，密度不均匀的场景（比如物体都堆在屏幕一角）容易出现某个子节点特别拥挤的情况。
  • 物体移动后忘记调用 update()，是最容易踩的坑——查询用的还是过时的空间位置，可能会漏检测本该碰撞的物体，或者检测出本不该碰撞的。
  • query 返回的是”可能碰撞”的候选集合（基于空间邻近关系筛出来的），不是精确的碰撞判定结果，具体两个形状是否真的相交，还需要业务层再做一次精确的几何判断。

项目信息

零依赖，独立使用，纯 TypeScript 实现，不限定 Cocos Creator，任何 2D 场景都能用。