每日算法 — 使用java实现爆破气球：物理模拟与贪心消除顺序

可莉爸爸 AI算法

一、背景介绍

爆破气球（Balloon Pop）是一款简单但富有策略性的休闲游戏。玩家在限定次数内按顺序刺破漂浮在不同高度的气球，每次爆破会产生连锁反应——爆开的气球可能触发相邻气球也爆破，触发额外的得分奖励。游戏目标是在最少次数内获得最高总分。

本游戏的核心算法包括：

  • 物理模拟：气球在浮力与重力作用下的运动轨迹。
  • 连锁反应：爆破波在气球网络中的传播。
  • 贪心选择：选择爆破顺序以最大化连锁消除数。
  • 图论建模：把气球抽象为图节点，连锁关系作为边。

二、整体设计

  • Balloon：包含位置、半径、颜色、HP、爆裂状态。
  • Physics：浮力、重力、空气阻力的简单物理模型。
  • ChainGraph：气球连锁反应的有向图，BFS 传播爆裂。
  • GreedyStrategy：贪心选择每次爆破哪只气球以触发最长链。
  • GameMain：演示一次完整的爆破过程与得分。

三、完整代码实现

3.1 气球 Balloon.java

/**
 * 气球
 * 状态：位置 (x, y)、半径 r、HP、是否已爆
 */
public class Balloon {
    public final int id;
    public double x, y;        // 位置
    public double vx, vy;      // 速度
    public final double radius;
    public int hp;             // 剩余血量
    public boolean popped;     // 是否已爆
    public final int color;    // 颜色（决定连锁时影响范围）

    public Balloon(int id, double x, double y, double radius, int hp, int color) {
        this.id = id;
        this.x = x; this.y = y;
        this.vx = 0; this.vy = 0;
        this.radius = radius;
        this.hp = hp;
        this.popped = false;
        this.color = color;
    }

    public boolean overlaps(Balloon other) {
        double dx = x - other.x, dy = y - other.y;
        return Math.hypot(dx, dy) < (radius + other.radius);
    }
}

3.2 物理模拟 Physics.java

import java.util.*;

/**
 * 物理模拟
 * 浮力向上、重力向下、空气阻力与速度成正比
 *   ay = (buoyancy - gravity) / mass - drag * vy / mass
 */
public class Physics {
    public static final double G = 9.8;
    public static final double AIR_DENSITY = 1.225;
    public final double buoyancy;   // 单位体积浮力
    public final double drag;       // 阻力系数
    public final double dt;         // 时间步长

    public Physics(double buoyancy, double drag, double dt) {
        this.buoyancy = buoyancy;
        this.drag = drag;
        this.dt = dt;
    }

    public static Physics helium() {
        // 氦气浮力约 1.1 kg/m^3
        return new Physics(11.0, 0.05, 0.02);
    }

    /**
     * 推进一个时间步
     * 浮力 = buoyancy * volume
     * 体积 = 4/3 * pi * r^3
     * 质量 mass = volume * AIR_DENSITY
     */
    public void step(Balloon b) {
        double volume = (4.0 / 3.0) * Math.PI * Math.pow(b.radius, 3);
        double mass = volume * AIR_DENSITY;
        double netForce = (buoyancy - AIR_DENSITY * G) * volume;
        double ay = netForce / mass - drag * b.vy / mass;
        b.vy += ay * dt;
        b.vx *= 0.99; // 水平轻微阻尼
        b.x += b.vx * dt;
        b.y += b.vy * dt;

        // 地面反弹
        if (b.y < b.radius) {
            b.y = b.radius;
            b.vy = -b.vy * 0.5; // 弹性碰撞
        }
    }
}

3.3 连锁图 ChainGraph.java

import java.util.*;

/**
 * 连锁反应图
 * 当气球 A 被刺破时，与 A 距离 <= 触发半径 r 的同色或近色气球也会被触发
 * 使用 BFS 传播爆裂
 */
public class ChainGraph {
    private final List<Balloon> balloons = new ArrayList<>();
    private final double triggerRadius;

    public ChainGraph(double triggerRadius) {
        this.triggerRadius = triggerRadius;
    }

    public void addBalloon(Balloon b) { balloons.add(b); }
    public List<Balloon> getBalloons() { return balloons; }

    /**
     * 计算邻居：距离 < triggerRadius 的其他气球
     */
    public List<Balloon> neighbors(Balloon b) {
        List<Balloon> result = new ArrayList<>();
        for (Balloon other : balloons) {
            if (other == b || other.popped) continue;
            double dx = b.x - other.x, dy = b.y - other.y;
            if (Math.hypot(dx, dy) < triggerRadius) result.add(other);
        }
        return result;
    }

    /**
     * 触发爆裂链：从 balloon 出发 BFS 传播
     * 返回被引爆的所有气球
     */
    public List<Balloon> popChain(Balloon start) {
        List<Balloon> popped = new ArrayList<>();
        if (start.popped) return popped;
        Queue<Balloon> queue = new ArrayDeque<>();
        start.popped = true;
        queue.add(start);
        popped.add(start);

        while (!queue.isEmpty()) {
            Balloon cur = queue.poll();
            for (Balloon nb : neighbors(cur)) {
                if (nb.popped) continue;
                // 同色一定触发；不同色概率触发
                boolean trigger = (nb.color == cur.color) || Math.random() < 0.3;
                if (trigger) {
                    nb.popped = true;
                    popped.add(nb);
                    queue.add(nb);
                }
            }
        }
        return popped;
    }
}

