每日算法 — 使用java实现青蛙过河：BFS时空调度与动态规划风险决策

青蛙过河（Frogger）是街机黄金时代的经典之作。一只青蛙需要从屏幕底部穿越繁忙的车流与湍急的河流，最终到达对岸的安全区域。游戏中的车辆与木头随时间不断移动，使得每一时刻的”安全区”都在动态变化。这种时变环境为路径规划算法提出了独特的挑战。本文将带你用 Java 实现一个具备 AI 决策能力的青蛙过河程序，重点讲解时空 BFS 与动态规划（DP）在动态障碍物场景中的综合运用。

一、问题建模：时变环境中的决策空间

与传统静态迷宫不同，青蛙过河的核心难点在于环境随时间变化。车辆在马路上匀速横移，木头在河流中漂流，青蛙必须在正确的时间出现在正确的位置。

我们将游戏场景抽象为一个二维网格，每一行代表不同的地形：

1.1 核心数据结构

/**
 * 地形类型枚举
 */
public enum TerrainType {
    SAFE_ZONE,    // 安全区（起点、终点、中间安全岛）
    ROAD,         // 马路
    RIVER         // 河流
}

/**
 * 移动物体：车辆或木头
 */
public class MovingObject {
    private final int row;          // 所在行
    private final int length;       // 占据长度（格数）
    private final int speed;        // 每回合移动格数（正=右，负=左）
    private int headPosition;       // 头部当前列坐标

    public MovingObject(int row, int length, int speed, int startCol) {
        this.row = row;
        this.length = length;
        this.speed = speed;
        this.headPosition = startCol;
    }

    /**
     * 模拟前进一个时间步，更新位置
     */
    public void tick(int gridWidth) {
        headPosition += speed;
        // 循环边界处理：超出屏幕则从另一侧进入
        if (speed > 0 && headPosition >= gridWidth) {
            headPosition = -length + 1;
        } else if (speed < 0 && headPosition + length - 1 < 0) {
            headPosition = gridWidth - 1;
        }
    }

    /**
     * 判断某列在当前时刻是否被该物体占据
     */
    public boolean occupies(int col, int gridWidth) {
        // 处理循环边界下的占据判断
        for (int i = 0; i < length; i++) {
            int occupiedCol = normalize(headPosition + i, gridWidth);
            if (occupiedCol == col) return true;
        }
        return false;
    }

    private int normalize(int col, int width) {
        return ((col % width) + width) % width;
    }

    public int getRow() { return row; }
}

/**
 * 位置记录
 */
public record Position(int x, int y) {
    public Position add(int dx, int dy) {
        return new Position(x + dx, y + dy);
    }
}

1.2 游戏网格

import java.util.*;

public class FroggerGrid {
    private final int width;
    private final int height;
    private final TerrainType[] rows;           // 每行的地形类型
    private final List<MovingObject> objects;     // 所有移动物体

    public FroggerGrid(int width, int height, TerrainType[] rows) {
        this.width = width;
        this.height = height;
        this.rows = rows;
        this.objects = new ArrayList<>();
    }

    public void addObject(MovingObject obj) {
        objects.add(obj);
    }

    /**
     * 获取指定行在指定时刻被移动物体占据的列集合
     */
    public Set<Integer> getOccupiedColsAtTime(int row, int time) {
        Set<Integer> occupied = new HashSet<>();
        // 先模拟 time 步后的物体位置（为了性能可预计算）
        for (MovingObject obj : objects) {
            if (obj.getRow() != row) continue;
            // 计算 time 步后的位置（此处简化处理，实际应在时间维度预计算）
            int simulatedHead = simulatePosition(obj, time);
            for (int i = 0; i < obj.length(); i++) {
                occupied.add(normalize(simulatedHead + i, width));
            }
        }
        return occupied;
    }

    private int simulatePosition(MovingObject obj, int time) {
        // 基于初始位置和速度计算
        return obj.getHeadPosition() + obj.getSpeed() * time;
    }

