每日算法 — 使用java实现大西瓜：物理碰撞检测与贪心合并策略

“合成大西瓜”是一款曾风靡全网的休闲益智小游戏。游戏的核心机制是：玩家从顶部投放不同大小的圆形水果，水果受重力下落并在底部堆叠；当两个相同类型的水果接触时，会合并为更大一级的水果。本文用Java实现该游戏的核心物理引擎，重点讲解圆形刚体的碰撞检测与响应、空间划分加速，以及基于贪心策略的合并时机决策算法。

一、游戏物理模型

1.1 水果状态表示

每个水果由以下属性描述：

• 位置 ((x, y))、半径 (r)、质量 (m \propto r^2)
• 速度 ((v_x, v_y))、角速度 (\omega)
• 类型等级 (level \in {0, 1, …, 10})，等级越高半径越大

1.2 运动方程

水果在重力作用下下落，同时受底部边界和其他水果的碰撞约束：

[\ddot{x} = 0, \quad \ddot{y} = -g]

当水果间发生碰撞时，采用基于冲量的碰撞响应模型。对于两个质量分别为 (m_1, m_2)、恢复系数为 (e) 的圆形物体，沿碰撞法线方向的相对速度在碰撞后变为 (-e) 倍碰撞前相对速度。

1.3 合并条件

两个水果合并需同时满足：

1. 圆心距离 (d < r_1 + r_2 + \epsilon)（接触或轻微重叠）
2. 类型等级相同：(level_1 = level_2)
3. 两者均处于”稳定期”（碰撞后经过一段冷却时间，防止连续合并）

合并后新水果的等级为 (level + 1)，半径按预设比例增长。

二、核心算法设计

2.1 圆形碰撞检测

最直接的方法是 (O(n^2)) 两两检测，但当水果数量达到数十个时效率低下。本文采用均匀网格空间划分（Uniform Grid Spatial Hashing）：将游戏区域划分为固定大小的网格单元，每个水果根据其位置映射到一个或多个网格中。碰撞检测时，只需检查同一网格及相邻网格中的水果对，平均复杂度降至 (O(n))。

2.2 基于冲量的碰撞响应

对于碰撞对 ((A, B))：

1. 计算碰撞法线：(\vec{n} = (B – A) / |B – A|)
2. 计算相对速度在法线方向的分量：(v_{rel} = (\vec{v}_B – \vec{v}_A) \cdot \vec{n})
3. 若 (v_{rel} > 0)（正在分离），跳过
4. 计算冲量大小：(j = -(1+e) v_{rel} / (1/m_A + 1/m_B))
5. 应用冲量：(\vec{v}_A -= j/m_A \cdot \vec{n})，(\vec{v}_B += j/m_B \cdot \vec{n})

2.3 位置修正

为避免水果相互穿透导致的数值不稳定性，每次碰撞响应后进行位置修正：将两水果沿碰撞法线方向推开，推开距离与穿透深度成正比。

2.4 贪心合并策略

AI自动玩”合成大西瓜”时，需要在每个回合选择最佳投放位置和水果类型。本文实现一个简化版贪心策略：

1. 空间评估：扫描底部区域，找到”最大连续空档”
2. 对齐投放：将水果投放在与底部最大水果相同的水平位置，以增加碰撞合并概率
3. 高度惩罚：避免在已堆叠较高区域投放，防止提前触顶

三、完整Java实现

import java.util.*;

/**
 * 合成大西瓜物理引擎与贪心策略
 * 运用圆形碰撞检测、冲量响应与空间划分加速
 */
public class BigWatermelon {

    // 物理常量
    private static final double G = 9.8;           // 重力加速度
    private static final double DT = 0.016;        // 时间步长 (60FPS)
    private static final double RESTITUTION = 0.3; // 恢复系数（非弹性碰撞）
    private static final double FRICTION = 0.98;   // 速度衰减
    private static final double MERGE_COOLDOWN = 0.3; // 合并冷却时间(s)
    private static final double BOUNDS_WIDTH = 6.0;   // 游戏区域宽度
    private static final double BOUNDS_HEIGHT = 8.0;  // 游戏区域高度

    // 水果半径配置（等级0到10）
    private static final double[] RADII = {
        0.15, 0.20, 0.25, 0.30, 0.35,
        0.40, 0.50, 0.60, 0.75, 0.90, 1.10
    };

    /** 水果实体 */
    static class Fruit {
        double x, y;           // 位置
        double vx, vy;         // 速度
        int level;             // 类型等级
        double radius;         // 半径
        double mass;           // 质量
        double cooldown;       // 合并冷却计时
        boolean merged;        // 是否已被合并
        int id;                // 唯一标识

        static int nextId = 0;

        Fruit(double x, double y, int level) {
            this.x = x; this.y = y;
            this.vx = 0; this.vy = 0;
            this.level = level;
            this.radius = RADII[level];
            this.mass = radius * radius; // 质量 ∝ 面积
            this.cooldown = MERGE_COOLDOWN;
            this.merged = false;
            this.id = nextId++;
        }
    }

