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

合成大西瓜是一款极具上瘾性的休闲益智游戏，玩家通过控制水果的下落位置，使相同水果碰撞合并成更大一级的水果，最终目标是合成大西瓜。本文将用Java完整实现该游戏的核心算法，重点讲解圆形物体的碰撞检测、弹性碰撞响应以及贪心合并策略。

一、游戏机制与算法分析

游戏的核心机制可以分解为以下几个算法问题：

1. 圆形碰撞检测：判断两个圆形水果是否接触或重叠
2. 碰撞响应：处理碰撞后的速度变化与位置修正
3. 合并判定：相同等级水果碰撞后触发合并逻辑
4. 贪心放置策略：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());
    }
}

四、算法复杂度分析

对于水果数量较少的场景（通常 $< 50$），$O(n^2)$ 的碰撞检测完全足够。若需优化，可引入均匀网格（Uniform Grid）或四叉树（Quadtree）进行空间划分，将复杂度降至 $O(n)$。

五、贪心策略的局限与改进

当前贪心策略仅考虑当前水果的最佳落点，属于贪心局部最优。实际游戏中更优的策略应考虑：

1. 未来多步规划：使用蒙特卡洛树搜索（MCTS）评估不同落点的长期收益
2. 局面评估函数：综合考量水果分布均匀性、高等级水果位置、顶部空间余量
3. 危险预判：检测顶部水果是否接近溢出边界，提前调整策略

六、总结

本文完整实现了合成大西瓜的核心物理引擎与AI策略。通过圆形碰撞检测、弹性碰撞响应和贪心放置策略，读者可以深入理解休闲游戏背后的算法原理。关键收获包括：

• 使用平方距离避免开方运算，优化碰撞检测性能
• 动量守恒简化模型实现真实的碰撞反弹效果
• 贪心启发式函数的设计思路：同级聚集 + 底部支撑 + 边缘惩罚
• 物理模拟的迭代求解方法提升稳定性