    private int normalize(int col, int width) {
        return ((col % width) + width) % width;
    }

    public boolean isValid(int x, int y) {
        return x >= 0 && x < width && y >= 0 && y < height;
    }

    public TerrainType getTerrain(int y) {
        return rows[y];
    }

    public int getWidth() { return width; }
    public int getHeight() { return height; }
}

二、动态规划：预计算时空安全性

在动态环境中，某个格子此刻安全不代表下一刻安全。我们用动态规划预计算每个时空坐标的安全性，为后续的 BFS 提供 O(1) 查询能力。

2.1 安全状态定义

• 马路上的格子：当且仅当该时刻没有车辆占据时安全
• 河流上的格子：当且仅当该时刻有木头/乌龟承载时安全
• 安全区：始终安全

2.2 DP 预计算实现

/**
 * 时空安全表：DP[t][y][x] 表示时刻 t、位置 (x,y) 是否安全
 */
public class SafetyDP {
    private final boolean[][][] safeTable;  // [time][y][x]
    private final int maxTime;
    private final int period;                // 环境循环周期（用于压缩）

    public SafetyDP(FroggerGrid grid, int maxTime) {
        this.maxTime = maxTime;
        this.period = computePeriod(grid);
        // 实际存储只需一个周期
        this.safeTable = new boolean[period][grid.getHeight()][grid.getWidth()];
        precompute(grid);
    }

    /**
     * 计算环境循环周期（所有移动物体位置同时重复的最小时间）
     * 对于匀速直线运动，周期 = LCM(width/|speed|) for all objects
     */
    private int computePeriod(FroggerGrid grid) {
        // 简化：假设所有速度互质，周期为网格宽度
        // 实际游戏中可针对速度计算最小公倍数
        return grid.getWidth() * 2;
    }

    private void precompute(FroggerGrid grid) {
        int w = grid.getWidth();
        int h = grid.getHeight();

        for (int t = 0; t < period; t++) {
            // 计算时刻 t 所有移动物体的位置
            Map<Integer, Set<Integer>> rowOccupied = new HashMap<>();
            Map<Integer, Set<Integer>> rowWoods = new HashMap<>();

            for (MovingObject obj : grid.getObjects()) {
                int row = obj.getRow();
                rowOccupied.computeIfAbsent(row, k -> new HashSet<>());
                rowWoods.computeIfAbsent(row, k -> new HashSet<>());

                int pos = obj.getHeadPosition() + obj.getSpeed() * t;
                for (int i = 0; i < obj.length(); i++) {
                    int col = ((pos + i) % w + w) % w;
                    if (grid.getTerrain(row) == TerrainType.ROAD) {
                        rowOccupied.get(row).add(col);  // 车辆占据
                    } else if (grid.getTerrain(row) == TerrainType.RIVER) {
                        rowWoods.get(row).add(col);     // 木头可承载
                    }
                }
            }

            // 填充安全表
            for (int y = 0; y < h; y++) {
                for (int x = 0; x < w; x++) {
                    TerrainType terrain = grid.getTerrain(y);
                    if (terrain == TerrainType.SAFE_ZONE) {
                        safeTable[t][y][x] = true;
                    } else if (terrain == TerrainType.ROAD) {
                        safeTable[t][y][x] = !rowOccupied.getOrDefault(y, Set.of()).contains(x);
                    } else { // RIVER
                        safeTable[t][y][x] = rowWoods.getOrDefault(y, Set.of()).contains(x);
                    }
                }
            }
        }
    }

    /**
     * 查询时空安全性（利用周期性取模）
     */
    public boolean isSafe(int x, int y, int time) {
        if (!gridBoundsCheck(x, y)) return false;
        int t = time % period;
        return safeTable[t][y][x];
    }

    private boolean gridBoundsCheck(int x, int y) {
        return x >= 0 && x < safeTable[0][0].length && y >= 0 && y < safeTable[0].length;
    }
}