    private final List<Fruit> fruits;
    private final Random random;

    public BigWatermelon() {
        this.fruits = new ArrayList<>();
        this.random = new Random(42);
    }

    /**
     * 空间划分：均匀网格哈希
     * 网格大小取最大水果直径
     */
    private Map<Long, List<Fruit>> buildSpatialGrid() {
        Map<Long, List<Fruit>> grid = new HashMap<>();
        double cellSize = RADII[RADII.length - 1] * 2.5;
        for (Fruit f : fruits) {
            if (f.merged) continue;
            long gx = (long) Math.floor(f.x / cellSize);
            long gy = (long) Math.floor(f.y / cellSize);
            long key = (gx << 32) ^ (gy & 0xffffffffL);
            grid.computeIfAbsent(key, k -> new ArrayList<>()).add(f);
        }
        return grid;
    }

    /**
     * 检测并处理所有碰撞对
     */
    private void resolveCollisions() {
        Map<Long, List<Fruit>> grid = buildSpatialGrid();
        double cellSize = RADII[RADII.length - 1] * 2.5;
        Set<String> processed = new HashSet<>();

        for (Map.Entry<Long, List<Fruit>> entry : grid.entrySet()) {
            long key = entry.getKey();
            int gx = (int) (key >> 32);
            int gy = (int) (key & 0xffffffffL);

            // 检查当前格及8邻域
            for (int dx = -1; dx <= 1; dx++) {
                for (int dy = -1; dy <= 1; dy++) {
                    long nKey = (((long)(gx + dx)) << 32) ^ (((long)(gy + dy)) & 0xffffffffL);
                    List<Fruit> neighbors = grid.get(nKey);
                    if (neighbors == null) continue;

                    for (Fruit a : entry.getValue()) {
                        for (Fruit b : neighbors) {
                            if (a.id >= b.id) continue;
                            String pairKey = a.id + "-" + b.id;
                            if (processed.contains(pairKey)) continue;
                            processed.add(pairKey);
                            checkAndResolve(a, b);
                        }
                    }
                }
            }
        }
    }

    private void checkAndResolve(Fruit a, Fruit b) {
        if (a.merged || b.merged) return;

        double dx = b.x - a.x;
        double dy = b.y - a.y;
        double dist = Math.hypot(dx, dy);
        double minDist = a.radius + b.radius;

        if (dist >= minDist || dist < 1e-9) return;

        // 碰撞法线
        double nx = dx / dist;
        double ny = dy / dist;

        // 相对速度
        double dvx = b.vx - a.vx;
        double dvy = b.vy - a.vy;
        double vRel = dvx * nx + dvy * ny;

        if (vRel > 0) return; // 正在分离

        // 冲量响应
        double invMassA = 1.0 / a.mass;
        double invMassB = 1.0 / b.mass;
        double j = -(1 + RESTITUTION) * vRel / (invMassA + invMassB);

        a.vx -= j * invMassA * nx;
        a.vy -= j * invMassA * ny;
        b.vx += j * invMassB * nx;
        b.vy += j * invMassB * ny;

        // 位置修正（防止穿透）
        double overlap = minDist - dist;
        double correction = overlap * 0.5;
        a.x -= correction * nx;
        a.y -= correction * ny;
        b.x += correction * nx;
        b.y += correction * ny;

        // 尝试合并
        tryMerge(a, b);
    }

    private void tryMerge(Fruit a, Fruit b) {
        if (a.level != b.level) return;
        if (a.level >= RADII.length - 1) return; // 已达最大等级
        if (a.cooldown > 0 || b.cooldown > 0) return;

        a.merged = true;
        b.merged = true;

        // 新水果在碰撞中点生成
        double mx = (a.x + b.x) / 2;
        double my = (a.y + b.y) / 2;
        Fruit merged = new Fruit(mx, my, a.level + 1);
        // 继承部分动量
        merged.vx = (a.vx * a.mass + b.vx * b.mass) / (a.mass + b.mass);
        merged.vy = (a.vy * a.mass + b.vy * b.mass) / (a.mass + b.mass);
        fruits.add(merged);
    }

    /**
     * 单步物理更新
     */
    public void step() {
        // 更新位置和速度
        for (Fruit f : fruits) {
            if (f.merged) continue;
            f.vy -= G * DT;
            f.x += f.vx * DT;
            f.y += f.vy * DT;
            f.cooldown = Math.max(0, f.cooldown - DT);

            // 边界约束
            if (f.x - f.radius < -BOUNDS_WIDTH / 2) {
                f.x = -BOUNDS_WIDTH / 2 + f.radius;
                f.vx = Math.abs(f.vx) * RESTITUTION;
            }
            if (f.x + f.radius > BOUNDS_WIDTH / 2) {
                f.x = BOUNDS_WIDTH / 2 - f.radius;
                f.vx = -Math.abs(f.vx) * RESTITUTION;
            }
            if (f.y - f.radius < 0) {
                f.y = f.radius;
                f.vy = Math.abs(f.vy) * RESTITUTION;
            }
            // 顶部溢出检测
            if (f.y + f.radius > BOUNDS_HEIGHT) {
                f.vy *= 0.5;
            }

            // 摩擦衰减
            f.vx *= FRICTION;
            f.vy *= FRICTION;
        }

        // 碰撞检测与响应（迭代多次增加稳定性）
        for (int i = 0; i < 3; i++) {
            resolveCollisions();
        }

        // 清理已合并水果
        fruits.removeIf(f -> f.merged);
    }

