每日算法 — 使用java实现炸弹人：BFS爆炸范围传播与最短路径逃离策略

引言

炸弹人（Bomberman）是一款经典的策略动作游戏。玩家在二维网格中放置炸弹，利用爆炸清除障碍物和敌人，同时需要保证自身安全。本文将用Java实现一个带AI的炸弹人核心逻辑，重点讲解BFS爆炸范围传播算法计算炸弹影响区域，以及A*最短路径算法帮助玩家规划安全撤离路线。

问题建模

将游戏地图抽象为二维网格，每个格子有以下几种状态：
– EMPTY（空地）：可以自由移动和放置炸弹
– WALL（固定墙）：不可破坏，阻挡爆炸
– BLOCK（可破坏障碍）：可以被炸弹炸毁
– BOMB（炸弹）：倒计时后爆炸
– PLAYER（玩家）与 ENEMY（敌人）

爆炸沿四个方向（上下左右）传播，遇到墙或边界停止，遇到可破坏障碍则炸毁该障碍并停止传播。

核心算法一：BFS爆炸范围传播

炸弹爆炸时，需要快速计算其影响范围。采用BFS从炸弹位置向四个方向扩散，直到遇到阻挡物。

import java.util.*;

public class BombermanGame {
    // 地图状态常量
    public static final int EMPTY = 0;
    public static final int WALL = 1;    // 固定墙，不可破坏
    public static final int BLOCK = 2;   // 可破坏障碍
    public static final int BOMB = 3;    // 炸弹

    private int rows, cols;
    private int[][] grid;
    private int bombRange; // 炸弹爆炸半径

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

    /**
     * 使用BFS计算炸弹爆炸的影响范围
     * @param bombRow 炸弹行坐标
     * @param bombCol 炸弹列坐标
     * @return 所有会被爆炸波及的位置集合
     */
    public Set<Position> calculateExplosionRange(int bombRow, int bombCol) {
        Set<Position> affected = new HashSet<>();
        Queue<ExplosionWave> queue = new LinkedList<>();

        // 四个方向向量
        int[][] dirs = {{-1,0}, {1,0}, {0,-1}, {0,1}};

        // 初始状态：从炸弹位置向四个方向发射冲击波
        affected.add(new Position(bombRow, bombCol));
        for (int d = 0; d < 4; d++) {
            queue.offer(new ExplosionWave(bombRow, bombCol, d, 0));
        }

        while (!queue.isEmpty()) {
            ExplosionWave wave = queue.poll();
            int nextRow = wave.row + dirs[wave.dir][0];
            int nextCol = wave.col + dirs[wave.dir][1];
            int nextDist = wave.dist + 1;

            // 边界检查
            if (nextRow < 0 || nextRow >= rows || nextCol < 0 || nextCol >= cols) {
                continue;
            }
            // 超出爆炸半径
            if (nextDist > bombRange) {
                continue;
            }

            affected.add(new Position(nextRow, nextCol));
            int cell = grid[nextRow][nextCol];

            if (cell == WALL) {
                // 固定墙阻挡爆炸传播
                continue;
            } else if (cell == BLOCK) {
                // 可破坏障碍被炸毁，爆炸停止
                continue;
            } else {
                // 空地或炸弹，爆炸继续沿原方向传播
                queue.offer(new ExplosionWave(nextRow, nextCol, wave.dir, nextDist));
            }
        }
        return affected;
    }

    // 爆炸冲击波：记录当前位置、传播方向和已传播距离
    static class ExplosionWave {
        int row, col, dir, dist;
        ExplosionWave(int r, int c, int d, int dist) {
            this.row = r; this.col = c; this.dir = d; this.dist = dist;
        }
    }

    static class Position {
        int row, col;
        Position(int r, int c) { this.row = r; this.col = c; }
        @Override public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof Position)) return false;
            Position p = (Position) o;
            return row == p.row && col == p.col;
        }
        @Override public int hashCode() { return row * 131 + col; }
    }
}

BFS爆炸传播的时间复杂度为 O(4 × R)，其中 R 为爆炸半径。由于只有四个方向，实际运算量很小。

