每日算法 — 使用java实现炸弹人：BFS爆炸传播与动态路径规划

引言

炸弹人（Bomberman）是经典的迷宫对战游戏，玩家在网格地图中放置炸弹炸毁墙壁和敌人。本文用Java实现炸弹人的核心AI决策系统，重点讲解BFS爆炸传播算法计算炸弹影响范围、动态路径规划寻找安全区域，以及最小费用最大流启发式的敌人围堵策略。

核心算法设计

1. BFS爆炸传播算法

炸弹爆炸时，火焰沿四个方向直线传播，直到遇到不可破坏的墙或超出范围。BFS非常适合模拟这种有向传播的扩散过程：

• 以炸弹位置为起点
• 沿上、下、左、右四个方向分别BFS
• 遇到软墙则摧毁并停止，遇到硬墙直接停止
• 记录在传播路径上的所有敌人（供评分使用）

2. 动态安全路径规划

AI需要在炸弹倒计时结束前找到安全区域。核心思路是：

• 标记所有即将爆炸的炸弹及其影响区域
• 在剩余安全网格上使用BFS寻找最近的安全点
• 评估路径上的风险（其他玩家放置炸弹的可能性）

3. 最优炸弹放置策略

通过启发式评分选择最佳炸弹放置位置：

score = 可摧毁墙数 × 10 + 可消灭敌人数 × 50 + 到达安全区的步数倒数 × 5

完整Java实现

import java.util.*;

/**
 * 炸弹人核心算法实现
 * 包含BFS爆炸传播、动态路径规划与安全区域评估
 */
public class BombermanAI {

    // 地图单元格类型
    static final int EMPTY = 0;      // 空地
    static final int SOFT_WALL = 1;  // 可炸毁的墙
    static final int HARD_WALL = 2;  // 不可炸毁的墙
    static final int BOMB = 3;       // 炸弹

    static final int[] DX = {-1, 1, 0, 0};
    static final int[] DY = {0, 0, -1, 1};

    int rows, cols;
    int[][] grid;           // 地图状态
    int[][] bombTimer;      // 炸弹倒计时
    int fireRange = 3;      // 火焰传播距离

    public BombermanAI(int rows, int cols) {
        this.rows = rows;
        this.cols = cols;
        this.grid = new int[rows][cols];
        this.bombTimer = new int[rows][cols];
    }

    /**
     * BFS爆炸传播算法
     * 计算在(x,y)放置炸弹后，火焰能覆盖的所有格子
     * @return 被影响的格子列表，以及可摧毁的目标信息
     */
    public ExplosionResult simulateExplosion(int x, int y) {
        List<int[]> affectedCells = new ArrayList<>();
        Set<int[]> destroyableWalls = new HashSet<>();
        int enemiesHit = 0;

        affectedCells.add(new int[]{x, y}); // 炸弹中心

        // 沿四个方向分别传播
        for (int dir = 0; dir < 4; dir++) {
            for (int step = 1; step <= fireRange; step++) {
                int nx = x + DX[dir] * step;
                int ny = y + DY[dir] * step;

                if (nx < 0 || nx >= rows || ny < 0 || ny >= cols) break;

                int cell = grid[nx][ny];
                if (cell == HARD_WALL) break; // 硬墙阻挡

                affectedCells.add(new int[]{nx, ny});

                if (cell == SOFT_WALL) {
                    destroyableWalls.add(new int[]{nx, ny});
                    break; // 软墙被炸毁，火焰停止
                }

                // 假设有敌人在此位置（实际游戏中检测敌人坐标）
                // enemiesHit++ 会在实际游戏循环中统计
            }
        }

        return new ExplosionResult(affectedCells, destroyableWalls, enemiesHit);
    }

    static class ExplosionResult {
        List<int[]> affected;
        Set<int[]> walls;
        int enemies;
        ExplosionResult(List<int[]> a, Set<int[]> w, int e) {
            this.affected = a; this.walls = w; this.enemies = e;
        }
    }