2.3 DP 复杂度分析

• 时间复杂度：O(period × H × W + period × O)，其中 O 为移动物体数量
• 空间复杂度：O(period × H × W)
• 查询复杂度：O(1)

对于标准游戏场景（宽度 15~20，周期 30~40），这一开销完全可以接受。

三、时空 BFS：在四维状态空间中寻路

传统 BFS 在静态图上搜索，而青蛙过河需要在时空状态图上搜索。每个状态为 (x, y, t)，表示青蛙在时刻 t 位于 (x, y)。

3.1 状态转移

从状态 (x, y, t)，青蛙有 5 种选择：
1. 等待（留在原地）：(x, y, t+1)
2. 向上（前进）：(x, y-1, t+1)
3. 向下（后退）：(x, y+1, t+1)
4. 向左：(x-1, y, t+1)
5. 向右：(x+1, y, t+1)

每一步消耗 1 个时间单位，且目标位置在 t+1 时刻必须安全。

3.2 BFS 核心实现

import java.util.*;

/**
 * 时空 BFS 寻路器
 */
public class SpatioTemporalBFS {
    private final SafetyDP safetyDP;
    private final int gridWidth;
    private final int gridHeight;
    private final int maxSearchTime;  // 最大搜索深度，防止无限搜索

    public SpatioTemporalBFS(SafetyDP safetyDP, int width, int height, int maxSearchTime) {
        this.safetyDP = safetyDP;
        this.gridWidth = width;
        this.gridHeight = height;
        this.maxSearchTime = maxSearchTime;
    }

    /**
     * 搜索从起点到目标区域的安全路径
     * @param start 起始位置
     * @param goalY 目标行（顶部安全区）
     * @return 动作序列（UP/DOWN/LEFT/RIGHT/WAIT），为空表示无路可逃
     */
    public List<Action> findPath(Position start, int goalY) {
        // 访问标记：避免重复访问同一时空状态
        boolean[][][] visited = new boolean[maxSearchTime + 1][gridHeight][gridWidth];
        // 前驱记录：用于路径重建
        Map<State, State> cameFrom = new HashMap<>();
        Map<State, Action> actionTo = new HashMap<>();

        Queue<State> queue = new LinkedList<>();
        State initial = new State(start.x(), start.y(), 0);
        queue.add(initial);
        visited[0][start.y()][start.x()] = true;

        while (!queue.isEmpty()) {
            State current = queue.poll();

            // 到达目标
            if (current.y == goalY) {
                return reconstructPath(cameFrom, actionTo, current);
            }

            // 超过最大搜索时间
            if (current.time >= maxSearchTime) continue;

            // 扩展 5 种动作
            for (Action action : Action.values()) {
                int nx = current.x + action.dx;
                int ny = current.y + action.dy;
                int nt = current.time + 1;

                // 边界检查
                if (nx < 0 || nx >= gridWidth || ny < 0 || ny >= gridHeight) continue;

                // 时空安全性检查 + 未访问检查
                if (safetyDP.isSafe(nx, ny, nt) && !visited[nt][ny][nx]) {
                    visited[nt][ny][nx] = true;
                    State next = new State(nx, ny, nt);
                    queue.add(next);
                    cameFrom.put(next, current);
                    actionTo.put(next, action);
                }
            }
        }

        return Collections.emptyList(); // 无路可逃
    }

    private List<Action> reconstructPath(Map<State, State> cameFrom,
                                          Map<State, Action> actionTo,
                                          State goal) {
        LinkedList<Action> path = new LinkedList<>();
        State current = goal;
        while (cameFrom.containsKey(current)) {
            path.addFirst(actionTo.get(current));
            current = cameFrom.get(current);
        }
        return path;
    }

    /**
     * 时空状态记录
     */
    private record State(int x, int y, int time) {}

    /**
     * 青蛙动作枚举
     */
    public enum Action {
        WAIT(0, 0),
        UP(0, -1),
        DOWN(0, 1),
        LEFT(-1, 0),
        RIGHT(1, 0);

