每日算法 — 使用java实现炸弹人：BFS爆炸传播与A*智能追击策略

炸弹人（Bomberman）是诞生于1983年的经典街机游戏，玩家操控角色在网格迷宫中放置炸弹，炸毁墙壁和敌人。其核心算法挑战在于：如何高效模拟炸弹的连锁爆炸传播、如何让敌人智能追击玩家、以及如何在复杂局势下做出最优的炸弹放置决策。本文将用Java完整实现炸弹人的核心算法引擎，深入讲解BFS爆炸范围计算、A*寻路驱动的敌人AI，以及基于安全距离评估的策略决策系统。

一、问题建模与地图表示

炸弹人的游戏世界可抽象为一个二维网格，每个格子具有不同的属性。我们用枚举类型定义格子状态：

/**
 * 地图格子类型
 */
enum CellType {
    EMPTY,      // 空地，可行走
    WALL,       // 固定墙壁，不可破坏
    BRICK,      // 砖块，可被炸弹炸毁
    BOMB,       // 已放置的炸弹
    EXPLOSION   // 爆炸中的火焰
}

/**
 * 地图单元格
 */
class Cell {
    CellType type;
    int bombPower;      // 若type=BOMB，记录炸弹威力
    int bombTimer;      // 若type=BOMB，记录剩余引爆时间（帧数）
    int explosionTimer; // 若type=EXPLOSION，记录火焰持续时间

    Cell(CellType type) {
        this.type = type;
    }
}

游戏地图采用二维数组存储，配合玩家位置和敌人列表即可完整描述游戏状态：

class GameMap {
    private final Cell[][] grid;
    private final int rows;
    private final int cols;

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

    GameMap(int rows, int cols) {
        this.rows = rows;
        this.cols = cols;
        this.grid = new Cell[rows][cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                // 边界固定为墙壁
                if (i == 0 || i == rows-1 || j == 0 || j == cols-1) {
                    grid[i][j] = new Cell(CellType.WALL);
                } else {
                    // 随机生成砖块（约30%概率），确保可通行
                    grid[i][j] = new Cell(Math.random() < 0.3 ? CellType.BRICK : CellType.EMPTY);
                }
            }
        }
        // 确保玩家和敌人出生点为空
        grid[1][1].type = CellType.EMPTY;
        grid[rows-2][cols-2].type = CellType.EMPTY;
    }

    boolean inBounds(int r, int c) {
        return r >= 0 && r < rows && c >= 0 && c < cols;
    }

    boolean isWalkable(int r, int c) {
        return inBounds(r, c) && (grid[r][c].type == CellType.EMPTY || grid[r][c].type == CellType.EXPLOSION);
    }

    Cell get(int r, int c) { return grid[r][c]; }
    int getRows() { return rows; }
    int getCols() { return cols; }
}

二、BFS炸弹爆炸传播算法

炸弹引爆后，火焰沿四个方向直线蔓延，直到遇到固定墙壁为止，砖块会被炸毁并阻挡火焰继续传播。爆炸可能引燃其他炸弹，形成连锁反应。使用BFS可以高效计算所有受影响的格子：

import java.util.*;

/**
 * 炸弹爆炸传播计算器
 * 使用BFS处理连锁反应，确保所有被引燃的炸弹都被正确计算
 */
class ExplosionEngine {
    private final GameMap map;

    ExplosionEngine(GameMap map) {
        this.map = map;
    }