3.4 贪心策略 GreedyStrategy.java

import java.util.*;

/**
 * 贪心策略
 * 给定一个 ChainGraph 与一个允许刺破次数 budget，
 * 每次选择能触发最长连锁的气球优先爆破
 * 目标：最大化总爆裂数
 */
public class GreedyStrategy {
    private final ChainGraph graph;
    private final int budget;

    public GreedyStrategy(ChainGraph graph, int budget) {
        this.graph = graph;
        this.budget = budget;
    }

    /**
     * 模拟贪心爆破
     * 每一步：扫描未爆气球，对每个气球模拟链式反应，选取引爆数最大的
     * 注意：模拟时需要临时回滚 popped 状态
     */
    public SimulationResult simulate() {
        int totalPopped = 0;
        List<Integer> chosenIds = new ArrayList<>();
        List<Integer> chainSizes = new ArrayList<>();
        for (int step = 0; step < budget; step++) {
            Balloon best = null;
            int bestSize = -1;
            // 扫描所有未爆气球
            for (Balloon b : graph.getBalloons()) {
                if (b.popped) continue;
                // 模拟链式反应
                Map<Balloon, Boolean> backup = new HashMap<>();
                for (Balloon x : graph.getBalloons()) backup.put(x, x.popped);
                List<Balloon> chain = graph.popChain(b);
                int size = chain.size();
                // 回滚
                for (Map.Entry<Balloon, Boolean> e : backup.entrySet())
                    e.getKey().popped = e.getValue();
                if (size > bestSize) { bestSize = size; best = b; }
            }
            if (best == null) break;
            List<Balloon> chain = graph.popChain(best);
            totalPopped += chain.size();
            chosenIds.add(best.id);
            chainSizes.add(chain.size());
        }
        return new SimulationResult(totalPopped, chosenIds, chainSizes);
    }

    public static class SimulationResult {
        public final int totalPopped;
        public final List<Integer> chosenIds;
        public final List<Integer> chainSizes;
        public SimulationResult(int total, List<Integer> ids, List<Integer> sizes) {
            this.totalPopped = total;
            this.chosenIds = ids;
            this.chainSizes = sizes;
        }
        public void print() {
            System.out.println("Total popped: " + totalPopped);
            System.out.println("Choices (id, chainSize): " + chosenIds + " " + chainSizes);
        }
    }
}

3.5 主程序 GameMain.java

import java.util.*;

/**
 * 爆破气球游戏主程序
 * 模拟 30 个气球，玩家有 5 次刺破机会，贪心选择最大化总爆裂数
 */
public class GameMain {
    public static void main(String[] args) {
        Random rand = new Random(42);
        ChainGraph graph = new ChainGraph(2.5);

        // 随机生成 30 个气球
        for (int i = 0; i < 30; i++) {
            double x = rand.nextDouble() * 30.0;
            double y = rand.nextDouble() * 15.0 + 1.0;
            double r = 0.4 + rand.nextDouble() * 0.3;
            int color = rand.nextInt(5);
            graph.addBalloon(new Balloon(i, x, y, r, 1, color));
        }

        // 物理模拟若干步，让气球稳定
        Physics physics = Physics.helium();
        for (int t = 0; t < 100; t++) {
            for (Balloon b : graph.getBalloons()) physics.step(b);
        }

        // 贪心爆破
        GreedyStrategy strategy = new GreedyStrategy(graph, 5);
        GreedyStrategy.SimulationResult res = strategy.simulate();
        System.out.println("=== 爆破气球 - 贪心策略 ===");
        res.print();

        // 物理模拟后查看剩余气球
        int remaining = 0;
        for (Balloon b : graph.getBalloons()) if (!b.popped) remaining++;
        System.out.println("Remaining balloons: " + remaining);
    }
}

四、算法分析

4.1 物理模拟

  • 每帧 O(N) 推进 N 个气球位置。
  • 总模拟时间 100 帧，N=30 时约 3000 次运算。

4.2 连锁反应 BFS

  • 单次 BFS 复杂度 O(N + E)，E 为相邻对数。
  • 由于 triggerRadius 较小，E << N^2。

4.3 贪心选择

  • 每次扫描 N 个候选，每个候选模拟一次 BFS。
  • 单次决策 O(N * (N + E))。
  • 总决策 O(budget * N * (N + E))，budget=5、N=30 时约 4500 次运算。

4.4 贪心最优性

  • 贪心算法在每一步选择局部最优，但不一定全局最优。例如可能存在先用一次机会触发小链，再用一次触发包含多个小链覆盖区的大链。
  • 实际可使用动态规划精确求解，状态为 (剩余 budget, 已爆气球集合)，但状态空间 2^N 太大。

五、可扩展方向

  1. 精确 DP：用 bitmask 表示已爆状态，求解最优爆破顺序。
  2. 蒙特卡洛搜索：用 MCTS 评估每步动作的长期收益。
  3. 多色连锁规则：同色必爆，相邻色概率爆，无关色不爆。
  4. 强化学习：用 PPO 训练自适应策略，应对不同关卡布局。

六、运行说明

将 Balloon.java、Physics.java、ChainGraph.java、GreedyStrategy.java、GameMain.java 放入同一目录，javac *.java && java GameMain，程序会输出贪心策略下的总爆裂数与每次选择的气球 ID。

Tagged with: