站内《游戏引擎实现原理》四卷 180 篇 是从零实现引擎内核（含 ECS 与系统调度），那里会讲一套通用的碰撞管线怎么搭；本章讲的是小游戏语境下到底需要多少物理：分级取舍、轻量碰撞与空间划分、手感参数。差别在于，那边把碰撞做成框架，这边只做《合成小岛》真正会用到的那几十行。
上一节把物理需求分了五级，并说明《合成小岛》落在 t1（矩形相交）、将来可能补到 t2（圆 + 网格）。这一节就动手把 t1 和 t2 里最核心的部分写出来：怎么判定两个物体相撞，以及物体多起来时怎么不算那么多次。
轻量碰撞：只做需要的那一层
碰撞检测在工程上分两段：broad phase（粗筛，快速排除不可能相撞的对）和 narrow phase（细判，对候选对做精确相交测试）。t1 的玩法实体少，broad phase 直接暴力两两比就行；t2 的实体可能上千，暴力就成了 O(n²)。这一节把两段都写出来，并让 broad phase 在暴力和网格之间可切换。
narrow phase 只有两个原语：AABB 相交（矩形，四边分离即不相交）和圆相交（比较平方距离，避免开方）。小游戏里 99% 的判定都能归到这两个原语上。
P 层：AABB / 圆 / 网格
下面这段是 P 层（内核层）产物：core/src/e07/collision.ts。它是纯函数式的碰撞内核——输入几何体，输出是否相交或相交对列表。全整数坐标、无 Math.random()、无开方，因此既能被单元测试直接跑，也能被浏览器原型内联。
// file: core/src/e07/collision.ts
// tier: P
// verify: node --test 'core/test/e07_*.test.ts'
//
// 《合成小岛》轻量碰撞内核：AABB 相交、圆相交（平方距离比较，无开方）、
// 以及按网格做的空间划分 broad phase。全整数坐标、无 Math.random()、只用可擦除语法。
// 正确性前提：cellPx >= 2 * maxRadiusPx 时，只查 3x3 邻域即可判定圆相交。
export interface Vec { x: number; y: number }
export interface Aabb { x: number; y: number; w: number; h: number }
export interface Circle { x: number; y: number; r: number }
export interface Body { id: number; x: number; y: number; r: number }
export interface GridConfig { cellPx: number; cols: number; rows: number }
function fclamp(v: number, lo: number, hi: number): number { return v < lo ? lo : v > hi ? hi : v; }
/** AABB 相交：四边分离即不相交（严格不等号，贴边不算相交）。 */
export function aabbOverlap(a: Aabb, b: Aabb): boolean {
return a.x < b.x + b.w && b.x < a.x + a.w && a.y < b.y + b.h && b.y < a.y + a.h;
}
/** 圆相交：比较平方距离，避免开方；贴边（距离 == 半径和）算相交。 */
export function circleOverlap(a: Circle, b: Circle): boolean {
const dx = a.x - b.x, dy = a.y - b.y, rr = a.r + b.r;
return dx * dx + dy * dy <= rr * rr;
}
/** 矩形与圆相交：取矩形上离圆心最近的点，再比平方距离。 */
export function aabbCircleOverlap(a: Aabb, c: Circle): boolean {
const nx = fclamp(c.x, a.x, a.x + a.w);
const ny = fclamp(c.y, a.y, a.y + a.h);
const dx = c.x - nx, dy = c.y - ny;
return dx * dx + dy * dy <= c.r * c.r;
}
/** 由世界尺寸与网格边长推导网格维度（向上取整，整数运算）。 */
export function gridOf(worldPx: number, cellPx: number): GridConfig {
const n = (worldPx + cellPx - 1) / cellPx;
const cols = Math.floor(n);
return { cellPx, cols, rows: cols };
}
/** 坐标 -> 单元下标（clamp 到网格内，越界坐标也落进边缘单元）。 */
export function cellIndex(g: GridConfig, x: number, y: number): number {
const col = fclamp(Math.floor(x / g.cellPx), 0, g.cols - 1);
const row = fclamp(Math.floor(y / g.cellPx), 0, g.rows - 1);
return row * g.cols + col;
}
/** 某个坐标点所在单元的 3x3 邻域单元下标（去掉越界部分）。 */
export function neighborCells(g: GridConfig, x: number, y: number): number[] {
const col = fclamp(Math.floor(x / g.cellPx), 0, g.cols - 1);
const row = fclamp(Math.floor(y / g.cellPx), 0, g.rows - 1);
const out: number[] = [];
for (let dr = -1; dr <= 1; dr += 1) {
for (let dc = -1; dc <= 1; dc += 1) {
const r = row + dr, c = col + dc;
if (r >= 0 && r < g.rows && c >= 0 && c < g.cols) out.push(r * g.cols + c);
}
}
return out;
}
/** 把实体按中心点分桶到网格：返回每个单元里的实体下标列表。 */
export function buildGrid(g: GridConfig, bodies: Body[]): number[][] {
const cells: number[][] = [];
for (let i = 0; i < g.cols * g.rows; i += 1) cells.push([]);
for (let i = 0; i < bodies.length; i += 1) cells[cellIndex(g, bodies[i].x, bodies[i].y)].push(i);
return cells;
}
/** 暴力求全部真实相交对（返回排序后的 "i,j" 列表，用于与网格结果对照）。 */
export function bruteOverlapPairs(bodies: Body[]): string[] {
const out: string[] = [];
for (let i = 0; i < bodies.length; i += 1) {
for (let j = i + 1; j < bodies.length; j += 1) {
if (circleOverlap(bodies[i], bodies[j])) out.push(i + "," + j);
}
}
return out;
}
/** 网格求全部真实相交对：broad phase 只给候选，narrow phase 再判圆相交。 */
export function gridOverlapPairs(g: GridConfig, bodies: Body[]): string[] {
const cells = buildGrid(g, bodies);
const out: string[] = [];
for (let i = 0; i < bodies.length; i += 1) {
const a = bodies[i];
for (const ci of neighborCells(g, a.x, a.y)) {
for (const j of cells[ci]) {
if (j > i && circleOverlap(a, bodies[j])) out.push(i + "," + j);
}
}
}
out.sort((p, q) => {
const pi = Number(p.split(",")[0]), pj = Number(p.split(",")[1]);
const qi = Number(q.split(",")[0]), qj = Number(q.split(",")[1]);
return pi - qi || pj - qj;
});
return out;
}
圆相交那一行是这套内核的关键：dx * dx + dy * dy <= rr * rr。它比较的是平方距离，从头到尾没有 Math.sqrt。对「是否相交」这种布尔判定来说，开方是纯浪费——a² + b² <= r² 与 sqrt(a² + b²) <= r 等价，但前者全是整数乘法，跨平台结果完全一致（浮点开方在极端值上会有误差）。这是小游戏碰撞代码的第一条纪律：能比平方就别开方。gridOf 里的 (worldPx + cellPx - 1) / cellPx 是整数上取整（ceil 的整数写法），避免浮点；neighborCells 返回 3x3 邻域，角单元只有 4 个、内部单元 9 个，这是空间划分的边界处理，也是最容易漏掉的地方。
P 层测试：网格必须与暴力结果一致
空间划分最怕「漏判」：网格把两个真相撞的物体分到不相邻的单元，就漏掉了。所以测试的核心不是「网格更快」，而是**「网格和暴力求出的相交对完全一致」**。P 层测试 core/test/e07_collision.test.ts 用可播种 LCG 撒点，让两种方法对拍。跑它，输出是这样（同机相对量级，耗时不可移植）：
✔ AABB：相交与分离
✔ 圆：贴边算相交（平方距离比较，无开方）
✔ 矩形与圆：最近点法
✔ 网格维度与单元下标（越界坐标 clamp 到边缘单元）
✔ 分桶：每个实体恰好落进一个单元
✔ 网格与暴力求得完全相同的相交对（正确性）
✔ 网格候选对数远小于暴力（同机相对量级）
✔ 同一输入两遍结果一致（无隐藏随机）
ℹ tests 8
ℹ pass 8
ℹ fail 0
第六行是这套实现的「安全网」：600 个随机圆里，网格与暴力求出的相交对逐条相等，证明在 cellPx >= 2 * radiusPx 的前提下 3x3 邻域不会漏判。测试里的点集用可播种 LCG而不是 Math.random() 生成——这样每次跑的点集完全一样，断言才能稳定，也符合 core/ 的确定性要求。
S 层：候选对数随实体数增长
P 层证明了「网格判得对」，但没量化「网格省多少」。下面这段是 S 层（仿真层）脚本：它在同样的世界里撒不同数量的圆，统计暴力与网格两种 broad phase 的候选对数（也就是检测次数），并核对两种方法的真实相交对完全一致。它读的配置 config/e07_collision.json 是这样：
{
"version": 1,
"game": "merge-island",
"seed": 20261012,
"note": "碰撞检测复杂度对照参数：世界尺寸 / 网格边长 / 实体半径全为像素整数。cellPx >= 2*radiusPx 是「只查 3x3 邻域即可判定圆相交」的正确性前提。",
"worldPx": 960,
"cellPx": 48,
"radiusPx": 24,
"counts": [100, 200, 400, 800, 1600, 3200],
"rounds": 8
}
#!/usr/bin/env python3
# file: sim/e07_collision_bench.py
# tier: S
# verify: /opt/homebrew/bin/python3 sim/e07_collision_bench.py --config config/ --out out/
"""碰撞 broad phase 复杂度对照：暴力 O(n^2) vs 网格 3x3 邻域，全整数、纯 Python SVG。
产出 out/e07_collision_bench.json + _bench.csv + _bench.svg。"""
from __future__ import annotations
import argparse
import csv
import json
import os
import xml.etree.ElementTree as ET
def make_bodies(n, world, r, seed):
"""可播种 LCG（Numerical Recipes），与 core 测试同口径。"""
s, span, out = seed & 0xFFFFFFFF, world - 2 * r, []
for _ in range(n):
pts = []
for _ in range(2):
s = (1664525 * s + 1013904223) & 0xFFFFFFFF
pts.append(r + s % span)
out.append((pts[0], pts[1], r))
return out
def buckets(bodies, cell, cols):
cs = [[] for _ in range(cols * cols)]
for i, b in enumerate(bodies):
cs[min(b[1] // cell, cols - 1) * cols + min(b[0] // cell, cols - 1)].append(i)
return cs
def near(x, y, cell, cols):
"""坐标点所在单元的 3x3 邻域下标（去掉越界部分）。"""
c, r = min(x // cell, cols - 1), min(y // cell, cols - 1)
return [rr * cols + cc for rr in range(max(0, r - 1), min(cols, r + 2))
for cc in range(max(0, c - 1), min(cols, c + 2))]
def hit(a, b):
dx, dy, rr = a[0] - b[0], a[1] - b[1], a[2] + b[2]
return dx * dx + dy * dy <= rr * rr
def bench(n, world, r, cell, cols, seed):
bodies = make_bodies(n, world, r, seed)
cs = buckets(bodies, cell, cols)
cand, ghits = 0, []
for i, a in enumerate(bodies):
for ci in near(a[0], a[1], cell, cols):
for j in cs[ci]:
if j > i:
cand += 1
if hit(a, bodies[j]):
ghits.append((i, j))
bhits = sorted((i, j) for i in range(n) for j in range(i + 1, n) if hit(bodies[i], bodies[j]))
assert sorted(ghits) == bhits, f"网格与暴力相交对不一致 n={n}"
return n * (n - 1) // 2, cand, len(bhits)
def draw_svg(path, rows):
"""横轴实体数，两条折线分别为暴力与网格候选对数。"""
W, H, L, T, PW, PH = 760, 400, 70, 50, 660, 300
mx = max(r["brutePairs"] for r in rows) or 1
step = PW // max(1, len(rows) - 1)
svg = ET.Element("svg", {"xmlns": "http://www.w3.org/2000/svg",
"width": str(W), "height": str(H), "viewBox": f"0 0 {W} {H}"})
ET.SubElement(svg, "rect", {"width": str(W), "height": str(H), "fill": "#ffffff"})
for key, color, label, tx in (("brutePairs", "#dc2626", "暴力 C(n,2)", L),
("gridPairs", "#2563eb", "网格 3x3", L + 140)):
pts = " ".join(f"{L + i * step},{T + PH - PH * r[key] // mx}" for i, r in enumerate(rows))
ET.SubElement(svg, "polyline", {"points": pts, "fill": "none", "stroke": color,
"stroke-width": "2"})
ET.SubElement(svg, "text", {"x": str(tx), "y": str(T - 8), "font-size": "12",
"fill": color}).text = label
for i, r in enumerate(rows):
ET.SubElement(svg, "text", {"x": str(L + i * step - 12), "y": str(T + PH + 20),
"font-size": "11", "fill": "#6b7280"}).text = str(r["n"])
os.makedirs(os.path.dirname(path), exist_ok=True)
ET.ElementTree(svg).write(path, encoding="utf-8", xml_declaration=True)
return len(ET.tostring(svg))
def main() -> int:
ap = argparse.ArgumentParser()
ap.add_argument("--config", default="config/")
ap.add_argument("--out", default="out/")
args = ap.parse_args()
cfg = json.load(open(os.path.join(args.config, "e07_collision.json"), encoding="utf-8"))
world, cell, r, seed = cfg["worldPx"], cfg["cellPx"], cfg["radiusPx"], cfg["seed"]
cols = (world + cell - 1) // cell
assert cell >= 2 * r, "cellPx 必须 >= 2*radiusPx，否则 3x3 邻域不足以判定相交"
rows = []
for n in cfg["counts"]:
bp, gp, hits = bench(n, world, r, cell, cols, seed)
rows.append({"n": n, "brutePairs": bp, "gridPairs": gp, "hits": hits, "ratioPct": gp * 100 // bp})
report = {"version": cfg["version"], "game": cfg["game"], "seed": seed, "worldPx": world,
"cellPx": cell, "radiusPx": r, "cols": cols,
"note": "同机相对量级，绝对数值不可移植；候选对数为 broad phase 检测次数。", "rows": rows}
os.makedirs(args.out, exist_ok=True)
report["svg"] = os.path.join(args.out, "e07_collision_bench.svg")
report["svgBytes"] = draw_svg(report["svg"], rows)
with open(os.path.join(args.out, "e07_collision_bench.json"), "w", encoding="utf-8") as f:
json.dump(report, f, ensure_ascii=False, indent=2)
with open(os.path.join(args.out, "e07_collision_bench.csv"), "w", encoding="utf-8", newline="") as f:
w = csv.writer(f)
w.writerow(["n", "brutePairs", "gridPairs", "hits", "gridPctOfBrute"])
for r in rows:
w.writerow([r["n"], r["brutePairs"], r["gridPairs"], r["hits"], r["ratioPct"]])
last = rows[-1]
print(json.dumps({"maxN": last["n"], "brutePairs": last["brutePairs"], "gridPairs": last["gridPairs"],
"gridPctOfBrute": last["ratioPct"], "hitsAtMaxN": last["hits"]}, ensure_ascii=False))
return 0
if __name__ == "__main__":
raise SystemExit(main())
在本机跑它，输出是这样（同机相对量级，绝对数值不可移植）：
{"maxN": 3200, "brutePairs": 5118400, "gridPairs": 117651, "gridPctOfBrute": 2, "hitsAtMaxN": 43592}
落盘的 out/e07_collision_bench.csv 把每个实体数下的候选对数记下来：
n,brutePairs,gridPairs,hits,gridPctOfBrute
100,4950,114,42,2
200,19900,473,181,2
400,79800,1774,682,2
800,319600,7279,2793,2
1600,1279200,29301,10924,2
3200,5118400,117651,43592,2
gridPctOfBrute 一列全是 2——网格的候选对数始终是暴力的约 2%（同机相对量级）。看绝对值更直观：1600 个圆时，暴力要检测 1279200 对，网格只要 29301 对。而且这个比例不随实体数增长：n 从 100 增到 3200，比例稳定在 2%。这说明网格把复杂度从 O(n²) 拉到了近似 O(n)——hits 一列也在增长（真实相交对从 42 涨到 43592），说明点撒得越密相交确实越多，网格并没有「漏掉」这些增长。
网格的两条正确性前提
网格能省检测次数，但它有前提，用错前提就会漏判。脚本里那行 assert cell >= 2 * r 就是前提之一。
第一，cellPx >= 2 * radiusPx。 两个半径 r 的圆，圆心距离必须 <= 2r 才可能相交。若单元边长 cellPx >= 2r，那么「距离 <= 2r」的两个圆心，在网格上的列差与行差都 <= 1——一定落在 3x3 邻域内。反之若 cellPx < 2r，两个相交的圆可能相隔两个单元，3x3 就漏了。配置里 cellPx = 48 = 2 * 24 正好卡在边界上。
第二，只对中心点分桶，且实体大小均匀。 这套实现把每个圆的中心点扔进一个单元，靠的是「所有圆半径相同」这个假设。若实体大小差异很大（一颗小弹珠和一面墙），大实体会跨很多单元，中心点分桶就会漏判，需要改用「实体包围盒覆盖的所有单元」来分桶。小游戏里实体尺寸接近时，中心点分桶性价比最高；尺寸差异大，就要退回包围盒覆盖法。
这两条前提也是「轻量碰撞」的代价：它用假设换性能。假设成立时它又快又对，假设不成立时它会静默漏判——所以第 15 章的端到端回放测试会专门用「网格 vs 暴力对拍」当作回归网。
小结与下一步
这一节把 t1/t2 的碰撞内核写完了：AABB 与圆相交（平方距离、无开方）、按中心点分桶的均匀网格 broad phase、3x3 邻域候选筛选。P 层测试证明网格与暴力求出的相交对完全一致；S 层仿真显示网格候选对数稳定在暴力的约 2%，把复杂度从 O(n²) 拉到近似 O(n)。
碰撞解决的是「碰到了没有」，但小游戏的手感还有另一半：碰到之后怎么动——落地弹多高、速度衰减多快、什么时候停下。下一节就来做这件事：物理手感调参。
阅读导航：上一节：小游戏的物理需求分级 · 下一节：物理手感调参 。
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。