    /**
     * 计算并执行爆炸
     * @param bombR 炸弹行坐标
     * @param bombC 炸弹列坐标
     * @return 被爆炸影响的坐标列表（包括炸弹本身位置）
     */
    List<int[]> computeExplosion(int bombR, int bombC) {
        List<int[]> affected = new ArrayList<>();
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[map.getRows()][map.getCols()];

        // 从初始炸弹开始BFS
        queue.offer(new int[]{bombR, bombC});
        visited[bombR][bombC] = true;

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int r = cur[0], c = cur[1];
            Cell cell = map.get(r, c);

            // 获取炸弹威力，若当前格子不是炸弹（被引燃的情况），使用默认威力3
            int power = (cell.type == CellType.BOMB) ? cell.bombPower : 3;

            // 当前格子被爆炸影响
            affected.add(new int[]{r, c});

            // 向四个方向传播
            for (int[] dir : GameMap.DIRECTIONS) {
                for (int step = 1; step <= power; step++) {
                    int nr = r + dir[0] * step;
                    int nc = c + dir[1] * step;

                    if (!map.inBounds(nr, nc)) break;

                    Cell target = map.get(nr, nc);

                    // 固定墙壁阻挡火焰
                    if (target.type == CellType.WALL) break;

                    // 记录受影响位置
                    affected.add(new int[]{nr, nc});

                    // 砖块被炸毁后阻挡后续传播
                    if (target.type == CellType.BRICK) {
                        break;
                    }

                    // 遇到其他炸弹，加入队列处理连锁反应
                    if (target.type == CellType.BOMB && !visited[nr][nc]) {
                        visited[nr][nc] = true;
                        queue.offer(new int[]{nr, nc});
                        break; // 炸弹位置阻挡火焰继续沿此方向传播
                    }
                }
            }
        }

        return affected;
    }

    /**
     * 执行一帧的爆炸计时更新
     * 返回本帧内新引爆的炸弹位置列表
     */
    List<int[]> updateBombs() {
        List<int[]> exploded = new ArrayList<>();

        for (int i = 0; i < map.getRows(); i++) {
            for (int j = 0; j < map.getCols(); j++) {
                Cell cell = map.get(i, j);
                if (cell.type == CellType.BOMB) {
                    cell.bombTimer--;
                    if (cell.bombTimer <= 0) {
                        exploded.add(new int[]{i, j});
                    }
                } else if (cell.type == CellType.EXPLOSION) {
                    cell.explosionTimer--;
                    if (cell.explosionTimer <= 0) {
                        cell.type = CellType.EMPTY;
                    }
                }
            }
        }

        // 处理爆炸
        for (int[] pos : exploded) {
            List<int[]> affected = computeExplosion(pos[0], pos[1]);
            for (int[] a : affected) {
                Cell cell = map.get(a[0], a[1]);
                if (cell.type == CellType.BRICK) {
                    cell.type = CellType.EMPTY; // 炸毁砖块
                } else if (cell.type == CellType.BOMB) {
                    // 连锁爆炸已在computeExplosion中通过BFS处理
                    cell.type = CellType.EXPLOSION;
                    cell.explosionTimer = 3;
                } else if (cell.type != CellType.WALL) {
                    cell.type = CellType.EXPLOSION;
                    cell.explosionTimer = 3;
                }
            }
        }

        return exploded;
    }
}

三、A*寻路驱动的敌人AI

敌人需要能够智能追击玩家，同时避开即将爆炸的区域。A*算法配合动态障碍物更新是实现这一行为的核心：

/**
 * A*寻路节点
 */
class Node implements Comparable<Node> {
    int r, c;           // 坐标
    int g;              // 从起点到当前节点的实际代价
    int h;              // 启发式估计值（曼哈顿距离）
    Node parent;        // 父节点，用于回溯路径

    Node(int r, int c, int g, int h, Node parent) {
        this.r = r; this.c = c;
        this.g = g; this.h = h;
        this.parent = parent;
    }

    int f() { return g + h; }

    @Override
    public int compareTo(Node o) {
        return Integer.compare(this.f(), o.f());
    }
}

/**
 * 敌人AI控制器
 * 基于A*寻路，结合安全区域判断实现智能追击
 */
class EnemyAI {
    private final GameMap map;
    private int posR, posC;     // 敌人当前位置

    EnemyAI(GameMap map, int startR, int startC) {
        this.map = map;
        this.posR = startR;
        this.posC = startC;
    }

