每日算法 — 使用java实现泡泡堂：BFS炸弹传播与A*智能逃生策略

引言

泡泡堂（BnB）是一款经典的休闲竞技游戏，玩家通过放置炸弹来破坏障碍物并攻击对手。游戏的核心算法涉及炸弹爆炸的广度优先传播、安全区域的动态计算以及玩家的智能逃生路径规划。本文使用Java实现泡泡堂的核心算法模块，重点讲解BFS爆炸传播模拟与A*寻路在紧急逃生中的应用。

游戏场景建模

将游戏地图抽象为一个二维网格：
– 0 表示空地，可以通行和放置炸弹
– 1 表示固定障碍物（不可破坏）
– 2 表示可破坏箱子
– 3 表示炸弹

炸弹爆炸时，会沿上下左右四个方向传播火焰，火焰遇到固定障碍物停止，遇到箱子则破坏箱子并停止。

BFS炸弹传播算法

炸弹爆炸的火焰传播本质上是四个方向上的射线传播，可以使用BFS模拟多源传播过程。

import java.util.*;

/**
 * 泡泡堂核心算法：炸弹爆炸传播与路径规划
 */
public class BombGame {

    private static final int EMPTY = 0;
    private static final int WALL = 1;    // 固定障碍物
    private static final int BOX = 2;     // 可破坏箱子
    private static final int BOMB = 3;    // 炸弹
    private static final int FIRE = 4;    // 火焰

    private int rows;
    private int cols;
    private int[][] map;
    private int bombPower; // 炸弹爆炸范围

    public BombGame(int rows, int cols, int bombPower) {
        this.rows = rows;
        this.cols = cols;
        this.bombPower = bombPower;
        this.map = new int[rows][cols];
    }

    /**
     * 使用BFS模拟炸弹爆炸传播
     * @param bombRow 炸弹行坐标
     * @param bombCol 炸弹列坐标
     * @return 被火焰覆盖的所有坐标列表
     */
    public List<int[]> simulateExplosion(int bombRow, int bombCol) {
        List<int[]> fireCells = new ArrayList<>();
        fireCells.add(new int[]{bombRow, bombCol});

        // 四个方向：上、下、左、右
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        for (int[] dir : directions) {
            for (int step = 1; step <= bombPower; step++) {
                int nr = bombRow + dir[0] * step;
                int nc = bombCol + dir[1] * step;

                // 边界检查
                if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) {
                    break;
                }

                // 遇到固定障碍物，火焰停止
                if (map[nr][nc] == WALL) {
                    break;
                }

                fireCells.add(new int[]{nr, nc});

                // 遇到箱子，破坏后停止
                if (map[nr][nc] == BOX) {
                    break;
                }
            }
        }

        return fireCells;
    }

    /**
     * 多炸弹连锁爆炸模拟
     * 使用BFS处理炸弹之间的连锁反应
     */
    public Set<String> simulateChainExplosion(List<int[]> bombs) {
        Set<String> allFire = new HashSet<>();
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[rows][cols];

        // 初始化所有炸弹位置
        for (int[] bomb : bombs) {
            queue.offer(bomb);
            visited[bomb[0]][bomb[1]] = true;
        }

        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int r = current[0], c = current[1];

            // 模拟当前炸弹爆炸
            List<int[]> fireCells = simulateExplosion(r, c);
            for (int[] cell : fireCells) {
                allFire.add(cell[0] + "," + cell[1]);

                // 如果火焰触发其他炸弹，加入队列
                if (map[cell[0]][cell[1]] == BOMB && !visited[cell[0]][cell[1]]) {
                    queue.offer(cell);
                    visited[cell[0]][cell[1]] = true;
                }
            }
        }

        return allFire;
    }

A*智能逃生路径

