粘粘世界（World of Goo）的核心玩法看似搭建，实质是在做一场连续介质力学计算：一堆有质量的粘性小球通过”粘性连杆”连接，玩家不断加高结构，让它跨越沟壑、顶住风阻、从高处垂下而不塌。判定标准很简单——只要有一根连杆承受的拉力超过粘性极限，整座塔就开始连锁崩溃。
这篇文章用纯 Java 把这套机制从零实现，重点不在画图，而在两件事：一是用 Verlet 积分 + 距离约束求解器（Position Based Dynamics）计算每根连杆的受力，二是用图论的连通性与最小生成结构判定”结构是否还撑得住”。
一、问题抽象：从游戏画面到力学模型
把每个粘豆包（Goo Ball）抽象成一个质点 p = (x, y, m)，把一根粘性连杆抽象成一根理想无质量弹簧，刚度 k、自然长度 L。整座结构就是一个带结构的无向图 G=(V, E)，其中同一条连杆两端的引力相互抵消，因此可以用迭代求解器快速收敛。
游戏里的关键约束有三条：
| 约束 | 物理含义 | 算法后果 |
|---|---|---|
| 最大拉伸比 | 连杆不能被拉长超过自身长度的 2 倍 | 硬约束，超限即断裂 |
| 最大压力比 | 连杆被压缩到 0.5 倍以下时就失去刚性 | 软约束，仅提示 |
| 锚点固定 | 顶部或底部的结构附着在静态物上 | 位移为 0，作为边界条件 |
真正会打断结构的只有第一条：拉伸比超过阈值。因此”断裂”是离散事件，”变形”是连续过程，两者必须分开处理。
二、核心算法一：Position Based Dynamics 求解约束
传统弹簧系统要用显式欧拉 + 阻尼，稍有不稳就爆炸。PBD 的做法是把动力学拆成两步：先积分预测，再投影约束。
积分部分采用 Verlet 形式，不需要显式保存速度：
x' = 2x - x_prev + a * dt^2
约束投影部分对每根连杆反复迭代：如果当前长度偏离自然长度，就把两端质点沿连线方向各移动一半（按质量反比分配）。
public final class Vec2 {
public double x, y;
public Vec2(double x, double y) { this.x = x; this.y = y; }
public Vec2 add(Vec2 o) { return new Vec2(x + o.x, y + o.y); }
public Vec2 sub(Vec2 o) { return new Vec2(x - o.x, y - o.y); }
public Vec2 mul(double s) { return new Vec2(x * s, y * s); }
public double len() { return Math.sqrt(x * x + y * y); }
public Vec2 norm() {
double l = len();
return l < 1e-12 ? new Vec2(0, 0) : new Vec2(x / l, y / l);
}
public double dot(Vec2 o) { return x * o.x + y * o.y; }
}
public final class GooBall {
public Vec2 pos; // 当前位置
public Vec2 prev; // 上一帧位置（Verlet）
public Vec2 force; // 累积外力
public double mass; // 质量
public double invMass; // 质量倒数，静止锚点为 0
public boolean anchored;
public GooBall(Vec2 p, double m, boolean anchored) {
this.pos = p;
this.prev = new Vec2(p.x, p.y);
this.force = new Vec2(0, 0);
this.mass = m;
this.anchored = anchored;
this.invMass = anchored ? 0.0 : 1.0 / m;
}
}
连杆负责记录自然长度与当前拉伸比，断裂判定就放在这里：
public final class ViscousLink {
public final GooBall a, b;
public final double restLength;
public double stretchRatio = 1.0; // 当前长度 / 自然长度
public boolean broken = false;
public static final double MAX_STRETCH = 2.0; // 拉伸 2 倍即断裂
public static final double TEAR_STIFFNESS = 0.9; // 约束收敛强度
public ViscousLink(GooBall a, GooBall b) {
this.a = a;
this.b = b;
this.restLength = a.pos.sub(b.pos).len();
}
/** 约束投影：把两端拉回自然长度附近，并按逆质量分配位移 */
public void solve() {
if (broken) return;
Vec2 d = b.pos.sub(a.pos);
double cur = d.len();
if (cur < 1e-9) return;
stretchRatio = cur / restLength;
if (stretchRatio > MAX_STRETCH) { // 拉力超限，直接断开
broken = true;
return;
}
double w = a.invMass + b.invMass;
if (w < 1e-12) return; // 两端都固定，无法调整
// 目标长度 = 自然长度，误差按逆质量比例分配
double correction = (cur - restLength) / cur * TEAR_STIFFNESS;
Vec2 n = d.mul(correction);
a.pos = a.pos.add(n.mul(a.invMass / w));
b.pos = b.pos.sub(n.mul(b.invMass / w));
}
}
迭代求解器把”重力积分”与”约束投影”分开，迭代次数是精度与性能的旋钮：
public final class PbdSolver {
private final java.util.List<GooBall> balls;
private final java.util.List<ViscousLink> links;
private final Vec2 gravity = new Vec2(0, 980); // 像素/秒^2
private static final double DAMPING = 0.98;
public PbdSolver(java.util.List<GooBall> b, java.util.List<ViscousLink> l) {
this.balls = b;
this.links = l;
}
public void step(double dt, int iterations) {
// 1) Verlet 积分：位置由历史位置与外力共同决定
for (GooBall g : balls) {
if (g.anchored) continue;
Vec2 vel = g.pos.sub(g.prev).mul(DAMPING);
Vec2 acc = g.force.mul(g.invMass).add(gravity);
Vec2 next = g.pos.add(vel).add(acc.mul(dt * dt));
g.prev = g.pos;
g.pos = next;
g.force = new Vec2(0, 0);
}
// 2) 多轮约束投影：迭代越多次，连杆越"硬"
for (int it = 0; it < iterations; it++) {
for (ViscousLink lk : links) lk.solve();
}
// 3) 碰撞兜底：不允许穿透地面
for (GooBall g : balls) {
if (g.pos.y > GameWorld.GROUND_Y) g.pos.y = GameWorld.GROUND_Y;
}
}
}
这里有一个容易踩的坑：TEAR_STIFFNESS 取 1.0 会导致约束过冲抖动，取太小则结构像橡皮筋一样软塌。工程实践中 0.8~0.95 是比较稳的区间；同时迭代次数 8~16 次即可在 60fps 下保持稳定。
三、核心算法二：并查集判定结构连通性
断裂发生后，”整座塔是否还连着锚点”才是玩家最关心的问题。这正是一个动态连通性问题，用并查集（Union-Find）在近 O(1) 时间内回答。
public final class DisjointSet {
private final int[] parent;
private final int[] rank;
public DisjointSet(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
}
public int find(int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]]; // 路径压缩（隔代压缩）
x = parent[x];
}
return x;
}
public boolean union(int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) return false;
if (rank[ra] < rank[rb]) { int t = ra; ra = rb; rb = t; }
parent[rb] = ra;
if (rank[ra] == rank[rb]) rank[ra]++;
return true;
}
}
每帧重建一次（V+E 规模，代价可接受），然后检查锚点所在集合是否覆盖了关键支点：
public final class StructureAnalyzer {
/** 返回仍然与锚点连通的小球数量；同时标记出悬空的残骸 */
public static int countConnected(java.util.List<GooBall> balls,
java.util.List<ViscousLink> links) {
int n = balls.size();
DisjointSet ds = new DisjointSet(n);
for (ViscousLink lk : links) {
if (lk.broken) continue;
ds.union(balls.indexOf(lk.a), balls.indexOf(lk.b));
}
// 找到任意锚点作为连通性基准
int root = -1;
for (int i = 0; i < n; i++) {
if (balls.get(i).anchored) { root = ds.find(i); break; }
}
if (root == -1) return n; // 无锚点的自由结构
int cnt = 0;
for (int i = 0; i < n; i++) {
if (ds.find(i) == root) cnt++;
}
return cnt;
}
}
balls.indexOf(lk.a) 是 O(V)，整体退化为 O(E·V)。生产代码应事先在 GooBall 里存索引（或直接用哈希表映射对象到下标），这样每帧重建才真正是 O(E α(V))。
四、核心算法三：基于受力的最小支撑结构分析
仅有连通性还不够——粘粘世界的难点是”结构连着，但中间那根连杆已经被拉到 1.9 倍，随时会断”。因此需要提前预测哪根连杆最危险。
对每根连杆计算相对拉伸裕度 slack = (MAX_STRETCH - stretchRatio) / MAX_STRETCH，再做一次最小生成树式的关键连杆识别：
public final class CriticalLinkFinder {
/** 用 Kruskal 的思路：按裕度升序把连杆加入，第一条使图成环的即冗余，反之是割边候选 */
public static java.util.List<ViscousLink> findBridges(
java.util.List<GooBall> balls, java.util.List<ViscousLink> links) {
int n = balls.size();
java.util.Map<GooBall, Integer> idx = new java.util.HashMap<>();
for (int i = 0; i < n; i++) idx.put(balls.get(i), i);
// 按危险程度从高到低排序：裕度最小的先处理
java.util.List<ViscousLink> sorted = new java.util.ArrayList<>(links);
sorted.sort((x, y) -> Double.compare(slack(x), slack(y)));
DisjointSet ds = new DisjointSet(n);
java.util.List<ViscousLink> critical = new java.util.ArrayList<>();
java.util.Set<ViscousLink> removed = new java.util.HashSet<>();
// Tarjan 桥检测的等价简化：逐条移除试探连通性
for (ViscousLink target : sorted) {
if (target.broken || removed.contains(target)) continue;
DisjointSet probe = new DisjointSet(n);
for (ViscousLink lk : sorted) {
if (lk == target || lk.broken || removed.contains(lk)) continue;
probe.union(idx.get(lk.a), idx.get(lk.b));
}
if (!probe.union(idx.get(target.a), idx.get(target.b))) {
// 移除后仍连通 => 冗余连杆，可以安全忽略
removed.add(target);
} else {
critical.add(target); // 割边：断了就分裂
}
}
return critical;
}
private static double slack(ViscousLink lk) {
return (ViscousLink.MAX_STRETCH - lk.stretchRatio) / ViscousLink.MAX_STRETCH;
}
}
这段”逐条移除 + 并查集探连通”的写法对 E 较小的场景（粘粘世界单关通常几十根连杆）非常实用，最坏 O(E² α(V))，但工程上完全可以按优先级只检查前 K 根，把复杂度压到 O(K·E α(V))。
真正实现 Tarjan 桥检测可以做到 O(V+E)，思路是维护 dfn/low，但因为我们还需要”按危险度排序”的语义，逐条试探反而更贴近游戏需求。
五、组装：一关的完整主循环
把三块拼起来，得到一个可以跑起来的最小关卡：底部一段固定锚点，玩家不断往上加球，结构过重就垮。
public final class GameWorld {
public static final double GROUND_Y = 600;
public static void main(String[] args) {
java.util.List<GooBall> balls = new java.util.ArrayList<>();
java.util.List<ViscousLink> links = new java.util.ArrayList<>();
// 锚点：地面上的固定球
GooBall a1 = new GooBall(new Vec2(200, GROUND_Y), 1.0, true);
GooBall a2 = new GooBall(new Vec2(260, GROUND_Y), 1.0, true);
balls.add(a1); balls.add(a2);
links.add(new ViscousLink(a1, a2));
// 逐层加高，每加一个球连两根杆（形成三角形，结构最稳）
GooBall prevA = a1, prevB = a2;
for (int level = 1; level <= 6; level++) {
GooBall left = new GooBall(new Vec2(200 - level * 10, GROUND_Y - level * 50), 1.5, false);
GooBall right = new GooBall(new Vec2(260 + level * 10, GROUND_Y - level * 50), 1.5, false);
balls.add(left); balls.add(right);
links.add(new ViscousLink(prevA, left));
links.add(new ViscousLink(prevB, right));
links.add(new ViscousLink(left, right)); // 横撑：抗剪
prevA = left; prevB = right;
}
PbdSolver solver = new PbdSolver(balls, links);
double dt = 1.0 / 60;
for (int frame = 0; frame < 600; frame++) {
solver.step(dt, 12);
int alive = StructureAnalyzer.countConnected(balls, links);
if (frame % 60 == 0) {
java.util.List<ViscousLink> critical =
CriticalLinkFinder.findBridges(balls, links);
System.out.printf("帧 %d：连通球数 %d，关键连杆 %d，最长拉伸 %.2f%n",
frame, alive, critical.size(), maxStretch(links));
}
if (alive < balls.size() / 2) {
System.out.println("结构崩解，关卡失败");
break;
}
}
}
private static double maxStretch(java.util.List<ViscousLink> links) {
double m = 0;
for (ViscousLink lk : links) if (!lk.broken) m = Math.max(m, lk.stretchRatio);
return m;
}
}
三角形横撑不是装饰——它让结构从”链式结构”变成”刚性桁架”，重心偏移时由剪切力分摊，这是粘粘世界高手搭塔的共同直觉。算法上，它带来的效果是一根连杆断掉后仍能保持连通，即结构冗余度提升。
六、复杂度与调优
| 环节 | 复杂度 | 说明 |
|---|---|---|
| Verlet 积分 | O(V) | 每帧一次 |
| 约束投影 | O(it · E) | it 为迭代次数（8~16） |
| 并查集连通性 | O(E α(V)) | 路径压缩 + 按秩合并 |
| 关键连杆识别 | O(E² α(V)) 或被 K 截断 | 单关规模足够 |
几个实操建议：
- dt 固定为 1/60，并与渲染帧分离，用累加器做定步长。变步长会让 Verlet 的稳定性彻底失效。
- 质量差不要超过 10 倍。逆质量差距过大时，约束投影会把位移几乎全部分配给轻的一端，导致视觉上的”甩动”。
- 断裂要做滞后处理：拉伸比超过 2.0 只标记
pendingBreak，连续 2~3 帧都超限才真正断，避免单帧数值抖动误判。 - 迭代次数自适应：结构规模大时降到 8 次，小关卡升到 16 次，帧率优先。
粘粘世界最迷人的地方在于它把”结构力学”包装成了拖拽游戏：玩家并不计算应力，但每次失败都在学习”三角形比四边形稳、长悬臂必垮、锚点要分散”。当这套直觉被翻译成 PBD 约束投影 + 并查集连通性 + 割边识别，一座塔的生死就从手感变成了可复现的计算。
