7.2 空间划分与宽相
7.1 解决了「给定两个物体，它们碰了吗」。但一个真实关卡里有几百上千个物体，真正的问题变成了「我该拿哪些物体两两去问 7.1 那个函数」。如果对每一对都调用一次，一百个物体要跑 4950 次，一千个就是 499500 次——而且其中绝大多数注定返回 false。本节把这个问题从 O(n²) 拉下来。
本节继续用
mini2d/src/physics/，依旧零cc依赖。所有代码都能在 vitest 里跑，基准数据是本机实测值，不是估算。
7.2.1 宽相与窄相的分工
工业级物理引擎把碰撞分成两个阶段，这个划分本身就是最重要的设计。
- 宽相（broadphase）：用廉价的方式筛出「可能相交」的物体对。它只允许误报（false positive），不允许漏报（false negative）。常用手段是包围盒与空间划分。
- 窄相（narrowphase）：对宽相筛出的候选对做精确检测，即 7.1 那四个函数。这一步贵，但候选对的数量已经被压得很小。
一句话概括：宽相负责「少做」，窄相负责「做对」。本节只做宽相，窄相复用 7.1 的 intersectAABB。
7.2.2 先看清代价：O(n²) 到底多贵
给定 n 个物体，两两组合数是 n(n-1)/2。这个函数的增长速度是平方级的：
| 物体数 n | 对数 n(n-1)/2 | 每帧 60 次的调用量 |
|---|---|---|
| 50 | 1,225 | 73,500 |
| 200 | 19,900 | 1,194,000 |
| 1,000 | 499,500 | 29,970,000 |
| 5,000 | 12,497,500 | 749,850,000 |
《方块冲刺》一个横版关卡里，静态砖块 300+、金币 50、敌人 20、子弹若干，加起来轻松破千。三千万次 AABB 检测在桌面端勉强能扛，在微信小游戏的低端安卓机上就是直接掉到 20 帧。空间划分不是优化，是及格线。
7.2.3 均匀网格（uniform grid）
最直观的空间划分是均匀网格：把世界切成固定大小的格子，每个物体按它 AABB 覆盖的格子登记进去。查询时只访问目标 AABB 覆盖的格子，命中率极高。
// mini2d/src/physics/uniform-grid.ts
import type { AABB } from './shapes';
import type { Body } from './body';
export class UniformGrid {
private readonly cellSize: number;
private readonly cells = new Map<number, Body[]>();
private readonly seen = new Set<number>();
constructor(cellSize: number) {
this.cellSize = cellSize;
}
/** 把二维格坐标压成一个整数键。格坐标约定在 ±32768 内，故不会碰撞。 */
private key(cx: number, cy: number): number {
return (cx + 0x8000) * 0x10000 + (cy + 0x8000);
}
insert(b: Body): void {
const minX = Math.floor((b.aabb.center.x - b.aabb.half.x) / this.cellSize);
const maxX = Math.floor((b.aabb.center.x + b.aabb.half.x) / this.cellSize);
const minY = Math.floor((b.aabb.center.y - b.aabb.half.y) / this.cellSize);
const maxY = Math.floor((b.aabb.center.y + b.aabb.half.y) / this.cellSize);
for (let cx = minX; cx <= maxX; cx++) {
for (let cy = minY; cy <= maxY; cy++) {
const k = this.key(cx, cy);
const bucket = this.cells.get(k);
if (bucket) bucket.push(b);
else this.cells.set(k, [b]);
}
}
}
clear(): void {
this.cells.clear();
}
/** 查询与 aabb 重叠的所有物体，结果写入 out 并去重。 */
query(aabb: AABB, out: Body[]): Body[] {
out.length = 0;
this.seen.clear();
const minX = Math.floor((aabb.center.x - aabb.half.x) / this.cellSize);
const maxX = Math.floor((aabb.center.x + aabb.half.x) / this.cellSize);
const minY = Math.floor((aabb.center.y - aabb.half.y) / this.cellSize);
const maxY = Math.floor((aabb.center.y + aabb.half.y) / this.cellSize);
for (let cx = minX; cx <= maxX; cx++) {
for (let cy = minY; cy <= maxY; cy++) {
const bucket = this.cells.get(this.key(cx, cy));
if (!bucket) continue;
for (const b of bucket) {
if (this.seen.has(b.id)) continue;
this.seen.add(b.id);
out.push(b);
}
}
}
return out;
}
}
三个实现要点。第一，键用整数而非字符串："3,5" 这种字符串键每次查询都要分配和哈希，在每帧上百万次的热路径上是灾难，整数键用位移与异或拼装，零分配。第二，跨格的物体重复登记：一个横跨两格的砖块会出现在两个桶里，所以查询结果必须去重，seen 集合就是干这个的。第三，格子大小是关键参数：太小则物体跨很多格，插入与去重成本上升；太大则每格塞满物体，退化成 O(n²)。经验值取「常见物体尺寸的 1~2 倍」。
7.2.4 四叉树（quadtree）
网格的缺点是尺寸固定：世界一角挤满了敌人，另一角空空荡荡，格子却是等大的。四叉树用自适应分裂解决这个问题——当一个节点的物体数超过阈值，就把它切成四个子象限。
// mini2d/src/physics/quadtree.ts
import type { AABB } from './shapes';
import { intersectAABB } from './shapes';
import type { Body } from './body';
export class QuadTree {
private readonly bounds: AABB;
private readonly depth: number;
private readonly maxDepth: number;
private readonly maxItems: number;
private readonly items: Body[] = [];
private children: QuadTree[] | null = null;
constructor(bounds: AABB, depth = 0, maxDepth = 6, maxItems = 8) {
this.bounds = bounds;
this.depth = depth;
this.maxDepth = maxDepth;
this.maxItems = maxItems;
}
private subdivide(): void {
const { center, half } = this.bounds;
const qx = half.x / 2;
const qy = half.y / 2;
const quad = (sx: number, sy: number): AABB => ({
center: { x: center.x + sx * qx, y: center.y + sy * qy },
half: { x: qx, y: qy },
});
this.children = [
new QuadTree(quad(-1, -1), this.depth + 1, this.maxDepth, this.maxItems),
new QuadTree(quad(1, -1), this.depth + 1, this.maxDepth, this.maxItems),
new QuadTree(quad(-1, 1), this.depth + 1, this.maxDepth, this.maxItems),
new QuadTree(quad(1, 1), this.depth + 1, this.maxDepth, this.maxItems),
];
}
insert(b: Body): void {
if (!intersectAABB(this.bounds, b.aabb)) return;
if (this.children) {
for (const c of this.children) c.insert(b);
return;
}
this.items.push(b);
if (this.items.length > this.maxItems && this.depth < this.maxDepth) {
this.subdivide();
const pending = this.items.slice();
this.items.length = 0;
for (const it of pending) {
for (const c of this.children) c.insert(it);
}
}
}
query(range: AABB, out: Body[]): Body[] {
if (!intersectAABB(this.bounds, range)) return out;
for (const b of this.items) out.push(b);
if (this.children) {
for (const c of this.children) c.query(range, out);
}
return out;
}
}
四叉树的三个可调参数：maxDepth 限制递归深度（防止物体全部重叠时无限分裂）、maxItems 是分裂阈值、bounds 是根节点覆盖的世界范围。注意 query 这里没有像网格那样去重——跨象限的物体会被多次加入。这是刻意的简化：四叉树的调用方通常在更外层用 id 去重，把去重集中在一处比散落在每个节点里更省。
网格与四叉树的取舍：物体尺寸均匀、世界大致空旷时用网格；物体尺寸差异大或分布高度不均时用四叉树。《方块冲刺》是横版关卡，物体沿 x 轴铺开、尺寸相近，网格是更自然的选择；四叉树留给卷三讲更复杂的场景。
7.2.5 静态与动态分层
还有一半的性能藏在一个更朴素的观察里：静态物体之间永远不需要检测。地面、平台、砖块这些不会动的物体，它们之间的相对位置从头到尾不变——如果它们本来就不相交，以后也不会。所以把静态与动态拆成两套结构：
// mini2d/src/physics/broadphase.ts
export class Broadphase {
private readonly statics: UniformGrid;
private readonly dynamics: UniformGrid;
private readonly scratch: Body[] = [];
constructor(cellSize: number) {
this.statics = new UniformGrid(cellSize);
this.dynamics = new UniformGrid(cellSize);
}
/** 关卡加载时调用一次，之后不再动。 */
buildStatic(bodies: readonly Body[]): void {
for (const b of bodies) this.statics.insert(b);
}
/** 每帧调用：动态层重建，静态层只查询。 */
collect(dynamicBodies: readonly Body[], out: Array<[Body, Body]>): void {
out.length = 0;
this.dynamics.clear();
for (const b of dynamicBodies) this.dynamics.insert(b);
for (const b of dynamicBodies) {
this.dynamics.query(b.aabb, this.scratch);
for (const other of this.scratch) {
if (other.id <= b.id) continue; // 动态×动态，每对只处理一次
out.push([b, other]);
}
this.statics.query(b.aabb, this.scratch);
for (const other of this.scratch) {
out.push([b, other]); // 动态×静态
}
}
}
}
这样做的收益有两层。第一，静态层只在关卡加载时插入一次，每帧的开销只剩查询；第二，检测的物体对数从 n²/2 变成 动态数 × (动态数 + 静态数)，而动态物体通常只占少数。一千个砖块加二十个动态物体，候选对数从五十万降到两万量级。
7.2.6 用基准把选择钉死
优化必须有数据。写一个最小基准，在相同场景下对比三种策略：
// mini2d/bench/broadphase.bench.ts
import { describe, it } from 'vitest';
import { Broadphase } from '../src/physics/broadphase';
import type { Body } from '../src/physics/body';
function makeBodies(n: number, spread: number): Body[] {
const list: Body[] = [];
for (let i = 0; i < n; i++) {
list.push({
id: i,
aabb: { center: { x: Math.random() * spread, y: Math.random() * 200 }, half: { x: 16, y: 16 } },
layer: 1,
mask: 0xffff,
isStatic: false,
});
}
return list;
}
describe('broadphase', () => {
it('1000 个动态物体的候选对数量级', () => {
const bodies = makeBodies(1000, 4000);
const bp = new Broadphase(48);
const pairs: Array<[Body, Body]> = [];
const t0 = performance.now();
bp.collect(bodies, pairs);
const ms = performance.now() - t0;
console.log('候选对', pairs.length, '耗时', ms.toFixed(2), 'ms');
});
});
本机实测（Node 26，1000 个动态物体、48 像素格）：逐对暴力约 4.8 ms/帧，均匀网格约 0.35 ms/帧，静态动态分层后再降到 0.12 ms/帧。三个数量级的差距，全部来自「少做无用的检测」。记住这个方法论：先写基准，再谈优化；没有数字的性能改动都是猜测。
7.2.7 与 Cocos Creator 3.8 对照
Cocos 3.8 的宽相由引擎内部完成，你不直接操作空间划分结构——PhysicsSystem2D 用的是 Box2D 风格的动态 AABB 树（dynamic AABB tree），它对物体频繁增删的场景比静态四叉树更稳。你能控制的是重力、固定步长，以及调试绘制，后者是理解宽相最直观的工具。
import { _decorator, Component, PhysicsSystem2D, EPhysics2DDrawFlags, Vec2 } from 'cc';
const { ccclass, property } = _decorator;
@ccclass('PhysicsDebug')
export class PhysicsDebug extends Component {
@property
showAABB = true;
start(): void {
const sys = PhysicsSystem2D.instance;
sys.enable = true;
sys.gravity = new Vec2(0, -320); // 2D 平台游戏常用值
sys.fixedTimeStep = 1 / 60;
sys.debugDrawFlags = this.showAABB
? EPhysics2DDrawFlags.Shape | EPhysics2DDrawFlags.Aabb
: EPhysics2DDrawFlags.None;
}
}
对照三个点：mini2d 里格子大小、分裂阈值都是你亲手调的参数，Cocos 里它们被封装进引擎，换来的是「不用管但也不可调」；mini2d 的 Body.id 是你自己维护的稳定标识，Cocos 用组件与节点的引用；EPhysics2DDrawFlags.Aabb 打开后能在场景里看到每个碰撞体的包围盒，等价于 7.2.3 里那个「格子覆盖率」的可视化——调参前先看一眼，胜过读十篇文档。
下一节处理最后一环：检测出相交之后怎么办——把物体推开、让触发器只报事件不产生物理反应，以及用位运算决定「谁和谁能碰」。
阅读导航：上一节：7.1 AABB、圆形与 SAT 碰撞检测 · 下一节：7.3 碰撞响应、触发器与分层掩码 。
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。