一、游戏背景与算法核心
《合成大西瓜》是一款风靡全球的休闲物理合成游戏。玩家从屏幕顶部投放圆形水果，相同大小的水果碰撞后会合并成更大的水果，最终目标是合成出最大的”西瓜”。看似简单的玩法背后，蕴含着丰富的算法问题：圆形碰撞检测、刚体物理堆叠模拟、合并链式反应以及最优落点决策。
本文将用Java从零实现该游戏的核心算法引擎，重点讲解以下四个技术要点：
- 圆形碰撞检测：基于圆心距与半径和的快速排斥与精确相交判定
- 冲量法碰撞响应：模拟弹性碰撞后的速度分解与位置修正
- 重力堆叠稳定化：迭代松弛算法解决多体穿透与堆叠静止判定
- 贪心落点策略：基于空间利用率与合并概率的最优投放位置计算
二、圆形碰撞检测算法
2.1 算法原理
游戏中所有水果均为圆形刚体，两个圆发生碰撞的充要条件是圆心距小于等于半径之和。设圆A的圆心为 $(x_1, y_1)$、半径为 $r_1$，圆B的圆心为 $(x_2, y_2)$、半径为 $r_2$，则碰撞条件为：
$$\sqrt{(x_1 – x_2)^2 + (y_1 – y_2)^2} \leq r_1 + r_2$$
为避免开方运算，实际代码中比较距离的平方与半径和的平方：
$$dx^2 + dy^2 \leq (r_1 + r_2)^2$$
2.2 Java实现
/**
* 水果圆形刚体类
*/
public class Fruit {
// 水果类型枚举，从0（最小）到10（最大西瓜）
public final int type;
// 圆心坐标
public double x, y;
// 速度向量
public double vx, vy;
// 半径由类型决定
public final double radius;
// 质量与半径平方成正比（假设密度均匀）
public final double mass;
// 是否已合并（防止一帧内多次合并）
public boolean merged = false;
// 各类型水果的半径配置
private static final double[] RADII = {
15.0, 20.0, 25.0, 30.0, 35.0,
40.0, 45.0, 50.0, 55.0, 60.0, 65.0
};
public Fruit(int type, double x, double y) {
this.type = type;
this.x = x;
this.y = y;
this.radius = RADII[type];
this.mass = radius * radius; // 质量 ∝ 面积 ∝ r²
this.vx = 0;
this.vy = 0;
}
/**
* 检测与另一个水果是否发生碰撞
* 使用平方距离避免开方运算，时间复杂度 O(1)
*/
public boolean collidesWith(Fruit other) {
double dx = this.x - other.x;
double dy = this.y - other.y;
double distSq = dx * dx + dy * dy;
double radiusSum = this.radius + other.radius;
return distSq <= radiusSum * radiusSum;
}
/**
* 计算碰撞深度（穿透量），用于位置修正
*/
public double penetrationDepth(Fruit other) {
double dx = this.x - other.x;
double dy = this.y - other.y;
double dist = Math.sqrt(dx * dx + dy * dy);
double radiusSum = this.radius + other.radius;
// 若已穿透，返回穿透深度；否则返回0
return dist < radiusSum ? radiusSum - dist : 0;
}
}
三、冲量法碰撞响应
3.1 物理模型
当两个圆形水果碰撞后，需要根据动量守恒与能量守恒（近似弹性碰撞）计算碰撞后的速度。将速度分解为沿碰撞法线方向与切线方向：
- 法线方向（两圆心连线方向）发生速度交换与反弹
- 切线方向速度保持不变（忽略摩擦力简化模型）
恢复系数 $e \in [0,1]$ 控制碰撞弹性程度，$e=1$ 为完全弹性，$e=0$ 为完全非弹性。
3.2 Java实现
public class PhysicsEngine {
// 重力加速度（像素/帧²）
private static final double GRAVITY = 0.5;
// 恢复系数
private static final double RESTITUTION = 0.3;
// 地面反弹系数
private static final double GROUND_BOUNCE = 0.2;
// 迭代次数（用于堆叠稳定化）
private static final int SOLVER_ITERATIONS = 8;
/**
* 处理一对水果的碰撞响应
* @return 若发生了有效碰撞返回true
*/
public boolean resolveCollision(Fruit a, Fruit b) {
double dx = b.x - a.x;
double dy = b.y - a.y;
double distSq = dx * dx + dy * dy;
double radiusSum = a.radius + b.radius;
// 快速排斥：若距离平方大于半径和平方，未碰撞
if (distSq > radiusSum * radiusSum || distSq == 0) {
return false;
}
double dist = Math.sqrt(distSq);
// 碰撞法线单位向量（从a指向b）
double nx = dx / dist;
double ny = dy / dist;
// --- 位置修正：将两圆沿法线方向推开，消除穿透 ---
double penetration = radiusSum - dist;
// 按质量反比分配修正量（轻物体推得多）
double totalMass = a.mass + b.mass;
double percent = 0.8; // 修正比例，防止过度修正导致抖动
double correction = penetration / totalMass * percent;
a.x -= nx * correction * b.mass;
a.y -= ny * correction * b.mass;
b.x += nx * correction * a.mass;
b.y += ny * correction * a.mass;
// --- 速度响应：沿法线方向交换动量 ---
// 相对速度在法线方向的分量
double dvx = b.vx - a.vx;
double dvy = b.vy - a.vy;
double velAlongNormal = dvx * nx + dvy * ny;
// 若相对速度沿法线方向分离，说明正在分开，无需处理
if (velAlongNormal > 0) {
return true;
}
// 冲量大小计算（一维弹性碰撞公式推广）
double j = -(1 + RESTITUTION) * velAlongNormal;
j /= (1 / a.mass + 1 / b.mass);
// 应用冲量
double impulseX = j * nx;
double impulseY = j * ny;
a.vx -= impulseX / a.mass;
a.vy -= impulseY / a.mass;
b.vx += impulseX / b.mass;
b.vy += impulseY / b.mass;
return true;
}
/**
* 处理水果与地面的碰撞
*/
public void resolveGroundCollision(Fruit fruit, double groundY) {
if (fruit.y + fruit.radius > groundY) {
// 位置修正：将水果置于地面之上
fruit.y = groundY - fruit.radius;
// 速度反向并衰减
fruit.vy = -fruit.vy * GROUND_BOUNCE;
// 切向摩擦力（简化处理：直接衰减水平速度）
fruit.vx *= 0.95;
}
}
/**
* 处理水果与侧壁的碰撞
*/
public void resolveWallCollision(Fruit fruit, double leftWall, double rightWall) {
if (fruit.x - fruit.radius < leftWall) {
fruit.x = leftWall + fruit.radius;
fruit.vx = -fruit.vx * GROUND_BOUNCE;
} else if (fruit.x + fruit.radius > rightWall) {
fruit.x = rightWall - fruit.radius;
fruit.vx = -fruit.vx * GROUND_BOUNCE;
}
}
}
四、重力堆叠与多体稳定化
4.1 算法挑战
当多个水果堆叠在一起时，简单的两两碰撞处理会导致穿透累积与抖动现象。例如底层水果受重力下压，但由于与上层水果的碰撞响应被推回，形成震荡。
解决方案采用迭代松弛法：每帧进行多轮（通常6-10轮）位置与速度修正，逐步消除穿透，使堆叠趋于稳定。
4.2 Java实现
public class GameWorld {
private final List<Fruit> fruits = new ArrayList<>();
private final PhysicsEngine physics = new PhysicsEngine();
private final double width = 400;
private final double height = 600;
private final double groundY = height - 10;
private final double leftWall = 10;
private final double rightWall = width - 10;
/**
* 物理模拟主循环，每帧调用一次
*/
public void step() {
// Step 1: 施加重力，更新速度
for (Fruit f : fruits) {
if (!f.merged) {
f.vy += PhysicsEngine.GRAVITY;
}
}
// Step 2: 迭代求解碰撞（多轮松弛以稳定堆叠）
for (int iter = 0; iter < PhysicsEngine.SOLVER_ITERATIONS; iter++) {
for (int i = 0; i < fruits.size(); i++) {
Fruit a = fruits.get(i);
if (a.merged) continue;
for (int j = i + 1; j < fruits.size(); j++) {
Fruit b = fruits.get(j);
if (b.merged) continue;
physics.resolveCollision(a, b);
}
// 边界碰撞也在每轮迭代中处理
physics.resolveGroundCollision(a, groundY);
physics.resolveWallCollision(a, leftWall, rightWall);
}
}
// Step 3: 更新位置（欧拉积分）
for (Fruit f : fruits) {
if (!f.merged) {
f.x += f.vx;
f.y += f.vy;
// 阻尼衰减，防止无限震荡
f.vx *= 0.99;
f.vy *= 0.99;
}
}
// Step 4: 检测并处理合并（链式反应）
processMerges();
// Step 5: 清理已合并的水果
fruits.removeIf(f -> f.merged);
}
/**
* 投放新水果到指定x坐标
*/
public void dropFruit(int type, double dropX) {
fruits.add(new Fruit(type, dropX, 30));
}
}
五、合并链式反应算法
5.1 算法原理
当两个相同类型的水果碰撞时，它们合并成一个更高级别的水果。合并后新水果的位置取两者的质量加权中心，速度取动量守恒后的合成速度。新水果的诞生可能立即与周围同类型水果再次碰撞，引发链式反应。
处理策略：每帧物理模拟结束后，扫描所有碰撞对，收集待合并组，按从大到小的顺序依次执行合并，避免一帧内重复处理。
5.2 Java实现
public class GameWorld {
// ... 前文代码 ...
/**
* 处理所有合并，支持链式反应
* 使用BFS思想：先找出所有待合并对，再按层级顺序执行
*/
private void processMerges() {
boolean hasMerge;
// 循环处理直到没有新的合并发生（链式反应）
do {
hasMerge = false;
Set<String> processedPairs = new HashSet<>();
for (int i = 0; i < fruits.size(); i++) {
Fruit a = fruits.get(i);
if (a.merged || a.type >= 10) continue; // 最大类型不合并
for (int j = i + 1; j < fruits.size(); j++) {
Fruit b = fruits.get(j);
if (b.merged || b.type != a.type) continue;
// 唯一标识防止重复处理
String pairId = Math.min(i, j) + "-" + Math.max(i, j);
if (processedPairs.contains(pairId)) continue;
// 检测碰撞
if (a.collidesWith(b)) {
performMerge(a, b);
processedPairs.add(pairId);
hasMerge = true;
break; // a已合并，跳到下一个i
}
}
}
} while (hasMerge);
}
/**
* 执行两个水果的合并
* 新水果位置 = 质量加权中心
* 新水果速度 = 动量守恒合成速度
*/
private void performMerge(Fruit a, Fruit b) {
// 质量加权中心作为新位置
double totalMass = a.mass + b.mass;
double newX = (a.x * a.mass + b.x * b.mass) / totalMass;
double newY = (a.y * a.mass + b.y * b.mass) / totalMass;
// 动量守恒计算新速度
double newVx = (a.vx * a.mass + b.vx * b.mass) / totalMass;
double newVy = (a.vy * a.mass + b.vy * b.mass) / totalMass;
// 标记旧水果为已合并
a.merged = true;
b.merged = true;
// 生成更高级别的新水果
Fruit newFruit = new Fruit(a.type + 1, newX, newY);
newFruit.vx = newVx;
newFruit.vy = newVy;
fruits.add(newFruit);
// 触发合并特效/得分（此处省略UI代码）
System.out.println("合并触发: " + a.type + " + " + b.type + " -> " + newFruit.type);
}
}
六、贪心最优落点策略
6.1 策略设计
AI自动玩《合成大西瓜》时，需要为每一轮待投放的水果选择一个最佳水平位置。核心评估指标包括：
- 落地高度最大化：优先放在较低位置，为后续水果留出空间
- 同类型邻接概率：放在已有相同类型水果附近，促进合并
- 堆叠稳定性：避免造成单柱过高导致提前溢出
- 中心聚拢倾向：向中间靠拢，减少边缘浪费
综合以上指标，设计如下贪心评分函数：
$$Score(x) = w_1 \cdot \text{落地高度} + w_2 \cdot \text{同类邻接奖励} + w_3 \cdot \text{中心距离惩罚} + w_4 \cdot \text{地形平整度}$$
6.2 Java实现
public class GreedyDropStrategy {
// 评分权重
private static final double W_HEIGHT = 1.0; // 落地高度奖励（越低越好，取负值）
private static final double W_ADJACENT = 50.0; // 同类邻接奖励
private static final double W_CENTER = -0.1; // 中心距离惩罚
private static final double W_FLAT = 10.0; // 地形平整度奖励
private final GameWorld world;
private final double worldWidth;
public GreedyDropStrategy(GameWorld world, double worldWidth) {
this.world = world;
this.worldWidth = worldWidth;
}
/**
* 计算最佳投放位置
* @param fruitType 待投放的水果类型
* @return 最佳x坐标
*/
public double findBestDropX(int fruitType) {
double bestX = worldWidth / 2;
double bestScore = Double.NEGATIVE_INFINITY;
// 在有效范围内离散采样候选位置
double radius = getRadiusByType(fruitType);
double step = 5.0;
double startX = radius + 10;
double endX = worldWidth - radius - 10;
for (double x = startX; x <= endX; x += step) {
double score = evaluateDropPosition(x, fruitType);
if (score > bestScore) {
bestScore = score;
bestX = x;
}
}
return bestX;
}
/**
* 评估在指定x坐标投放水果的得分
*/
private double evaluateDropPosition(double dropX, int fruitType) {
double score = 0;
List<Fruit> fruits = world.getFruits();
// 1. 计算该x坐标下方的"地面高度"（即水果会落到多高）
double groundHeight = simulateLandingHeight(dropX, fruitType, fruits);
score += W_HEIGHT * (world.getHeight() - groundHeight); // 越低得分越高
// 2. 同类邻接奖励：统计该位置附近已有同类型水果的数量
int adjacentSameType = countAdjacentSameType(dropX, fruitType, fruits);
score += W_ADJACENT * adjacentSameType;
// 3. 中心距离惩罚
double centerDist = Math.abs(dropX - worldWidth / 2);
score += W_CENTER * centerDist;
// 4. 地形平整度：若左右邻近x位置高度相近，奖励平整
double leftHeight = simulateLandingHeight(dropX - 20, fruitType, fruits);
double rightHeight = simulateLandingHeight(dropX + 20, fruitType, fruits);
double flatness = -Math.abs(leftHeight - rightHeight);
score += W_FLAT * flatness;
return score;
}
/**
* 模拟投放水果后的落地高度
* 简化模型：从顶部垂直下落，找到第一个阻挡的圆形或地面
*/
private double simulateLandingHeight(double dropX, int fruitType, List<Fruit> fruits) {
double radius = getRadiusByType(fruitType);
double maxY = world.getGroundY() - radius; // 默认落到地面
for (Fruit f : fruits) {
if (f.merged) continue;
// 水平范围是否重叠
double horizontalDist = Math.abs(dropX - f.x);
if (horizontalDist < radius + f.radius) {
// 垂直方向：新水果底部刚好接触该水果顶部
double landingY = f.y - f.radius - radius;
if (landingY < maxY) {
maxY = landingY;
}
}
}
return maxY;
}
/**
* 统计指定位置附近同类型水果数量
*/
private int countAdjacentSameType(double dropX, int fruitType, List<Fruit> fruits) {
int count = 0;
double radius = getRadiusByType(fruitType);
double searchRadius = radius * 4; // 搜索范围
for (Fruit f : fruits) {
if (f.merged || f.type != fruitType) continue;
double dx = dropX - f.x;
double dy = 0; // 忽略垂直差异，仅看水平邻接潜力
if (Math.sqrt(dx * dx + dy * dy) < searchRadius) {
count++;
}
}
return count;
}
private double getRadiusByType(int type) {
double[] radii = {15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65};
return radii[Math.min(type, radii.length - 1)];
}
}
七、完整运行示例
public class SuikaGameDemo {
public static void main(String[] args) {
GameWorld world = new GameWorld();
GreedyDropStrategy ai = new GreedyDropStrategy(world, 400);
// 模拟AI自动游玩50步
Random rand = new Random(42);
for (int step = 0; step < 50; step++) {
// 随机生成待投放的水果类型（小水果概率更高）
int nextType = rand.nextInt(5); // 0~4
double bestX = ai.findBestDropX(nextType);
world.dropFruit(nextType, bestX);
// 物理模拟5帧，让水果落稳
for (int f = 0; f < 5; f++) {
world.step();
}
System.out.printf("Step %d: 投放类型%d 到 x=%.1f, 当前水果数=%d%n",
step, nextType, bestX, world.getFruitCount());
}
System.out.println("\n游戏结束，最终水果统计:");
world.printFruitStats();
}
}
八、复杂度分析
| 模块 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 碰撞检测 | $O(n^2)$ | $O(1)$ | 每帧遍历所有水果对，$n$为当前水果数量 |
| 冲量响应 | $O(1)$ | $O(1)$ | 单对碰撞的数学运算 |
| 迭代松弛 | $O(k \cdot n^2)$ | $O(1)$ | $k$为迭代轮数（通常6-10） |
| 合并处理 | $O(n^2)$ | $O(n)$ | 最坏情况下每帧触发链式合并 |
| 贪心落点 | $O(m \cdot n)$ | $O(1)$ | $m$为采样点数（约80） |
优化建议：当水果数量超过50时，可采用均匀空间网格（Uniform Grid）将碰撞检测优化至近似 $O(n)$；对于落点评估，可使用空间划分树（如四叉树）加速近邻查询。
九、总结
本文以《合成大西瓜》为载体，系统讲解了圆形刚体物理引擎的四大核心算法：
- 碰撞检测利用平方距离比较实现 $O(1)$ 判定
- 冲量响应基于动量守恒将速度分解为法线与切线分量处理
- 迭代松弛通过多轮位置修正解决堆叠穿透与抖动
- 贪心策略综合落地高度、同类邻接与平整度指标自动决策
读者可在此基础上扩展：引入四叉树空间划分优化大规模碰撞检测、使用蒙特卡洛模拟评估多步落点收益、或训练神经网络学习更高级的布局策略。