核心算法二：A*最短路径逃离策略

当玩家放置炸弹后，需要在爆炸倒计时结束前移动到安全区域。A*算法结合曼哈顿距离启发式函数，可以快速找到最短逃生路径。

    /**
     * A*寻路：从当前位置找到离炸弹爆炸范围最远的安全位置
     * @param startRow 玩家当前行
     * @param startCol 玩家当前列
     * @param dangerZone 炸弹爆炸影响范围
     * @return 安全撤离路径，若无处可逃返回空列表
     */
    public List<Position> findEscapePath(int startRow, int startCol, 
                                          Set<Position> dangerZone) {
        PriorityQueue<AStarNode> open = new PriorityQueue<>(
            Comparator.comparingInt(n -> n.f)
        );
        boolean[][] closed = new boolean[rows][cols];
        Map<Position, Position> parent = new HashMap<>();
        Map<Position, Integer> gScore = new HashMap<>();

        Position start = new Position(startRow, startCol);
        open.offer(new AStarNode(start, 0, heuristic(start, dangerZone)));
        gScore.put(start, 0);

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

        while (!open.isEmpty()) {
            AStarNode current = open.poll();
            Position currPos = current.pos;

            if (closed[currPos.row][currPos.col]) continue;
            closed[currPos.row][currPos.col] = true;

            // 找到安全位置：不在爆炸范围内且是空地
            if (!dangerZone.contains(currPos) && 
                grid[currPos.row][currPos.col] == EMPTY) {
                return reconstructPath(parent, currPos);
            }

            for (int[] d : dirs) {
                int nr = currPos.row + d[0];
                int nc = currPos.col + d[1];
                Position next = new Position(nr, nc);

                if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
                if (closed[nr][nc]) continue;
                if (grid[nr][nc] == WALL || grid[nr][nc] == BLOCK) continue;

                int tentativeG = gScore.getOrDefault(currPos, Integer.MAX_VALUE) + 1;
                if (tentativeG < gScore.getOrDefault(next, Integer.MAX_VALUE)) {
                    parent.put(next, currPos);
                    gScore.put(next, tentativeG);
                    int h = heuristic(next, dangerZone);
                    open.offer(new AStarNode(next, tentativeG, tentativeG + h));
                }
            }
        }
        return Collections.emptyList(); // 无路可逃
    }

    /**
     * 启发式函数：计算到最近危险格子的曼哈顿距离的相反数
     * 越远离爆炸范围，启发值越小（优先级越高）
     */
    private int heuristic(Position pos, Set<Position> dangerZone) {
        int minDist = Integer.MAX_VALUE;
        for (Position d : dangerZone) {
            int dist = Math.abs(pos.row - d.row) + Math.abs(pos.col - d.col);
            minDist = Math.min(minDist, dist);
        }
        return -minDist; // 负数使得远离危险区的节点优先级更高
    }

    private List<Position> reconstructPath(Map<Position, Position> parent, 
                                            Position goal) {
        List<Position> path = new ArrayList<>();
        Position curr = goal;
        while (curr != null) {
            path.add(curr);
            curr = parent.get(curr);
        }
        Collections.reverse(path);
        return path;
    }

    static class AStarNode {
        Position pos;
        int g, f;
        AStarNode(Position p, int g, int f) {
            this.pos = p; this.g = g; this.f = f;
        }
    }

完整演示与复杂度分析

将上述模块整合后，玩家AI的决策流程为：
1. 扫描地图寻找可破坏障碍密集区域
2. 计算放置炸弹后的BFS爆炸范围
3. 在爆炸倒计时内使用A*找到最短逃生路径
4. 若逃生路径长度 < 倒计时步数，则执行投放

其中 R 为炸弹半径，V 为地图可通行格子数。在标准 13×15 的炸弹人地图中，A*通常只需访问少量节点即可找到安全位置。

总结

炸弹人游戏的AI核心在于危险预判与路径规划的平衡。BFS负责精确计算爆炸的物理影响范围，A*则负责在倒计时约束下寻找最优逃生路线。两种算法的结合使AI玩家能够在复杂地图中做出既激进又安全的战术决策。