    /**
     * A*寻路：从当前位置到目标位置的最短路径
     * @param targetR 目标行
     * @param targetC 目标列
     * @return 下一步应移动的坐标 [r, c]，若无法到达返回null
     */
    int[] findPath(int targetR, int targetC) {
        PriorityQueue<Node> open = new PriorityQueue<>();
        boolean[][] closed = new boolean[map.getRows()][map.getCols()];

        open.offer(new Node(posR, posC, 0, heuristic(posR, posC, targetR, targetC), null));

        while (!open.isEmpty()) {
            Node cur = open.poll();

            if (cur.r == targetR && cur.c == targetC) {
                // 回溯找到第一步
                Node step = cur;
                while (step.parent != null && step.parent.parent != null) {
                    step = step.parent;
                }
                return new int[]{step.r, step.c};
            }

            if (closed[cur.r][cur.c]) continue;
            closed[cur.r][cur.c] = true;

            for (int[] dir : GameMap.DIRECTIONS) {
                int nr = cur.r + dir[0];
                int nc = cur.c + dir[1];

                if (!map.isWalkable(nr, nc) || closed[nr][nc]) continue;

                // 避开爆炸区域（增加额外代价）
                int extraCost = (map.get(nr, nc).type == CellType.EXPLOSION) ? 100 : 0;

                int ng = cur.g + 1 + extraCost;
                int nh = heuristic(nr, nc, targetR, targetC);
                open.offer(new Node(nr, nc, ng, nh, cur));
            }
        }

        return null; // 无可行路径
    }

    /**
     * 曼哈顿距离启发式
     */
    private int heuristic(int r1, int c1, int r2, int c2) {
        return Math.abs(r1 - r2) + Math.abs(c1 - c2);
    }

    /**
     * 敌人决策：优先追击玩家，若玩家附近危险则随机游走
     * @param playerR 玩家行
     * @param playerC 玩家列
     * @return 下一步移动方向 [dr, dc]
     */
    int[] decideMove(int playerR, int playerC) {
        // 首先尝试直接追击
        int[] next = findPath(playerR, playerC);
        if (next != null) {
            return new int[]{next[0] - posR, next[1] - posC};
        }

        // 若无法直接到达，随机选择安全方向
        List<int[]> safeDirs = new ArrayList<>();
        for (int[] dir : GameMap.DIRECTIONS) {
            int nr = posR + dir[0];
            int nc = posC + dir[1];
            if (map.isWalkable(nr, nc) && map.get(nr, nc).type != CellType.EXPLOSION) {
                safeDirs.add(dir);
            }
        }

        if (!safeDirs.isEmpty()) {
            return safeDirs.get((int)(Math.random() * safeDirs.size()));
        }

        return new int[]{0, 0}; // 原地不动
    }

    void move(int dr, int dc) {
        int nr = posR + dr;
        int nc = posC + dc;
        if (map.isWalkable(nr, nc)) {
            posR = nr;
            posC = nc;
        }
    }

    int getR() { return posR; }
    int getC() { return posC; }
}

四、玩家策略决策：安全区域评估与炸弹放置

玩家AI需要决定何时放置炸弹、往哪个方向移动。核心策略是：在保证自身安全的前提下，最大化炸毁砖块和消灭敌人的机会。我们通过BFS计算每个格子的”安全时间”——即该格子何时会被爆炸波及：

/**
 * 安全评估引擎
 * 计算地图每个格子的安全状态，辅助AI决策
 */
class SafetyEvaluator {
    private final GameMap map;

    SafetyEvaluator(GameMap map) {
        this.map = map;
    }