    /**
     * 投放新水果
     */
    public void dropFruit(double x, int level) {
        fruits.add(new Fruit(x, BOUNDS_HEIGHT - 0.2, level));
    }

    /**
     * 贪心策略：选择最佳投放位置
     * 策略：寻找底部最大空档的中心，或对齐同等级水果
     */
    public double greedyDropPosition(int level) {
        // 统计底部各区域的水果分布
        int bins = 20;
        double binWidth = BOUNDS_WIDTH / bins;
        double[] heights = new double[bins];
        for (Fruit f : fruits) {
            int bin = (int) ((f.x + BOUNDS_WIDTH / 2) / binWidth);
            bin = Math.max(0, Math.min(bins - 1, bin));
            heights[bin] = Math.max(heights[bin], f.y + f.radius);
        }

        // 寻找最低区域（最大空档）
        int bestBin = bins / 2;
        double minHeight = Double.MAX_VALUE;
        for (int i = 0; i < bins; i++) {
            // 加上中心偏好和高度惩罚
            double score = heights[i] + Math.abs(i - bins / 2) * 0.1;
            if (score < minHeight) {
                minHeight = score;
                bestBin = i;
            }
        }

        // 检查是否有同等级水果可以对齐
        for (Fruit f : fruits) {
            if (f.level == level && f.y < BOUNDS_HEIGHT * 0.5) {
                int bin = (int) ((f.x + BOUNDS_WIDTH / 2) / binWidth);
                if (bin >= 0 && bin < bins && heights[bin] < heights[bestBin] + 1.0) {
                    return f.x; // 对齐投放
                }
            }
        }

        return -BOUNDS_WIDTH / 2 + (bestBin + 0.5) * binWidth;
    }

    /**
     * 模拟一局游戏
     */
    public void simulateGame(int turns) {
        System.out.println("开始模拟 " + turns + " 回合...\n");
        for (int i = 0; i < turns; i++) {
            int level = random.nextInt(3); // 投放0-2级水果
            double pos = greedyDropPosition(level);
            dropFruit(pos, level);

            // 物理模拟直到静止
            for (int s = 0; s < 120; s++) step();

            if ((i + 1) % 10 == 0) {
                printStats(i + 1);
            }
        }
        printStats(turns);
    }

    public void printStats(int turn) {
        int count = 0;
        int maxLevel = 0;
        double maxHeight = 0;
        for (Fruit f : fruits) {
            count++;
            maxLevel = Math.max(maxLevel, f.level);
            maxHeight = Math.max(maxHeight, f.y + f.radius);
        }
        System.out.println("回合 " + turn + ": 水果数=" + count
                         + ", 最高等级=" + maxLevel
                         + "(" + RADII[maxLevel] + "m)"
                         + ", 堆叠高度=" + String.format("%.2f", maxHeight) + "m");
    }

    // ==================== 主程序 ====================
    public static void main(String[] args) {
        System.out.println("===== 合成大西瓜物理引擎与贪心策略 =====\n");

        BigWatermelon game = new BigWatermelon();
        game.simulateGame(50);

        System.out.println("\n【性能对比】碰撞检测优化效果");
        int[] counts = {10, 50, 100, 200};
        for (int n : counts) {
            BigWatermelon test = new BigWatermelon();
            for (int i = 0; i < n; i++) {
                test.dropFruit(test.random.nextDouble() * 4 - 2, test.random.nextInt(4));
            }

            long start = System.nanoTime();
            for (int s = 0; s < 60; s++) test.step();
            long elapsed = System.nanoTime() - start;

            System.out.println("  水果数=" + n + ": 60帧模拟耗时="
                             + String.format("%.2f", elapsed / 1e6) + "ms");
        }
    }
}

四、复杂度分析

空间划分将碰撞检测从 (O(n^2)) 降低到接近 (O(n))，在水果密集场景下加速效果尤为显著。

五、扩展思考

1. 四叉树动态空间划分：当水果分布极不均匀时，均匀网格效率下降。可采用四叉树根据物体密度自适应划分空间，进一步减少无效检测。
2. 蒙特卡洛树搜索（MCTS）：将”合成大西瓜”建模为序列决策问题，用MCTS评估每个投放位置的长远收益，超越局部贪心策略。
3. 连续碰撞检测（CCD）：高速运动的小水果可能在单帧内穿透其他水果，采用基于时间细分的CCD可确保碰撞不遗漏。

“合成大西瓜”的物理引擎涵盖了刚体动力学、碰撞检测和启发式决策三大核心主题，是构建完整2D物理系统的优秀练手项目。