每日算法 — 使用java实现炸弹人：Flood Fill与爆炸传播范围计算

引言

炸弹人是经典迷宫策略游戏，玩家放置炸弹摧毁砖墙并消灭敌人。本文用Java实现炸弹人的核心算法，重点讲解Flood Fill泛洪填充判断爆炸波及范围，以及BFS+时间轴模拟精确计算炸弹连锁爆炸的时序与伤害判定。

核心算法概览

1. Flood Fill爆炸传播：从炸弹位置向四方向扩散，遇钢墙停止，遇砖墙标记破坏
2. 连锁爆炸时序：被炸弹炸到的其他炸弹会延时引爆，需按时间顺序模拟
3. 安全区域判定：实时计算玩家可站立的安全格子，辅助AI躲避

地图与炸弹实体建模

public class BombMap {
    public static final int EMPTY = 0;  // 空地
    public static final int WALL = 1;   // 钢墙（阻挡爆炸）
    public static final int BRICK = 2;  // 砖墙（可被炸毁）
    public static final int BOMB = 3;   // 炸弹位置

    private int[][] grid;
    private int rows, cols;

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

    public boolean isPassable(int x, int y) {
        if (x < 0 || x >= rows || y < 0 || y >= cols) return false;
        return grid[x][y] == EMPTY || grid[x][y] == BOMB;
    }

    public boolean blocksExplosion(int x, int y) {
        if (x < 0 || x >= rows || y < 0 || y >= cols) return true;
        return grid[x][y] == WALL;
    }

    public boolean isBrick(int x, int y) {
        if (x < 0 || x >= rows || y < 0 || y >= cols) return false;
        return grid[x][y] == BRICK;
    }

    public void destroyBrick(int x, int y) {
        if (isBrick(x, y)) grid[x][y] = EMPTY;
    }

    public void setCell(int x, int y, int val) { grid[x][y] = val; }
    public int getCell(int x, int y) { return grid[x][y]; }
    public int getRows() { return rows; }
    public int getCols() { return cols; }
}

/**
 * 炸弹实体，记录位置和引爆时间
 */
class Bomb {
    int x, y;           // 网格坐标
    int power;          // 爆炸威力（辐射格数）
    long plantTime;     // 放置时间戳(ms)
    long explodeTime;   // 预计引爆时间
    boolean exploded;   // 是否已引爆

    Bomb(int x, int y, int power, long plantTime) {
        this.x = x; this.y = y;
        this.power = power;
        this.plantTime = plantTime;
        this.explodeTime = plantTime + 3000; // 3秒后爆炸
        this.exploded = false;
    }
}

Flood Fill爆炸传播计算

从炸弹位置向上下左右四个方向进行Flood Fill，直到碰到钢墙或超出威力范围。

import java.util.*;

public class ExplosionEngine {

    private static final int[][] DIRS = {{-1,0},{1,0},{0,-1},{0,1}};

    /**
     * 计算单颗炸弹的爆炸影响范围
     * @return 被波及的所有坐标列表（含炸弹自身位置）
     */
    public List<int[]> calculateExplosionRange(BombMap map, Bomb bomb) {
        List<int[]> affected = new ArrayList<>();
        affected.add(new int[]{bomb.x, bomb.y}); // 炸弹中心必然受影响

        for (int[] d : DIRS) {
            for (int step = 1; step <= bomb.power; step++) {
                int nx = bomb.x + d[0] * step;
                int ny = bomb.y + d[1] * step;

                // 钢墙完全阻挡爆炸
                if (map.blocksExplosion(nx, ny)) break;

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

                // 砖墙被炸毁但阻挡后续扩散（爆炸到这里停止）
                if (map.isBrick(nx, ny)) break;
            }
        }

        return affected;
    }

    /**
     * 执行爆炸效果：破坏砖墙、标记炸弹为已爆、返回被触发的其他炸弹
     */
    public List<Bomb> executeExplosion(BombMap map, Bomb bomb, List<Bomb> allBombs) {
        List<Bomb> triggered = new ArrayList<>();
        List<int[]> range = calculateExplosionRange(map, bomb);

        for (int[] pos : range) {
            // 破坏砖墙
            if (map.isBrick(pos[0], pos[1])) {
                map.destroyBrick(pos[0], pos[1]);
            }

            // 检测是否触发其他未爆炸弹（连锁爆炸）
            for (Bomb other : allBombs) {
                if (!other.exploded && other != bomb && 
                    other.x == pos[0] && other.y == pos[1]) {
                    triggered.add(other);
                }
            }
        }

        bomb.exploded = true;
        return triggered;
    }
}