    /**
     * 计算安全距离图：每个格子的最近爆炸时间（帧数）
     * 返回二维数组，值越大越安全（Integer.MAX_VALUE表示绝对安全）
     */
    int[][] computeSafetyMap() {
        int rows = map.getRows();
        int cols = map.getCols();
        int[][] safety = new int[rows][cols];
        for (int i = 0; i < rows; i++) {
            Arrays.fill(safety[i], Integer.MAX_VALUE);
        }

        // 遍历所有即将爆炸的炸弹
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                Cell cell = map.get(i, j);
                if (cell.type == CellType.BOMB) {
                    int timeToExplode = cell.bombTimer;

                    // 该炸弹所在位置
                    safety[i][j] = Math.min(safety[i][j], timeToExplode);

                    // 沿四个方向计算波及范围
                    for (int[] dir : GameMap.DIRECTIONS) {
                        for (int step = 1; step <= cell.bombPower; step++) {
                            int ni = i + dir[0] * step;
                            int nj = j + dir[1] * step;
                            if (!map.inBounds(ni, nj)) break;

                            Cell target = map.get(ni, nj);
                            if (target.type == CellType.WALL) break;

                            safety[ni][nj] = Math.min(safety[ni][nj], timeToExplode);

                            if (target.type == CellType.BRICK) break;
                        }
                    }
                }
            }
        }

        return safety;
    }

    /**
     * 判断从指定位置能否在爆炸前到达安全区
     * @param startR 起始行
     * @param startC 起始列
     * @param safetyMap 安全距离图
     * @return 若存在逃生路径返回true
     */
    boolean hasEscapeRoute(int startR, int startC, int[][] safetyMap) {
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[map.getRows()][map.getCols()];
        queue.offer(new int[]{startR, startC, 0}); // {r, c, elapsedTime}
        visited[startR][startC] = true;

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

            // 找到安全区：当前格子不会被爆炸波及，或爆炸时间足够我们离开
            if (safetyMap[r][c] == Integer.MAX_VALUE || safetyMap[r][c] > t + 2) {
                return true;
            }

            for (int[] dir : GameMap.DIRECTIONS) {
                int nr = r + dir[0];
                int nc = c + dir[1];
                int nt = t + 1;

                if (!map.isWalkable(nr, nc) || visited[nr][nc]) continue;
                // 确保移动到这个格子时它还安全
                if (safetyMap[nr][nc] > nt) {
                    visited[nr][nc] = true;
                    queue.offer(new int[]{nr, nc, nt});
                }
            }
        }

        return false;
    }

    /**
     * 评估在指定位置放置炸弹的价值
     * 综合考虑：可炸砖块数、可消灭敌人数、自身安全性
     */
    double evaluateBombPlacement(int r, int c, int power, List<EnemyAI> enemies, int playerR, int playerC) {
        // 模拟放置炸弹后的安全评估
        int[][] simulatedSafety = simulateExplosion(r, c, power);

        // 检查自身是否能逃生
        if (!hasEscapeRoute(playerR, playerC, simulatedSafety)) {
            return Double.NEGATIVE_INFINITY; // 会炸到自己，绝对禁止
        }

        double score = 0;

        // 1. 可炸毁的砖块数（每个+10分）
        for (int i = 0; i < map.getRows(); i++) {
            for (int j = 0; j < map.getCols(); j++) {
                if (simulatedSafety[i][j] < Integer.MAX_VALUE && map.get(i, j).type == CellType.BRICK) {
                    score += 10;
                }
            }
        }

        // 2. 可消灭的敌人（每个+50分）
        for (EnemyAI enemy : enemies) {
            if (simulatedSafety[enemy.getR()][enemy.getC()] < Integer.MAX_VALUE) {
                score += 50;
            }
        }

        // 3. 距离敌人的远近（越近越鼓励放置）
        for (EnemyAI enemy : enemies) {
            int dist = Math.abs(r - enemy.getR()) + Math.abs(c - enemy.getC());
            score += Math.max(0, 20 - dist);
        }

        return score;
    }

    /**
     * 模拟在(r,c)放置威力为power的炸弹后的安全图
     */
    private int[][] simulateExplosion(int r, int c, int power) {
        int rows = map.getRows();
        int cols = map.getCols();
        int[][] sim = new int[rows][cols];
        for (int i = 0; i < rows; i++) Arrays.fill(sim[i], Integer.MAX_VALUE);

        // 假设炸弹3帧后爆炸
        sim[r][c] = 3;
        for (int[] dir : GameMap.DIRECTIONS) {
            for (int step = 1; step <= power; step++) {
                int ni = r + dir[0] * step;
                int nj = c + dir[1] * step;
                if (!map.inBounds(ni, nj)) break;
                if (map.get(ni, nj).type == CellType.WALL) break;
                sim[ni][nj] = 3;
                if (map.get(ni, nj).type == CellType.BRICK) break;
            }
        }
        return sim;
    }
}