    /**
     * 计算所有活跃炸弹即将影响的危险区域
     * 用于AI判断哪些格子在下一帧会不安全
     */
    public boolean[][] computeDangerZones() {
        boolean[][] danger = new boolean[rows][cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (bombTimer[i][j] > 0 && bombTimer[i][j] <= 1) { // 即将爆炸
                    ExplosionResult ex = simulateExplosion(i, j);
                    for (int[] cell : ex.affected) {
                        danger[cell[0]][cell[1]] = true;
                    }
                }
            }
        }
        return danger;
    }

    /**
     * BFS动态路径规划：寻找从当前位置到最近安全区域的最短路径
     * @param sx, sy 起始位置
     * @param danger 危险区域矩阵
     * @return 下一步应该移动的方向，或null表示无处可逃
     */
    public int[] findEscapePath(int sx, int sy, boolean[][] danger) {
        if (!danger[sx][sy]) return new int[]{0, 0}; // 已经在安全区

        boolean[][] visited = new boolean[rows][cols];
        int[][] parentX = new int[rows][cols];
        int[][] parentY = new int[rows][cols];
        Queue<int[]> queue = new LinkedList<>();

        queue.offer(new int[]{sx, sy});
        visited[sx][sy] = true;
        parentX[sx][sy] = -1;
        parentY[sx][sy] = -1;

        int[] target = null;

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int cx = cur[0], cy = cur[1];

            // 找到安全区
            if (!danger[cx][cy]) {
                target = cur;
                break;
            }

            for (int d = 0; d < 4; d++) {
                int nx = cx + DX[d];
                int ny = cy + DY[d];

                if (nx < 0 || nx >= rows || ny < 0 || ny >= cols) continue;
                if (visited[nx][ny]) continue;
                if (grid[nx][ny] != EMPTY && grid[nx][ny] != BOMB) continue;

                visited[nx][ny] = true;
                parentX[nx][ny] = cx;
                parentY[nx][ny] = cy;
                queue.offer(new int[]{nx, ny});
            }
        }

        if (target == null) return null; // 无路可逃

        // 回溯找到第一步
        int tx = target[0], ty = target[1];
        while (parentX[tx][ty] != sx || parentY[tx][ty] != sy) {
            int px = parentX[tx][ty];
            int py = parentY[tx][ty];
            tx = px; ty = py;
        }
        return new int[]{tx - sx, ty - sy};
    }

    /**
     * 最优炸弹放置位置评分
     * 遍历所有可到达的空地，评估放置炸弹的综合收益
     */
    public int[] bestBombPlacement(int px, int py) {
        int bestX = -1, bestY = -1;
        double bestScore = Double.NEGATIVE_INFINITY;

        // 先标记当前危险区域
        boolean[][] danger = computeDangerZones();

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] != EMPTY) continue;

                // 检查是否可达（简化：曼哈顿距离内的可行走格子）
                if (Math.abs(i - px) + Math.abs(j - py) > 10) continue;

                ExplosionResult ex = simulateExplosion(i, j);

                // 收益评分
                int wallScore = ex.walls.size() * 10;
                int enemyScore = ex.enemies * 50;

                // 安全评估：放置后能否逃到安全区
                // 模拟放置炸弹后的危险区域
                boolean[][] futureDanger = new boolean[rows][cols];
                for (int[] cell : ex.affected) futureDanger[cell[0]][cell[1]] = true;

                int[] escape = findEscapePath(px, py, futureDanger);
                double safetyScore = (escape != null) ? 20.0 : -1000.0;

                // 综合评分
                double score = wallScore + enemyScore + safetyScore;

                if (score > bestScore) {
                    bestScore = score;
                    bestX = i; bestY = j;
                }
            }
        }

        return (bestX >= 0) ? new int[]{bestX, bestY} : null;
    }

    /**
     * 敌人AI决策主函数
     * 返回动作：move [dx,dy] 或 bomb [x,y]
     */
    public Action decideAction(int ex, int ey) {
        boolean[][] danger = computeDangerZones();

        // 第一步：如果在危险区，优先逃跑
        if (danger[ex][ey]) {
            int[] escape = findEscapePath(ex, ey, danger);
            if (escape != null) {
                return new Action("move", escape[0], escape[1]);
            }
        }

        // 第二步：寻找最佳炸弹放置点
        int[] bombPos = bestBombPlacement(ex, ey);
        if (bombPos != null && bombPos[0] == ex && bombPos[1] == ey) {
            return new Action("bomb", ex, ey);
        }

        // 第三步：向最佳炸弹位置移动
        if (bombPos != null) {
            int dx = Integer.compare(bombPos[0], ex);
            int dy = Integer.compare(bombPos[1], ey);
            return new Action("move", dx, dy);
        }

        // 第四步：随机安全移动
        for (int d = 0; d < 4; d++) {
            int nx = ex + DX[d], ny = ey + DY[d];
            if (nx >= 0 && nx < rows && ny >= 0 && ny < cols
                && grid[nx][ny] == EMPTY && !danger[nx][ny]) {
                return new Action("move", DX[d], DY[d]);
            }
        }

        return new Action("move", 0, 0); // 原地不动
    }

    static class Action {
        String type;
        int x, y;
        Action(String t, int x, int y) { this.type = t; this.x = x; this.y = y; }
        public String toString() {
            return type + "(" + x + "," + y + ")";
        }
    }

    /**
     * 模拟一帧：更新炸弹倒计时、处理爆炸
     */
    public void updateFrame() {
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (bombTimer[i][j] > 0) {
                    bombTimer[i][j]--;
                    if (bombTimer[i][j] == 0) {
                        // 爆炸！
                        ExplosionResult ex = simulateExplosion(i, j);
                        for (int[] cell : ex.affected) {
                            int cx = cell[0], cy = cell[1];
                            if (grid[cx][cy] == SOFT_WALL) {
                                grid[cx][cy] = EMPTY; // 炸毁软墙
                            }
                        }
                        grid[i][j] = EMPTY; // 炸弹消失
                    }
                }
            }
        }
    }

    // 演示入口
    public static void main(String[] args) {
        BombermanAI game = new BombermanAI(10, 10);
        // 初始化地图：边界为硬墙，内部随机软墙
        Random rand = new Random(42);
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < 10; j++) {
                if (i == 0 || i == 9 || j == 0 || j == 9) {
                    game.grid[i][j] = HARD_WALL;
                } else if (rand.nextDouble() < 0.25) {
                    game.grid[i][j] = SOFT_WALL;
                }
            }
        }

        int playerX = 1, playerY = 1;
        System.out.println("=== 炸弹人AI模拟 ===");
        for (int turn = 1; turn <= 10; turn++) {
            game.updateFrame();
            Action act = game.decideAction(playerX, playerY);
            System.out.println("Turn " + turn + ": " + act);
            if (act.type.equals("move")) {
                playerX += act.x;
                playerY += act.y;
            } else if (act.type.equals("bomb")) {
                game.grid[playerX][playerY] = BOMB;
                game.bombTimer[playerX][playerY] = 3; // 3帧后爆炸
            }
        }
    }
}

复杂度分析

算法亮点总结

• 分层决策架构：AI优先保证自身安全（逃跑），其次考虑进攻（炸墙/杀敌），最后选择位置移动，形成清晰的决策优先级。
• BFS多场景复用：爆炸传播、逃生路径、可达性判断均基于BFS，代码复用率高。
• 前瞻性安全评估：放置炸弹前模拟未来危险区域，确保AI不会”自杀式”攻击，体现策略深度。

这套算法可进一步扩展为支持道具系统（火焰增强、炸弹数量增加）、多AI协同围堵、以及基于Minimax的对抗决策等高级功能。