连锁爆炸时序模拟

当炸弹A引爆炸弹B时，B不会立即爆炸，而是有一个极短延时（模拟引线燃烧），需要按时间优先级处理。

import java.util.*;

public class ChainExplosionSimulator {

    private ExplosionEngine engine = new ExplosionEngine();
    private static final long CHAIN_DELAY = 200; // 连锁爆炸延迟200ms

    /**
     * 模拟所有炸弹的爆炸时序
     * @param map 游戏地图
     * @param bombs 地图上所有炸弹
     * @param currentTime 当前时间
     * @return 按时间顺序排列的爆炸事件列表
     */
    public List<ExplosionEvent> simulate(BombMap map, List<Bomb> bombs, long currentTime) {
        // 使用优先队列按爆炸时间排序
        PriorityQueue<Bomb> pq = new PriorityQueue<>(
            Comparator.comparingLong(b -> b.explodeTime));

        for (Bomb b : bombs) {
            if (!b.exploded && b.explodeTime <= currentTime) {
                pq.offer(b);
            }
        }

        List<ExplosionEvent> events = new ArrayList<>();
        Set<Bomb> scheduled = new HashSet<>(pq);

        while (!pq.isEmpty()) {
            Bomb bomb = pq.poll();
            if (bomb.exploded) continue;

            List<Bomb> triggered = engine.executeExplosion(map, bomb, bombs);
            events.add(new ExplosionEvent(bomb.explodeTime, bomb, 
                      engine.calculateExplosionRange(map, bomb)));

            // 被触发的炸弹加入队列，设置延时爆炸时间
            for (Bomb t : triggered) {
                if (!scheduled.contains(t) && !t.exploded) {
                    t.explodeTime = bomb.explodeTime + CHAIN_DELAY;
                    pq.offer(t);
                    scheduled.add(t);
                }
            }
        }

        return events;
    }

    static class ExplosionEvent {
        long time;
        Bomb source;
        List<int[]> range;

        ExplosionEvent(long time, Bomb source, List<int[]> range) {
            this.time = time; this.source = source; this.range = range;
        }
    }
}

安全区域实时判定

玩家和敌人AI需要知道哪些格子在下一时刻是安全的（不会被爆炸波及）。

import java.util.*;

public class SafetyAnalyzer {

    /**
     * 计算指定时刻的所有危险格子
     * @param bombs 所有已放置炸弹
     * @param engine 爆炸引擎
     * @param map 地图
     * @param currentTime 当前时间
     * @return 危险格子的坐标集合
     */
    public Set<String> getDangerZones(BombMap map, List<Bomb> bombs, 
                                       ExplosionEngine engine, long currentTime) {
        Set<String> danger = new HashSet<>();

        for (Bomb bomb : bombs) {
            if (bomb.exploded) continue;
            // 即将爆炸的炸弹（1秒内）
            if (bomb.explodeTime <= currentTime + 1000) {
                List<int[]> range = engine.calculateExplosionRange(map, bomb);
                for (int[] pos : range) {
                    danger.add(pos[0] + "," + pos[1]);
                }
            }
        }

        return danger;
    }

    /**
     * BFS寻找从起点到终点的安全路径（避开危险区域）
     */
    public List<int[]> findSafePath(BombMap map, int[] start, int[] target,
                                    Set<String> dangerZones) {
        int rows = map.getRows();
        int cols = map.getCols();
        boolean[][] visited = new boolean[rows][cols];
        int[][] parent = new int[rows][cols];
        for (int[] row : parent) Arrays.fill(row, -1);

        Queue<int[]> queue = new LinkedList<>();
        queue.offer(start);
        visited[start[0]][start[1]] = true;
        int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};

        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            if (curr[0] == target[0] && curr[1] == target[1]) {
                return reconstructPath(parent, start, target, cols);
            }