        public final int dx, dy;
        Action(int dx, int dy) {
            this.dx = dx;
            this.dy = dy;
        }
    }
}

3.3 时空 BFS 的关键优化

/**
 * 带启发式剪枝的时空搜索（A* 变体）
 * 使用曼哈顿距离作为启发函数，加速搜索
 */
public class HeuristicSpatioTemporalSearch extends SpatioTemporalBFS {
    private final int goalY;

    public HeuristicSpatioTemporalSearch(SafetyDP safetyDP, int width, int height,
                                          int maxSearchTime, int goalY) {
        super(safetyDP, width, height, maxSearchTime);
        this.goalY = goalY;
    }

    /**
     * 带启发式的 A* 搜索替代纯 BFS
     * f(n) = g(n) + h(n)，其中 g=已耗时间，h=估计还需时间
     */
    public List<Action> findPathAStar(Position start, int goalY) {
        PriorityQueue<Node> openSet = new PriorityQueue<>(
            Comparator.comparingInt(n -> n.fScore)
        );
        boolean[][][] visited = new boolean[maxSearchTime + 1][gridHeight][gridWidth];

        Node startNode = new Node(start.x(), start.y(), 0, 0, heuristic(start.y()));
        openSet.add(startNode);

        Map<State, State> cameFrom = new HashMap<>();
        Map<State, Action> actionTo = new HashMap<>();

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

            if (current.y == goalY) {
                return reconstructPath(cameFrom, actionTo,
                    new State(current.x, current.y, current.time));
            }

            if (current.time >= maxSearchTime) continue;
            if (visited[current.time][current.y][current.x]) continue;
            visited[current.time][current.y][current.x] = true;

            for (Action action : Action.values()) {
                int nx = current.x + action.dx;
                int ny = current.y + action.dy;
                int nt = current.time + 1;

                if (nx < 0 || nx >= gridWidth || ny < 0 || ny >= gridHeight) continue;
                if (!safetyDP.isSafe(nx, ny, nt) || visited[nt][ny][nx]) continue;

                int gScore = nt;
                int hScore = heuristic(ny);
                openSet.add(new Node(nx, ny, nt, gScore, gScore + hScore));

                State nextState = new State(nx, ny, nt);
                cameFrom.put(nextState, new State(current.x, current.y, current.time));
                actionTo.put(nextState, action);
            }
        }
        return Collections.emptyList();
    }

    /**
     * 启发函数：估计从当前行到达目标行的最少步数
     */
    private int heuristic(int currentY) {
        return Math.abs(currentY - goalY);
    }

    private record Node(int x, int y, int time, int gScore, int fScore) {}
}

四、完整 AI 决策引擎

将 DP 安全评估与 BFS 路径规划封装为统一的决策引擎：

/**
 * 青蛙过河 AI 决策引擎
 */
public class FroggerAI {
    private final FroggerGrid grid;
    private final SafetyDP safetyDP;
    private final SpatioTemporalBFS bfs;
    private final int goalY;

    public FroggerAI(FroggerGrid grid, int maxSearchTime) {
        this.grid = grid;
        this.safetyDP = new SafetyDP(grid, maxSearchTime);
        this.bfs = new SpatioTemporalBFS(safetyDP, grid.getWidth(),
                                          grid.getHeight(), maxSearchTime);
        this.goalY = 0; // 假设顶部（y=0）为目标
    }

    /**
     * 根据当前状态决定下一步动作
     * @param frogPos 青蛙当前位置
     * @param currentTime 当前游戏时间
     * @return 推荐动作
     */
    public SpatioTemporalBFS.Action decide(Position frogPos, int currentTime) {
        // 策略1：执行已规划路径的下一步
        List<SpatioTemporalBFS.Action> plannedPath = bfs.findPath(frogPos, goalY);
        if (!plannedPath.isEmpty()) {
            return plannedPath.get(0);
        }

        // 策略2：路径规划失败时的紧急避险
        return emergencyEvade(frogPos, currentTime);
    }