五、游戏主循环与完整运行示例

将以上模块整合，我们得到完整的炸弹人游戏引擎：

public class BombermanGame {
    private final GameMap map;
    private final ExplosionEngine explosionEngine;
    private final SafetyEvaluator safetyEvaluator;
    private final List<EnemyAI> enemies;
    private int playerR, playerC;
    private int playerBombPower = 2;
    private boolean gameOver = false;

    public BombermanGame(int rows, int cols) {
        this.map = new GameMap(rows, cols);
        this.explosionEngine = new ExplosionEngine(map);
        this.safetyEvaluator = new SafetyEvaluator(map);
        this.enemies = new ArrayList<>();
        this.playerR = 1;
        this.playerC = 1;

        // 生成敌人
        enemies.add(new EnemyAI(map, rows-2, cols-2));
        enemies.add(new EnemyAI(map, rows-2, 2));
    }

    /**
     * 玩家移动
     */
    void movePlayer(int dr, int dc) {
        int nr = playerR + dr;
        int nc = playerC + dc;
        if (map.isWalkable(nr, nc)) {
            playerR = nr;
            playerC = nc;
        }
    }

    /**
     * 玩家放置炸弹
     */
    void placeBomb() {
        Cell cell = map.get(playerR, playerC);
        if (cell.type == CellType.EMPTY) {
            cell.type = CellType.BOMB;
            cell.bombPower = playerBombPower;
            cell.bombTimer = 60; // 60帧后爆炸（约3秒，假设20FPS）
        }
    }

    /**
     * 玩家AI自动决策：移动或放炸弹
     */
    void playerAutoAct() {
        int[][] safety = safetyEvaluator.computeSafetyMap();

        // 当前位置危险，优先逃跑
        if (safety[playerR][playerC] < Integer.MAX_VALUE && safety[playerR][playerC] < 5) {
            int[] escapeDir = findEscapeDirection(safety);
            if (escapeDir != null) {
                movePlayer(escapeDir[0], escapeDir[1]);
                return;
            }
        }

        // 评估当前位置放炸弹的价值
        double score = safetyEvaluator.evaluateBombPlacement(
            playerR, playerC, playerBombPower, enemies, playerR, playerC);

        if (score > 20) {
            placeBomb();
            // 放完炸弹立即寻找逃生方向
            int[][] newSafety = safetyEvaluator.computeSafetyMap();
            int[] escapeDir = findEscapeDirection(newSafety);
            if (escapeDir != null) {
                movePlayer(escapeDir[0], escapeDir[1]);
            }
        } else {
            // 向最近的敌人移动
            if (!enemies.isEmpty()) {
                EnemyAI target = enemies.get(0);
                int minDist = Math.abs(playerR - target.getR()) + Math.abs(playerC - target.getC());
                for (EnemyAI e : enemies) {
                    int d = Math.abs(playerR - e.getR()) + Math.abs(playerC - e.getC());
                    if (d < minDist) {
                        minDist = d;
                        target = e;
                    }
                }
                int dr = Integer.compare(target.getR(), playerR);
                int dc = Integer.compare(target.getC(), playerC);
                if (dr != 0 && map.isWalkable(playerR + dr, playerC)) {
                    movePlayer(dr, 0);
                } else if (dc != 0 && map.isWalkable(playerR, playerC + dc)) {
                    movePlayer(0, dc);
                }
            }
        }
    }

