引言
吹泡泡是童年最纯真的乐趣之一。当肥皂泡从吹管中飘出，它们在空气中相互靠近、碰撞、有时合并成更大的泡泡，有时则因表面张力而保持独立。将这一现象抽象为算法问题，核心挑战在于：如何高效检测大量圆形泡泡之间的碰撞，并在合并时找到最优策略以获得最大泡泡？ 本文将用Java实现吹泡泡游戏的物理模拟系统，讲解圆形碰撞检测算法与贪心合并策略，帮助读者在趣味场景中理解计算几何与贪心算法的结合。
算法原理
圆形碰撞检测
两个圆心分别为 $C_1=(x_1, y_1)$ 和 $C_2=(x_2, y_2)$，半径为 $r_1$ 和 $r_2$ 的圆发生碰撞的充要条件是圆心距不大于半径之和：
$$\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$$
对于 $n$ 个泡泡，朴素的两两检测时间复杂度为 $O(n^2)$。当泡泡数量较大时，可使用均匀网格划分（Uniform Grid）或四叉树（Quadtree）进行空间索引优化，将检测复杂度降至 $O(n)$（在均匀分布下）。
泡泡合并的物理规则
当两个泡泡碰撞时，根据表面张力和体积守恒原理：
– 体积守恒：合并后泡泡的体积等于两泡泡体积之和
– 球形假设：合并后的泡泡仍保持球形
设两泡泡半径为 $r_1$ 和 $r_2$，合并后半径为：
$$R = \sqrt[3]{r_1^3 + r_2^3}$$
合并后的圆心位置按体积加权平均：
$$C_{new} = \frac{r_1^3 \cdot C_1 + r_2^3 \cdot C_2}{r_1^3 + r_2^3}$$
贪心最大泡泡策略
游戏目标是获得尽可能大的泡泡。贪心策略为：在每一时刻，优先合并能产生最大半径增量的泡泡对。由于半径增量为 $R – \max(r_1, r_2)$，在体积守恒下，合并相近大小的泡泡往往能获得更好的”性价比”。
Java实现
1. 泡泡基础类与碰撞检测
import java.util.*;
/**
* 泡泡：表示一个圆形肥皂泡
*/
public class Bubble {
public double x, y; // 圆心坐标
public double radius; // 半径
public double vx, vy; // 速度向量
public final int id; // 唯一编号
public boolean merged; // 是否已被合并
public Bubble(int id, double x, double y, double radius, double vx, double vy) {
this.id = id;
this.x = x;
this.y = y;
this.radius = radius;
this.vx = vx;
this.vy = vy;
this.merged = false;
}
/** 计算泡泡体积（三维球体体积，用于合并计算） */
public double getVolume() {
return (4.0 / 3.0) * Math.PI * radius * radius * radius;
}
/** 计算到另一泡泡的圆心距平方 */
public double distanceSqTo(Bubble other) {
double dx = this.x - other.x;
double dy = this.y - other.y;
return dx * dx + dy * dy;
}
/** 判断是否与其他泡泡碰撞 */
public boolean collidesWith(Bubble other) {
if (this.merged || other.merged || this.id == other.id) return false;
double radiusSum = this.radius + other.radius;
return distanceSqTo(other) <= radiusSum * radiusSum;
}
/** 按当前速度更新位置 */
public void move(double dt) {
this.x += vx * dt;
this.y += vy * dt;
}
@Override
public String toString() {
return String.format("Bubble%d(%.1f,%.1f) r=%.2f", id, x, y, radius);
}
}
/**
* 碰撞检测结果
*/
public class Collision {
public final Bubble a;
public final Bubble b;
public final double overlap; // 重叠深度
public Collision(Bubble a, Bubble b) {
this.a = a;
this.b = b;
double dist = Math.sqrt(a.distanceSqTo(b));
this.overlap = (a.radius + b.radius) - dist;
}
}
2. 空间索引优化：均匀网格
/**
* 均匀网格空间索引：加速碰撞检测
*/
public class UniformGrid {
private final double cellSize;
private final Map<Long, List<Bubble>> cells;
public UniformGrid(double cellSize) {
this.cellSize = cellSize;
this.cells = new HashMap<>();
}
/** 清空网格 */
public void clear() {
cells.clear();
}
/** 将泡泡插入网格 */
public void insert(Bubble bubble) {
// 泡泡可能跨越多个网格，需要插入到覆盖泡泡 bounding box 的所有网格
int minCellX = (int) Math.floor((bubble.x - bubble.radius) / cellSize);
int maxCellX = (int) Math.floor((bubble.x + bubble.radius) / cellSize);
int minCellY = (int) Math.floor((bubble.y - bubble.radius) / cellSize);
int maxCellY = (int) Math.floor((bubble.y + bubble.radius) / cellSize);
for (int cx = minCellX; cx <= maxCellX; cx++) {
for (int cy = minCellY; cy <= maxCellY; cy++) {
long key = ((long) cx << 32) | (cy & 0xFFFFFFFFL);
cells.computeIfAbsent(key, k -> new ArrayList<>()).add(bubble);
}
}
}
/** 查找与指定泡泡可能碰撞的所有候选泡泡 */
public List<Bubble> query(Bubble bubble) {
Set<Bubble> candidates = new HashSet<>();
int cellX = (int) Math.floor(bubble.x / cellSize);
int cellY = (int) Math.floor(bubble.y / cellSize);
// 查询相邻9个网格
for (int dx = -1; dx <= 1; dx++) {
for (int dy = -1; dy <= 1; dy++) {
long key = ((long) (cellX + dx) << 32) | ((cellY + dy) & 0xFFFFFFFFL);
List<Bubble> list = cells.get(key);
if (list != null) {
candidates.addAll(list);
}
}
}
return new ArrayList<>(candidates);
}
}
3. 泡泡游戏引擎
/**
* 吹泡泡游戏引擎：管理泡泡运动、碰撞检测与合并
*/
public class BubbleGameEngine {
private final List<Bubble> bubbles;
private final double width, height; // 游戏区域边界
private final UniformGrid grid;
private final double dt; // 时间步长
private int nextId; // 下一个泡泡编号
public BubbleGameEngine(double width, double height, double dt) {
this.bubbles = new ArrayList<>();
this.width = width;
this.height = height;
this.dt = dt;
this.nextId = 0;
this.grid = new UniformGrid(2.0); // 网格大小设为2
}
/** 添加一个新泡泡 */
public void addBubble(double x, double y, double radius, double vx, double vy) {
bubbles.add(new Bubble(nextId++, x, y, radius, vx, vy));
}
/** 更新所有泡泡位置 */
public void updatePositions() {
for (Bubble b : bubbles) {
if (b.merged) continue;
b.move(dt);
// 边界反弹
if (b.x - b.radius < 0) { b.x = b.radius; b.vx = Math.abs(b.vx); }
if (b.x + b.radius > width) { b.x = width - b.radius; b.vx = -Math.abs(b.vx); }
if (b.y - b.radius < 0) { b.y = b.radius; b.vy = Math.abs(b.vy); }
if (b.y + b.radius > height) { b.y = height - b.radius; b.vy = -Math.abs(b.vy); }
}
}
/** 检测所有碰撞（使用均匀网格优化） */
public List<Collision> detectCollisions() {
List<Collision> collisions = new ArrayList<>();
grid.clear();
for (Bubble b : bubbles) {
if (!b.merged) grid.insert(b);
}
Set<String> checked = new HashSet<>();
for (Bubble b : bubbles) {
if (b.merged) continue;
for (Bubble other : grid.query(b)) {
if (other.merged || other.id == b.id) continue;
String key = b.id < other.id ? b.id + "-" + other.id : other.id + "-" + b.id;
if (checked.contains(key)) continue;
checked.add(key);
if (b.collidesWith(other)) {
collisions.add(new Collision(b, other));
}
}
}
return collisions;
}
/** 贪心合并策略：每次合并能产生最大新半径的碰撞对 */
public int mergeGreedy() {
List<Collision> collisions = detectCollisions();
if (collisions.isEmpty()) return 0;
// 按合并后半径增量排序
collisions.sort((c1, c2) -> {
double r1 = Math.cbrt(c1.a.radius * c1.a.radius * c1.a.radius
+ c1.b.radius * c1.b.radius * c1.b.radius);
double r2 = Math.cbrt(c2.a.radius * c2.a.radius * c2.a.radius
+ c2.b.radius * c2.b.radius * c2.b.radius);
return Double.compare(r2, r1); // 降序
});
int mergeCount = 0;
Set<Integer> mergedThisRound = new HashSet<>();
for (Collision col : collisions) {
if (col.a.merged || col.b.merged) continue;
if (mergedThisRound.contains(col.a.id) || mergedThisRound.contains(col.b.id)) continue;
// 执行合并：a吸收b
double volA = col.a.getVolume();
double volB = col.b.getVolume();
double newVol = volA + volB;
double newRadius = Math.cbrt(newVol * 3.0 / (4.0 * Math.PI));
// 加权平均位置（按体积）
col.a.x = (col.a.x * volA + col.b.x * volB) / newVol;
col.a.y = (col.a.y * volA + col.b.y * volB) / newVol;
// 动量守恒合并速度
double totalMass = volA + volB; // 假设密度均匀，质量正比于体积
col.a.vx = (col.a.vx * volA + col.b.vx * volB) / totalMass;
col.a.vy = (col.a.vy * volA + col.b.vy * volMass) / totalMass;
col.a.radius = newRadius;
col.b.merged = true;
mergedThisRound.add(col.a.id);
mergedThisRound.add(col.b.id);
mergeCount++;
}
return mergeCount;
}
/** 清理已被合并的泡泡 */
public void cleanup() {
bubbles.removeIf(b -> b.merged);
}
/** 模拟一步 */
public void step() {
updatePositions();
mergeGreedy();
cleanup();
}
/** 获取当前最大泡泡 */
public Bubble getLargestBubble() {
Bubble largest = null;
for (Bubble b : bubbles) {
if (!b.merged && (largest == null || b.radius > largest.radius)) {
largest = b;
}
}
return largest;
}
/** 获取当前活跃泡泡数量 */
public int getActiveCount() {
int count = 0;
for (Bubble b : bubbles) {
if (!b.merged) count++;
}
return count;
}
/** 打印当前状态 */
public void printState() {
System.out.printf("活跃泡泡数: %d%n", getActiveCount());
Bubble largest = getLargestBubble();
if (largest != null) {
System.out.printf("最大泡泡: %s%n", largest);
}
}
}
### 4. 主程序演示
```java
import java.util.Random;
/**
* 吹泡泡游戏主程序
*/
public class BubbleGameDemo {
public static void main(String[] args) {
Random random = new Random(42);
double width = 50.0, height = 50.0;
BubbleGameEngine engine = new BubbleGameEngine(width, height, 0.1);
// 初始生成20个随机泡泡
int n = 20;
System.out.println("=== 初始泡泡生成 ===");
for (int i = 0; i < n; i++) {
double r = 0.5 + random.nextDouble() * 1.5;
double x = r + random.nextDouble() * (width - 2 * r);
double y = r + random.nextDouble() * (height - 2 * r);
double vx = (random.nextDouble() - 0.5) * 4;
double vy = (random.nextDouble() - 0.5) * 4;
engine.addBubble(x, y, r, vx, vy);
System.out.printf(" Bubble%d: 位置(%.1f,%.1f) 半径=%.2f 速度(%.2f,%.2f)%n",
i, x, y, r, vx, vy);
}
// 模拟100步
System.out.println("\n=== 开始模拟 ===");
engine.printState();
for (int step = 1; step <= 100; step++) {
engine.step();
if (step % 20 == 0) {
System.out.printf("\n--- 第 %d 步 ---%n", step);
engine.printState();
}
}
System.out.println("\n=== 模拟结束 ===");
engine.printState();
// 碰撞检测性能对比
System.out.println("\n=== 性能对比：均匀网格 vs 暴力检测 ===");
performanceTest();
}
public static void performanceTest() {
Random rand = new Random(123);
int[] sizes = {50, 100, 200, 500};
for (int n : sizes) {
BubbleGameEngine engine = new BubbleGameEngine(100, 100, 0.1);
for (int i = 0; i < n; i++) {
engine.addBubble(rand.nextDouble() * 100, rand.nextDouble() * 100,
0.5 + rand.nextDouble(), 0, 0);
}
long start1 = System.nanoTime();
// 暴力检测
int bruteCount = 0;
List<Bubble> list = new ArrayList<>();
// 模拟暴力检测逻辑
long end1 = System.nanoTime();
long start2 = System.nanoTime();
engine.detectCollisions();
long end2 = System.nanoTime();
System.out.printf("泡泡数量: %d | 网格检测: %.3f ms%n",
n, (end2 - start2) / 1_000_000.0);
}
}
}
复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 单对碰撞检测 | $O(1)$ | $O(1)$ | 距离平方比较 |
| 暴力全检测 | $O(n^2)$ | $O(1)$ | $n$ 为泡泡数量 |
| 均匀网格检测 | $O(n)$ | $O(n)$ | 均匀分布假设 |
| 单次合并 | $O(1)$ | $O(1)$ | 体积与位置计算 |
| 贪心排序合并 | $O(m \log m)$ | $O(m)$ | $m$ 为碰撞对数 |
扩展思考
- 表面张力模拟：实际泡泡合并后并非完美球形，可引入最小表面面积原理，通过数值优化求解合并后的真实形状。
- 颜色混合：合并不同颜色的泡泡时，按体积比例混合RGB值，增加视觉效果。
- 重力影响：加入竖直向下的重力加速度，使泡泡呈现更自然的上升和下落运动。
- Quadtree优化：对于泡泡分布极不均匀的场景，四叉树相比均匀网格具有更好的自适应能力。
总结
本文通过Java实现了吹泡泡游戏的碰撞检测与合并模拟系统，核心要点包括：
- 圆心距判定利用距离平方比较实现 $O(1)$ 的圆形碰撞检测
- 均匀网格空间索引将大规模碰撞检测从 $O(n^2)$ 优化至接近 $O(n)$
- 体积守恒合并基于球体体积公式计算合并后半径，位置按体积加权平均
- 贪心最大增量策略每次优先合并能产生最大新泡泡的碰撞对
吹泡泡将计算几何的空间查询与物理守恒定律巧妙结合，是理解碰撞检测和空间索引算法的生动案例。通过扩展表面张力和颜色混合，还能进一步探索计算机图形学中的流体模拟技术。
