合成大西瓜是一款极具上瘾性的休闲益智游戏，玩家通过控制水果的下落位置，使相同水果碰撞合并成更大一级的水果，最终目标是合成大西瓜。本文将用Java完整实现该游戏的核心算法，重点讲解圆形物体的碰撞检测、弹性碰撞响应以及贪心合并策略。
一、游戏机制与算法分析
游戏的核心机制可以分解为以下几个算法问题：
- 圆形碰撞检测：判断两个圆形水果是否接触或重叠
- 碰撞响应：处理碰撞后的速度变化与位置修正
- 合并判定：相同等级水果碰撞后触发合并逻辑
- 贪心放置策略：AI自动选择最优下落位置
二、圆形碰撞检测算法
圆形碰撞检测是最基础也是最核心的算法。对于两个圆心分别为 $(x_1, y_1)$、$(x_2, y_2)$，半径分别为 $r_1$、$r_2$ 的圆，当圆心距离小于等于半径之和时即发生碰撞：
$$d = \sqrt{(x_1 – x_2)^2 + (y_1 – y_2)^2} \leq r_1 + r_2$$
为提高性能，避免开方运算，可比较距离的平方：
$$(x_1 – x_2)^2 + (y_1 – y_2)^2 \leq (r_1 + r_2)^2$$
三、Java完整实现
import java.util.*;
import java.awt.*;
/**
* 合成大西瓜游戏核心算法实现
* 包含物理碰撞检测、弹性碰撞响应、合并逻辑与贪心AI策略
*/
public class MergeWatermelon {
// 水果等级配置：索引对应等级，值对应半径(像素)
private static final double[] FRUIT_RADIUS = {
10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60
};
// 水果名称
private static final String[] FRUIT_NAMES = {
"葡萄", "樱桃", "橘子", "柠檬", "猕猴桃", "番茄", "桃子", "菠萝", "椰子", "半个西瓜", "大西瓜"
};
// 游戏场景宽度与高度
private static final double WIDTH = 400;
private static final double HEIGHT = 600;
private static final double GRAVITY = 0.3; // 重力加速度
private static final double FRICTION = 0.98; // 速度衰减系数
private static final double BOUNCE = 0.6; // 反弹系数
private List<Fruit> fruits = new ArrayList<>();
private Random random = new Random();
/**
* 水果实体类，包含位置、速度、等级等属性
*/
static class Fruit {
double x, y; // 圆心坐标
double vx, vy; // 速度向量
int level; // 水果等级 0-10
double radius; // 当前半径
boolean merged; // 是否已合并（标记删除）
Fruit(double x, double y, int level) {
this.x = x;
this.y = y;
this.level = level;
this.radius = FRUIT_RADIUS[level];
this.vx = 0;
this.vy = 0;
this.merged = false;
}
/**
* 更新位置与速度，应用重力与边界碰撞
*/
void update() {
vy += GRAVITY; // 应用重力
x += vx;
y += vy;
vx *= FRICTION; // 空气阻力
vy *= FRICTION;
// 边界碰撞检测：左右墙壁
if (x - radius < 0) {
x = radius;
vx = -vx * BOUNCE;
} else if (x + radius > WIDTH) {
x = WIDTH - radius;
vx = -vx * BOUNCE;
}
// 边界碰撞检测：底部地面
if (y + radius > HEIGHT) {
y = HEIGHT - radius;
vy = -vy * BOUNCE;
vx *= 0.9; // 地面摩擦
}
}
@Override
public String toString() {
return String.format("%s(level=%d, x=%.1f, y=%.1f)",
FRUIT_NAMES[level], level, x, y);
}
}
/**
* 检测两个水果是否发生碰撞
* 使用平方距离避免开方运算，提升性能
*/
boolean checkCollision(Fruit a, Fruit b) {
double dx = a.x - b.x;
double dy = a.y - b.y;
double distSq = dx * dx + dy * dy;
double radiusSum = a.radius + b.radius;
return distSq <= radiusSum * radiusSum;
}
/**
* 计算两个水果碰撞后的弹性响应
* 基于动量守恒与能量守恒的简化模型
*/
void resolveCollision(Fruit a, Fruit b) {
double dx = b.x - a.x;
double dy = b.y - a.y;
double dist = Math.sqrt(dx * dx + dy * dy);
if (dist == 0) {
// 防止除零，随机偏移
dx = 0.01;
dist = 0.01;
}
// 归一化碰撞法向量
double nx = dx / dist;
double ny = dy / dist;
// 相对速度在法向量上的投影
double dvx = a.vx - b.vx;
double dvy = a.vy - b.vy;
double velAlongNormal = dvx * nx + dvy * ny;
// 若速度分离，无需处理
if (velAlongNormal > 0) return;
// 弹性碰撞公式：简化假设质量与半径成正比
double massA = a.radius * a.radius; // 面积近似质量
double massB = b.radius * b.radius;
double restitution = 0.5; // 恢复系数
double j = -(1 + restitution) * velAlongNormal;
j /= (1 / massA + 1 / massB);
// 应用冲量
double impulseX = j * nx;
double impulseY = j * ny;
a.vx += impulseX / massA;
a.vy += impulseY / massA;
b.vx -= impulseX / massB;
b.vy -= impulseY / massB;
// 位置修正：防止重叠穿透
double overlap = (a.radius + b.radius - dist) / 2.0;
a.x -= nx * overlap;
a.y -= ny * overlap;
b.x += nx * overlap;
b.y += ny * overlap;
}
/**
* 合并相同等级的水果
* 返回新生成的高一级水果，若无法合并返回null
*/
Fruit tryMerge(Fruit a, Fruit b) {
if (a.level != b.level || a.merged || b.merged) {
return null;
}
if (a.level >= FRUIT_RADIUS.length - 1) {
return null; // 已是大西瓜，无法继续合并
}
a.merged = true;
b.merged = true;
// 新水果位于两果中心，继承部分动量
double newX = (a.x + b.x) / 2;
double newY = (a.y + b.y) / 2;
Fruit merged = new Fruit(newX, newY, a.level + 1);
merged.vx = (a.vx + b.vx) / 2 * 0.8;
merged.vy = (a.vy + b.vy) / 2 * 0.8;
return merged;
}
/**
* 单帧物理更新：更新位置、检测碰撞、处理合并
*/
void updatePhysics() {
// 1. 更新所有水果位置
for (Fruit f : fruits) {
f.update();
}
// 2. 迭代处理碰撞与合并（多轮迭代提高稳定性）
for (int iter = 0; iter < 3; iter++) {
List<Fruit> newFruits = new ArrayList<>();
// 两两检测碰撞
for (int i = 0; i < fruits.size(); i++) {
for (int j = i + 1; j < fruits.size(); j++) {
Fruit a = fruits.get(i);
Fruit b = fruits.get(j);
if (a.merged || b.merged) continue;
if (checkCollision(a, b)) {
// 先尝试合并
Fruit merged = tryMerge(a, b);
if (merged != null) {
newFruits.add(merged);
} else {
// 不同等级则弹性碰撞
resolveCollision(a, b);
}
}
}
}
// 移除已合并的水果并添加新水果
fruits.removeIf(f -> f.merged);
fruits.addAll(newFruits);
}
}
/**
* 贪心策略：选择最佳下落位置
* 评估指标：与最近同级水果的距离 + 下方支撑稳定性
*/
double findBestDropPosition(int level) {
double bestX = WIDTH / 2;
double bestScore = Double.NEGATIVE_INFINITY;
double step = 5.0; // 搜索步长
for (double x = FRUIT_RADIUS[level]; x <= WIDTH - FRUIT_RADIUS[level]; x += step) {
double score = evaluateDropPosition(x, level);
if (score > bestScore) {
bestScore = score;
bestX = x;
}
}
return bestX;
}
/**
* 评估某一下落位置的得分
* 核心启发式：优先落在同级水果附近，同时保证底部有支撑
*/
double evaluateDropPosition(double x, int level) {
double score = 0;
double dropY = FRUIT_RADIUS[level]; // 假设从顶部释放
// 1. 寻找最近的同级水果，距离越近得分越高
double minSameLevelDist = Double.MAX_VALUE;
for (Fruit f : fruits) {
if (f.level == level) {
double dist = Math.abs(f.x - x);
if (dist < minSameLevelDist) {
minSameLevelDist = dist;
}
}
}
if (minSameLevelDist != Double.MAX_VALUE) {
// 距离在3倍半径内给予正分，越近越好
score += Math.max(0, 100 - minSameLevelDist);
}
// 2. 下方是否有支撑水果，避免悬空浪费
boolean hasSupport = false;
for (Fruit f : fruits) {
if (Math.abs(f.x - x) < f.radius + FRUIT_RADIUS[level] &&
f.y > dropY) {
hasSupport = true;
break;
}
}
if (hasSupport) {
score += 50;
}
// 3. 惩罚靠近边缘的位置（容易卡住）
double edgeDist = Math.min(x, WIDTH - x);
score += edgeDist * 0.1;
return score;
}
/**
* 添加新水果到场景中
*/
void spawnFruit(double x, int level) {
double y = FRUIT_RADIUS[level];
fruits.add(new Fruit(x, y, level));
}
/**
* 打印当前场景状态
*/
void printState() {
System.out.println("=== 当前水果状态 ===");
for (Fruit f : fruits) {
System.out.println(f);
}
System.out.println("水果总数: " + fruits.size());
}
public static void main(String[] args) {
MergeWatermelon game = new MergeWatermelon();
// 模拟游戏过程：AI自动放置5个水果
for (int i = 0; i < 5; i++) {
int level = game.random.nextInt(3); // 随机生成0-2级水果
double bestX = game.findBestDropPosition(level);
game.spawnFruit(bestX, level);
// 模拟10帧物理更新
for (int frame = 0; frame < 10; frame++) {
game.updatePhysics();
}
System.out.println("\n--- 第" + (i + 1) + "个水果放置后 ---");
game.printState();
}
System.out.println("\n游戏结束，最终水果数量: " + game.fruits.size());
}
}
四、算法复杂度分析
| 算法模块 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 碰撞检测 | $O(n^2)$ | $O(1)$ | 两两遍历，$n$ 为水果数量 |
| 碰撞响应 | $O(1)$ | $O(1)$ | 单次碰撞计算为常数时间 |
| 合并判定 | $O(1)$ | $O(1)$ | 等级比较与创建新对象 |
| 贪心放置 | $O(k \cdot n)$ | $O(1)$ | $k$ 为搜索位置数，约 $WIDTH/step$ |
| 空间划分优化 | $O(n)$ | $O(n)$ | 使用均匀网格可将碰撞降为线性 |
对于水果数量较少的场景（通常 $< 50$），$O(n^2)$ 的碰撞检测完全足够。若需优化，可引入均匀网格（Uniform Grid）或四叉树（Quadtree）进行空间划分，将复杂度降至 $O(n)$。
五、贪心策略的局限与改进
当前贪心策略仅考虑当前水果的最佳落点，属于贪心局部最优。实际游戏中更优的策略应考虑：
- 未来多步规划：使用蒙特卡洛树搜索（MCTS）评估不同落点的长期收益
- 局面评估函数：综合考量水果分布均匀性、高等级水果位置、顶部空间余量
- 危险预判：检测顶部水果是否接近溢出边界，提前调整策略
六、总结
本文完整实现了合成大西瓜的核心物理引擎与AI策略。通过圆形碰撞检测、弹性碰撞响应和贪心放置策略，读者可以深入理解休闲游戏背后的算法原理。关键收获包括：
- 使用平方距离避免开方运算，优化碰撞检测性能
- 动量守恒简化模型实现真实的碰撞反弹效果
- 贪心启发式函数的设计思路：同级聚集 + 底部支撑 + 边缘惩罚
- 物理模拟的迭代求解方法提升稳定性