当炸弹即将爆炸时，AI需要快速找到最近的安全位置。A*算法结合曼哈顿距离启发式函数是理想选择。

    /**
     * A*寻路算法寻找逃生路径
     * @param start 起点 [row, col]
     * @param dangerousCells 危险区域（即将被火焰覆盖）
     * @return 到达安全区域的最短路径
     */
    public List<int[]> findEscapePath(int[] start, Set<String> dangerousCells) {
        PriorityQueue<Node> openSet = new PriorityQueue<>(Comparator.comparingInt(n -> n.f));
        boolean[][] closedSet = new boolean[rows][cols];
        Map<String, String> cameFrom = new HashMap<>();

        Node startNode = new Node(start[0], start[1], 0, 
            heuristic(start[0], start[1], dangerousCells));
        openSet.offer(startNode);

        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        while (!openSet.isEmpty()) {
            Node current = openSet.poll();

            // 到达安全区域
            if (!dangerousCells.contains(current.r + "," + current.c)) {
                return reconstructPath(cameFrom, current);
            }

            if (closedSet[current.r][current.c]) continue;
            closedSet[current.r][current.c] = true;

            for (int[] dir : directions) {
                int nr = current.r + dir[0];
                int nc = current.c + dir[1];

                if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
                if (closedSet[nr][nc]) continue;
                if (map[nr][nc] == WALL || map[nr][nc] == BOX) continue;

                int gScore = current.g + 1;
                int hScore = heuristic(nr, nc, dangerousCells);
                Node neighbor = new Node(nr, nc, gScore, hScore);

                String key = nr + "," + nc;
                String currentKey = current.r + "," + current.c;
                cameFrom.put(key, currentKey);
                openSet.offer(neighbor);
            }
        }

        return new ArrayList<>(); // 无逃生路径
    }

    /**
     * 启发式函数：到最近安全区域的曼哈顿距离
     */
    private int heuristic(int r, int c, Set<String> dangerousCells) {
        // 搜索最近的安全位置作为启发值
        int minDist = Integer.MAX_VALUE;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (!dangerousCells.contains(i + "," + j) && map[i][j] != WALL && map[i][j] != BOX) {
                    int dist = Math.abs(r - i) + Math.abs(c - j);
                    minDist = Math.min(minDist, dist);
                }
            }
        }
        return minDist == Integer.MAX_VALUE ? 0 : minDist;
    }

    private List<int[]> reconstructPath(Map<String, String> cameFrom, Node current) {
        List<int[]> path = new ArrayList<>();
        String key = current.r + "," + current.c;
        while (cameFrom.containsKey(key)) {
            String[] parts = key.split(",");
            path.add(0, new int[]{Integer.parseInt(parts[0]), Integer.parseInt(parts[1])});
            key = cameFrom.get(key);
        }
        path.add(0, new int[]{current.r, current.c});
        return path;
    }

    static class Node {
        int r, c, g, f;
        Node(int r, int c, int g, int h) {
            this.r = r; this.c = c; this.g = g; this.f = g + h;
        }
    }

安全区域预计算

在炸弹放置后、爆炸前的延迟时间内，预计算所有危险区域：

    /**
     * 预计算所有即将爆炸的危险区域
     */
    public Set<String> predictDangerZones(List<BombInfo> activeBombs) {
        Set<String> danger = new HashSet<>();

        for (BombInfo bomb : activeBombs) {
            List<int[]> fire = simulateExplosion(bomb.row, bomb.col);
            for (int[] cell : fire) {
                danger.add(cell[0] + "," + cell[1]);
            }
        }

        return danger;
    }

    static class BombInfo {
        int row, col, timer;
        BombInfo(int row, int col, int timer) {
            this.row = row; this.col = col; this.timer = timer;
        }
    }

完整测试用例

    public static void main(String[] args) {
        // 创建 7x7 游戏地图
        BombGame game = new BombGame(7, 7, 2);

        // 设置地图障碍物
        int[][] mapData = {
            {0, 0, 1, 0, 0, 0, 0},
            {0, 2, 1, 2, 0, 2, 0},
            {0, 0, 0, 0, 0, 0, 0},
            {1, 2, 0, 3, 0, 2, 1},
            {0, 0, 0, 0, 0, 0, 0},
            {0, 2, 1, 2, 0, 2, 0},
            {0, 0, 0, 0, 0, 0, 0}
        };
        game.map = mapData;

        System.out.println("=== 泡泡堂炸弹传播模拟 ===");

        // 模拟中央炸弹爆炸
        List<int[]> fire = game.simulateExplosion(3, 3);
        System.out.println("炸弹在(3,3)爆炸，火焰覆盖" + fire.size() + "个格子");

        // 寻找逃生路径
        Set<String> danger = new HashSet<>();
        for (int[] cell : fire) {
            danger.add(cell[0] + "," + cell[1]);
        }

        List<int[]> escapePath = game.findEscapePath(new int[]{3, 4}, danger);
        System.out.println("从(3,4)逃生的最短路径长度: " + escapePath.size());
    }
}

复杂度分析

其中 k 为炸弹威力，b 为炸弹数量。

总结

本文通过泡泡堂游戏场景，实现了炸弹爆炸的BFS传播模拟、连锁爆炸的多源BFS处理，以及基于A*算法的智能逃生路径搜索。读者可以掌握网格地图上的广度优先搜索与启发式寻路的工程实践方法。