    /**
     * 紧急避险策略：当 BFS 找不到完整路径时的局部最优选择
     * 选择能让青蛙存活最久的方向
     */
    private SpatioTemporalBFS.Action emergencyEvade(Position pos, int time) {
        SpatioTemporalBFS.Action bestAction = SpatioTemporalBFS.Action.WAIT;
        int maxSurvival = -1;

        for (SpatioTemporalBFS.Action action : SpatioTemporalBFS.Action.values()) {
            int nx = pos.x() + action.dx;
            int ny = pos.y() + action.dy;

            if (nx < 0 || nx >= grid.getWidth() || ny < 0 || ny >= grid.getHeight())
                continue;

            // 评估选择该动作后的预期存活时间
            int survival = evaluateSurvival(nx, ny, time + 1);
            if (survival > maxSurvival) {
                maxSurvival = survival;
                bestAction = action;
            }
        }
        return bestAction;
    }

    /**
     * 动态规划评估：从 (x,y,t) 出发最多能存活多少步
     * 使用记忆化搜索实现
     */
    private int evaluateSurvival(int x, int y, int time) {
        // 简化版：检查接下来几个时间步是否安全
        int survival = 0;
        for (int dt = 0; dt < 20; dt++) {
            if (safetyDP.isSafe(x, y, time + dt)) {
                survival++;
            } else {
                break;
            }
        }
        return survival;
    }
}

五、可运行的游戏主程序

/**
 * 青蛙过河游戏主类（控制台版本）
 */
public class FroggerGame {
    private static final int WIDTH = 15;
    private static final int HEIGHT = 12;
    private static final int MAX_TIME = 200;

    private final FroggerGrid grid;
    private final FroggerAI ai;
    private Position frog;
    private int time;
    private boolean gameOver;
    private boolean won;

    public FroggerGame() {
        // 初始化地形：安全区-马路-河流-安全岛-马路-河流-终点
        TerrainType[] rows = {
            TerrainType.SAFE_ZONE,  // 0: 终点
            TerrainType.RIVER,      // 1: 河流（木头向右）
            TerrainType.RIVER,      // 2: 河流（木头向左）
            TerrainType.SAFE_ZONE,  // 3: 中间安全岛
            TerrainType.ROAD,       // 4: 马路（车辆向左）
            TerrainType.ROAD,       // 5: 马路（车辆向右）
            TerrainType.SAFE_ZONE,  // 6: 中间安全岛
            TerrainType.RIVER,      // 7: 河流
            TerrainType.RIVER,      // 8: 河流
            TerrainType.ROAD,       // 9: 马路
            TerrainType.ROAD,       // 10: 马路
            TerrainType.SAFE_ZONE   // 11: 起点
        };

        this.grid = new FroggerGrid(WIDTH, HEIGHT, rows);
        initObjects();
        this.ai = new FroggerAI(grid, MAX_TIME);
        this.frog = new Position(WIDTH / 2, HEIGHT - 1);
        this.time = 0;
    }

    private void initObjects() {
        // 河流木头（承载青蛙）
        grid.addObject(new MovingObject(1, 3, 1, 0));   // row=1, len=3, 向右
        grid.addObject(new MovingObject(1, 2, 1, 7));
        grid.addObject(new MovingObject(2, 3, -1, 5));  // row=2, 向左
        grid.addObject(new MovingObject(2, 2, -1, 12));
        grid.addObject(new MovingObject(7, 3, 1, 2));
        grid.addObject(new MovingObject(8, 2, -1, 8));

        // 马路车辆（危险）
        grid.addObject(new MovingObject(4, 2, -1, 3));
        grid.addObject(new MovingObject(4, 2, -1, 10));
        grid.addObject(new MovingObject(5, 2, 1, 0));
        grid.addObject(new MovingObject(5, 2, 1, 6));
        grid.addObject(new MovingObject(9, 2, -1, 2));
        grid.addObject(new MovingObject(10, 2, 1, 4));
    }