    /**
     * 寻找最安全的逃跑方向
     */
    private int[] findEscapeDirection(int[][] safety) {
        int bestScore = -1;
        int[] bestDir = null;

        for (int[] dir : GameMap.DIRECTIONS) {
            int nr = playerR + dir[0];
            int nc = playerC + dir[1];
            if (!map.isWalkable(nr, nc)) continue;

            int score = safety[nr][nc];
            if (score == Integer.MAX_VALUE) score = 1000;
            if (score > bestScore) {
                bestScore = score;
                bestDir = dir;
            }
        }

        return bestDir;
    }

    /**
     * 更新一帧
     */
    void update() {
        // 更新炸弹与爆炸
        explosionEngine.updateBombs();

        // 敌人行动
        for (EnemyAI enemy : enemies) {
            int[] move = enemy.decideMove(playerR, playerC);
            enemy.move(move[0], move[1]);
        }

        // 玩家AI自动行动
        playerAutoAct();

        // 碰撞检测
        checkCollisions();
    }

    private void checkCollisions() {
        // 玩家被爆炸击中或碰到敌人
        if (map.get(playerR, playerC).type == CellType.EXPLOSION) {
            gameOver = true;
            return;
        }
        for (EnemyAI enemy : enemies) {
            if (enemy.getR() == playerR && enemy.getC() == playerC) {
                gameOver = true;
                return;
            }
            if (map.get(enemy.getR(), enemy.getC()).type == CellType.EXPLOSION) {
                // 敌人被炸死
            }
        }
    }

    void printMap() {
        for (int i = 0; i < map.getRows(); i++) {
            for (int j = 0; j < map.getCols(); j++) {
                if (i == playerR && j == playerC) {
                    System.out.print("P ");
                } else {
                    boolean isEnemy = false;
                    for (EnemyAI e : enemies) {
                        if (e.getR() == i && e.getC() == j) {
                            isEnemy = true;
                            break;
                        }
                    }
                    if (isEnemy) {
                        System.out.print("E ");
                    } else {
                        switch (map.get(i, j).type) {
                            case WALL: System.out.print("# "); break;
                            case BRICK: System.out.print("B "); break;
                            case BOMB: System.out.print("O "); break;
                            case EXPLOSION: System.out.print("* "); break;
                            default: System.out.print(". ");
                        }
                    }
                }
            }
            System.out.println();
        }
        System.out.println();
    }

    public static void main(String[] args) throws InterruptedException {
        BombermanGame game = new BombermanGame(11, 15);

        System.out.println("=== 炸弹人游戏启动 ===");
        game.printMap();

        // 模拟运行30帧
        for (int frame = 0; frame < 30 && !game.gameOver; frame++) {
            game.update();
            System.out.println("Frame " + (frame + 1) + ":");
            game.printMap();
            Thread.sleep(100);
        }

        System.out.println(game.gameOver ? "游戏结束！" : "模拟结束");
    }
}

六、复杂度分析

七、总结与延伸

本文通过Java实现了炸弹人的核心算法引擎，涵盖了三个关键技术点：

• BFS连锁爆炸传播：通过队列处理炸弹之间的引燃关系，确保连锁反应被正确计算，避免简单递归导致的栈溢出或重复计算。
• A*智能寻路：敌人AI利用A*算法实时追踪玩家位置，并通过动态调整代价函数避开爆炸危险区域，实现有”危机感”的追击行为。
• 安全评估与策略决策：玩家AI通过预计算安全距离图评估局势，只在确保有逃生路径时才放置炸弹，实现攻防兼备的决策逻辑。

延伸方向包括：引入多智能体协同追击策略、使用蒙特卡洛搜索（MCTS）优化炸弹放置的长期收益、以及通过状态压缩动态规划求解特定地图的最优通关路径。