            for (int[] d : dirs) {
                int nx = curr[0] + d[0];
                int ny = curr[1] + d[1];
                String key = nx + "," + ny;

                if (map.isPassable(nx, ny) && !visited[nx][ny] && 
                    !dangerZones.contains(key)) {
                    visited[nx][ny] = true;
                    parent[nx][ny] = curr[0] * cols + curr[1];
                    queue.offer(new int[]{nx, ny});
                }
            }
        }

        return new ArrayList<>(); // 无安全路径
    }

    private List<int[]> reconstructPath(int[][] parent, int[] start, int[] target, int cols) {
        List<int[]> path = new LinkedList<>();
        int currIdx = target[0] * cols + target[1];
        int startIdx = start[0] * cols + start[1];
        while (currIdx != startIdx) {
            int x = currIdx / cols;
            int y = currIdx % cols;
            path.add(0, new int[]{x, y});
            currIdx = parent[x][y];
        }
        path.add(0, start);
        return path;
    }
}

敌人AI躲避策略

public class EnemyAI {

    private SafetyAnalyzer safetyAnalyzer = new SafetyAnalyzer();
    private Random random = new Random();

    /**
     * 敌人AI决策：优先躲避爆炸，其次朝玩家移动
     */
    public int[] decideMove(BombMap map, int[] enemyPos, int[] playerPos,
                            List<Bomb> bombs, ExplosionEngine engine, long time) {
        Set<String> danger = safetyAnalyzer.getDangerZones(map, bombs, engine, time);

        // 如果当前位置危险，必须立即离开
        String currentKey = enemyPos[0] + "," + enemyPos[1];
        if (danger.contains(currentKey)) {
            return findEscape(map, enemyPos, danger);
        }

        // 安全时尝试朝玩家移动
        List<int[]> path = safetyAnalyzer.findSafePath(map, enemyPos, playerPos, danger);
        if (!path.isEmpty() && path.size() > 1) {
            return path.get(1); // 返回下一步
        }

        // 无路可走时原地不动
        return enemyPos;
    }

    /**
     * 紧急逃离：找一个相邻的安全格子
     */
    private int[] findEscape(BombMap map, int[] pos, Set<String> danger) {
        int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
        List<int[]> safeMoves = new ArrayList<>();

        for (int[] d : dirs) {
            int nx = pos[0] + d[0];
            int ny = pos[1] + d[1];
            if (map.isPassable(nx, ny) && !danger.contains(nx + "," + ny)) {
                safeMoves.add(new int[]{nx, ny});
            }
        }

        if (!safeMoves.isEmpty()) {
            return safeMoves.get(random.nextInt(safeMoves.size()));
        }
        return pos; // 无处可逃
    }
}

主程序入口

public class BombermanGame {
    public static void main(String[] args) {
        // 11x11地图
        BombMap map = new BombMap(11, 11);

        // 设置钢墙边框
        for (int i = 0; i < 11; i++) {
            map.setCell(0, i, BombMap.WALL);
            map.setCell(10, i, BombMap.WALL);
            map.setCell(i, 0, BombMap.WALL);
            map.setCell(i, 10, BombMap.WALL);
        }

        // 设置内部砖墙和钢墙
        map.setCell(2, 2, BombMap.BRICK);
        map.setCell(2, 3, BombMap.BRICK);
        map.setCell(3, 2, BombMap.BRICK);
        map.setCell(5, 5, BombMap.WALL);
        map.setCell(5, 6, BombMap.WALL);

        long now = System.currentTimeMillis();
        List<Bomb> bombs = new ArrayList<>();
        bombs.add(new Bomb(3, 3, 2, now)); // 威力2的炸弹
        bombs.add(new Bomb(3, 5, 2, now)); // 威力2的炸弹，将被连锁引爆

        ExplosionEngine engine = new ExplosionEngine();
        ChainExplosionSimulator simulator = new ChainExplosionSimulator();

        // 模拟爆炸
        List<ChainExplosionSimulator.ExplosionEvent> events = 
            simulator.simulate(map, bombs, now + 3000);

        System.out.println("爆炸事件数：" + events.size());
        for (ChainExplosionSimulator.ExplosionEvent e : events) {
            System.out.println("炸弹(" + e.source.x + "," + e.source.y + 
                             ") 在 t=" + e.time + " 爆炸，波及 " + e.range.size() + " 格");
        }
    }
}

复杂度分析

总结

本文以炸弹人游戏为载体，深入讲解了Flood Fill在爆炸传播中的应用、基于优先队列的连锁爆炸时序模拟，以及结合BFS的安全路径规划。读者可以扩展：
– 实现道具系统（增加炸弹威力、加速移动等）
– 加入多敌人协同AI，使用A*寻找最优追击路径
– 实现精确的碰撞框检测，支持更细腻的角色移动