    /**
     * 执行一步游戏循环
     */
    public void step() {
        if (gameOver) return;

        // AI 决策
        SpatioTemporalBFS.Action action = ai.decide(frog, time);
        frog = frog.add(action.dx, action.dy);

        // 移动所有物体
        for (MovingObject obj : grid.getObjects()) {
            obj.tick(WIDTH);
        }

        time++;

        // 胜负判定
        if (frog.y() == 0) {
            won = true;
            gameOver = true;
        } else if (!isFrogSafe()) {
            gameOver = true;
        }
    }

    private boolean isFrogSafe() {
        int x = frog.x();
        int y = frog.y();
        TerrainType terrain = grid.getTerrain(y);

        if (terrain == TerrainType.SAFE_ZONE) return true;

        // 检查是否有移动物体占据青蛙位置
        for (MovingObject obj : grid.getObjects()) {
            if (obj.getRow() == y && obj.occupies(x, WIDTH)) {
                if (terrain == TerrainType.ROAD) {
                    return false; // 被车撞
                } else if (terrain == TerrainType.RIVER) {
                    return true;  // 站在木头上
                }
            }
        }

        // 河流上没有被木头占据 → 落水
        return terrain != TerrainType.RIVER;
    }

    public boolean isGameOver() { return gameOver; }
    public boolean isWon() { return won; }
    public Position getFrog() { return frog; }
    public int getTime() { return time; }

    public static void main(String[] args) {
        FroggerGame game = new FroggerGame();
        int maxSteps = 150;

        System.out.println("=== 青蛙过河 AI 演示 ===");
        while (!game.isGameOver() && game.getTime() < maxSteps) {
            game.step();
        }

        if (game.isWon()) {
            System.out.println("青蛙成功到达对岸！用时：" + game.getTime() + " 步");
        } else {
            System.out.println("青蛙牺牲了... 存活时间：" + game.getTime() + " 步");
        }
    }
}

六、项目结构

frogger-ai/
├── src/
│   ├── model/
│   │   ├── TerrainType.java
│   │   ├── MovingObject.java
│   │   └── Position.java
│   ├── algorithm/
│   │   ├── SafetyDP.java
│   │   ├── SpatioTemporalBFS.java
│   │   └── FroggerAI.java
│   └── game/
│       └── FroggerGame.java
└── README.md

七、算法复杂度与策略效果对比

关键洞察

1. 时空状态图的大小为 T × H × W。对于 15×12 的网格、200 步上限，状态总数约为 36,000，现代计算机可在毫秒级完成搜索。

2. 周期性压缩将 DP 表从 O(T×H×W) 降低到 O(P×H×W)，其中 P 为环境周期（通常 ≤ 40），大幅节省内存。

3. 启发式 A* 相比纯 BFS 通常能减少 30%~50% 的搜索节点数，尤其是在目标明确的纵向穿越场景中。

八、扩展方向

• 多青蛙协同：引入多个青蛙，使用多智能体路径规划（MAPF）避免碰撞
• 强化学习：用 Q-Learning 替代规则式 AI，从大量对局中学习最优策略
• 视觉增强：接入 JavaFX 或 Swing 实现图形化界面，实时展示时空安全热区

九、总结

本文实现了一个基于 时空 BFS 与 动态规划 的青蛙过河 AI。核心思路可归纳为三步：

1. 建模：将动态环境抽象为时空状态图，每个状态包含 (x, y, t) 三维信息
2. 预计算：用 DP 在周期维度预计算每个时空坐标的安全性，支持 O(1) 查询
3. 搜索：在时空状态图上执行 BFS（或 A*），寻找从起点到终点的最短安全路径

这套框架不仅适用于青蛙过河，还可推广到一切时变环境中的路径规划问题，如自动驾驶中的动态避障、机器人调度中的时序约束等。