每日算法 — 使用java实现青蛙过河：A*搜索与曼哈顿距离启发式路径规划

引言

青蛙过河是一款经典的益智游戏：青蛙需要从河岸一侧通过荷叶、石头等落脚点跳跃到对岸。不同落脚点的承载能力不同，有些会下沉，有些会移动。本文用Java实现带AI的青蛙过河游戏，核心采用A*（A-Star）搜索算法，结合曼哈顿距离启发式函数，为青蛙规划最优跳跃路径，同时引入动态风险评估应对荷叶下沉等时变因素。

算法核心思想

A*算法是启发式搜索的经典代表，综合了Dijkstra算法的完备性和贪心策略的高效性：

• 实际代价 g(n)：从起点到当前节点已消耗的步数或能量
• 启发估计 h(n)：从当前节点到目标的预估代价（本文使用曼哈顿距离）
• 综合评估 f(n) = g(n) + h(n)：决定搜索优先级

在青蛙过河场景中，我们额外引入：
– 落脚点稳定性：荷叶下沉概率影响实际通过代价
– 动态重规划：当落脚点状态变化时，从当前位置重新执行A
– 多目标评估*：不仅考虑最短路径，还兼顾安全性与能量消耗

核心数据结构

import java.util.*;

/**
 * A*搜索青蛙过河AI
 */
public class AStarFrogRiver {

    // 游戏区域：20行×15列的河流
    private static final int ROWS = 20;
    private static final int COLS = 15;

    // 地形类型
    private static final int LAND = 0;      // 河岸陆地（起点/终点）
    private static final int WATER = 1;     // 河水（不可站立）
    private static final int LILY_PAD = 2;  // 荷叶（稳定落脚点）
    private static final int STONE = 3;     // 石头（永久落脚点）
    private static final int LOG = 4;       // 木头（顺流移动）
    private static final int TURTLE = 5;    // 乌龟（会潜水）
    private static final int CROC = 6;      // 鳄鱼（危险！）

    // 青蛙跳跃范围（曼哈顿距离）
    private static final int MAX_JUMP = 3;

    // 四个基本方向 + 四个对角线方向
    private static final int[][] DIRECTIONS = {
        {-1,0},{1,0},{0,-1},{0,1},        // 上下左右
        {-1,-1},{-1,1},{1,-1},{1,1}       // 对角线
    };

    private final Random random;
    private int[][] terrain;       // 地形网格
    private double[][] risk;       // 每个格子的风险值(0-1)
    private boolean[][] sinkTimer; // 标记即将下沉的荷叶

    // 青蛙状态
    private int frogRow, frogCol;
    private int targetRow, targetCol;
    private int energy; // 能量值，跳跃消耗能量

    public AStarFrogRiver() {
        this.random = new Random();
        this.terrain = new int[ROWS][COLS];
        this.risk = new double[ROWS][COLS];
        this.sinkTimer = new boolean[ROWS][COLS];
        generateTerrain();
        this.frogRow = 0;
        this.frogCol = COLS / 2;
        this.targetRow = ROWS - 1;
        this.targetCol = COLS / 2;
        this.energy = 100;
    }

    /**
     * A*搜索节点
     */
    static class Node implements Comparable<Node> {
        int row, col;
        double g; // 从起点到当前节点的实际代价
        double h; // 启发式估计到目标的代价
        double f; // g + h
        Node parent;

        Node(int r, int c, double g, double h, Node parent) {
            this.row = r; this.col = c;
            this.g = g; this.h = h;
            this.f = g + h;
            this.parent = parent;
        }

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

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof Node)) return false;
            Node n = (Node) o;
            return row == n.row && col == n.col;
        }

        @Override
        public int hashCode() {
            return row * 31 + col;
        }
    }

地形生成与风险评估

    /**
     * 生成随机河流地形
     * 顶部和底部为陆地，中间为河流混合各种落脚点
     */
    private void generateTerrain() {
        // 起点和终点为陆地
        for (int c = 0; c < COLS; c++) {
            terrain[0][c] = LAND;
            terrain[ROWS - 1][c] = LAND;
        }

        // 中间区域生成河流元素
        for (int r = 1; r < ROWS - 1; r++) {
            for (int c = 0; c < COLS; c++) {
                double rand = random.nextDouble();
                if (rand < 0.3) {
                    terrain[r][c] = LILY_PAD;
                    risk[r][c] = 0.1; // 低风险
                } else if (rand < 0.45) {
                    terrain[r][c] = STONE;
                    risk[r][c] = 0.0; // 无风险
                } else if (rand < 0.55) {
                    terrain[r][c] = LOG;
                    risk[r][c] = 0.05;
                } else if (rand < 0.6) {
                    terrain[r][c] = TURTLE;
                    risk[r][c] = 0.3; // 可能潜水
                } else if (rand < 0.62) {
                    terrain[r][c] = CROC;
                    risk[r][c] = 0.9; // 高风险
                } else {
                    terrain[r][c] = WATER;
                    risk[r][c] = 1.0; // 不可通过
                }
            }
        }

        // 确保起点和终点附近有通路
        ensurePathExists(0, COLS/2, ROWS-1, COLS/2);
    }

    /**
     * 确保存在至少一条可行路径（BFS验证并修补）
     */
    private void ensurePathExists(int sr, int sc, int tr, int tc) {
        while (!hasAnyPath(sr, sc, tr, tc)) {
            // 随机将一些水变成荷叶
            int r = 1 + random.nextInt(ROWS - 2);
            int c = random.nextInt(COLS);
            if (terrain[r][c] == WATER) {
                terrain[r][c] = LILY_PAD;
                risk[r][c] = 0.1;
            }
        }
    }

    /**
     * BFS快速检查是否存在任意路径
     */
    private boolean hasAnyPath(int sr, int sc, int tr, int tc) {
        boolean[][] visited = new boolean[ROWS][COLS];
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{sr, sc});
        visited[sr][sc] = true;

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            if (cur[0] == tr && cur[1] == tc) return true;

            for (int[] dir : DIRECTIONS) {
                for (int jump = 1; jump <= MAX_JUMP; jump++) {
                    int nr = cur[0] + dir[0] * jump;
                    int nc = cur[1] + dir[1] * jump;
                    if (nr < 0 || nr >= ROWS || nc < 0 || nc >= COLS) break;
                    if (visited[nr][nc]) continue;
                    if (terrain[nr][nc] == WATER || terrain[nr][nc] == CROC) continue;
                    visited[nr][nc] = true;
                    queue.add(new int[]{nr, nc});
                }
            }
        }
        return false;
    }

A*搜索核心算法

    /**
     * A*搜索寻找从当前位置到目标的最优路径
     * @return 路径节点列表（从起点到终点），若不可达返回null
     */
    public List<Node> findPath(int startRow, int startCol, int targetRow, int targetCol) {
        PriorityQueue<Node> openSet = new PriorityQueue<>();
        Map<String, Node> openMap = new HashMap<>();
        Set<String> closedSet = new HashSet<>();

        double h0 = heuristic(startRow, startCol, targetRow, targetCol);
        Node start = new Node(startRow, startCol, 0, h0, null);
        openSet.add(start);
        openMap.put(key(startRow, startCol), start);

        while (!openSet.isEmpty()) {
            Node current = openSet.poll();
            openMap.remove(key(current.row, current.col));

            // 到达目标
            if (current.row == targetRow && current.col == targetCol) {
                return reconstructPath(current);
            }

            closedSet.add(key(current.row, current.col));

            // 扩展邻居（考虑不同跳跃距离）
            for (int[] dir : DIRECTIONS) {
                for (int jump = 1; jump <= MAX_JUMP; jump++) {
                    int nr = current.row + dir[0] * jump;
                    int nc = current.col + dir[1] * jump;

                    // 越界检查
                    if (nr < 0 || nr >= ROWS || nc < 0 || nc >= COLS) break;

                    String nKey = key(nr, nc);
                    if (closedSet.contains(nKey)) continue;

                    // 地形可行性检查
                    if (!isPassable(nr, nc)) continue;

                    // 计算实际代价：基础代价 + 跳跃距离代价 + 风险代价
                    double moveCost = calculateMoveCost(current.row, current.col, nr, nc, jump);
                    double tentativeG = current.g + moveCost;

                    Node neighbor = openMap.get(nKey);
                    if (neighbor == null || tentativeG < neighbor.g) {
                        double h = heuristic(nr, nc, targetRow, targetCol);
                        Node newNode = new Node(nr, nc, tentativeG, h, current);
                        if (neighbor != null) {
                            openSet.remove(neighbor);
                        }
                        openSet.add(newNode);
                        openMap.put(nKey, newNode);
                    }
                }
            }
        }

        return null; // 无可行路径
    }

    /**
     * 曼哈顿距离启发式（可采纳且一致）
     */
    private double heuristic(int r1, int c1, int r2, int c2) {
        // 基本曼哈顿距离
        double manhattan = Math.abs(r1 - r2) + Math.abs(c1 - c2);
        // 考虑到青蛙不能走水路，实际距离不会小于曼哈顿距离除以最大跳跃
        return manhattan / MAX_JUMP;
    }

    /**
     * 判断格子是否可通过
     */
    private boolean isPassable(int r, int c) {
        int t = terrain[r][c];
        return t == LAND || t == LILY_PAD || t == STONE || t == LOG || t == TURTLE;
    }

    /**
     * 计算从当前位置移动到目标位置的代价
     */
    private double calculateMoveCost(int fromR, int fromC, int toR, int toC, int jump) {
        double cost = 1.0; // 基础步数代价

        // 跳跃距离惩罚：跳得越远消耗越大
        cost += (jump - 1) * 0.3;

        // 地形风险代价
        cost += risk[toR][toC] * 5.0;

        // 即将下沉的荷叶额外惩罚
        if (sinkTimer[toR][toC]) {
            cost += 3.0;
        }

        // 能量惩罚：鼓励保留能量
        if (energy < 30) {
            cost += jump * 0.5; // 能量低时，远跳更贵
        }

        return cost;
    }

    /**
     * 从终点回溯重建路径
     */
    private List<Node> reconstructPath(Node end) {
        List<Node> path = new ArrayList<>();
        Node current = end;
        while (current != null) {
            path.add(0, current);
            current = current.parent;
        }
        return path;
    }

    private String key(int r, int c) {
        return r + "," + c;
    }

动态环境更新与重规划

    /**
     * 模拟河流环境动态变化
     * 荷叶可能下沉、木头顺流移动、乌龟潜水
     */
    public void updateEnvironment() {
        boolean[][] newSink = new boolean[ROWS][COLS];

        for (int r = 1; r < ROWS - 1; r++) {
            for (int c = 0; c < COLS; c++) {
                switch (terrain[r][c]) {
                    case LILY_PAD:
                        // 10%概率开始下沉倒计时
                        if (!sinkTimer[r][c] && random.nextDouble() < 0.1) {
                            newSink[r][c] = true;
                        } else if (sinkTimer[r][c]) {
                            // 已经标记下沉的，50%概率真的变成水
                            if (random.nextDouble() < 0.5) {
                                terrain[r][c] = WATER;
                                risk[r][c] = 1.0;
                            } else {
                                newSink[r][c] = true;
                            }
                        }
                        break;
                    case LOG:
                        // 木头顺流而下（行号增加）
                        if (random.nextDouble() < 0.3 && r + 1 < ROWS - 1) {
                            // 简化：只在原地做标记，实际移动由渲染处理
                        }
                        break;
                    case TURTLE:
                        // 乌龟随机潜水/浮出水面
                        if (random.nextDouble() < 0.2) {
                            risk[r][c] = (risk[r][c] > 0.5) ? 0.1 : 0.8;
                        }
                        break;
                }
            }
        }
        sinkTimer = newSink;
    }

    /**
     * 青蛙执行AI决策：寻找路径并移动一步
     * @return 是否成功移动或到达终点
     */
    public boolean frogAIStep() {
        // 如果已经到达目标
        if (frogRow == targetRow && frogCol == targetCol) {
            System.out.println("青蛙已成功到达对岸！");
            return false;
        }

        // 执行A*搜索
        List<Node> path = findPath(frogRow, frogCol, targetRow, targetCol);

        if (path == null || path.size() < 2) {
            System.out.println("无可用路径！青蛙被困。");
            return false;
        }

        // 移动到路径的下一个节点
        Node next = path.get(1);
        int jumpDist = Math.abs(next.row - frogRow) + Math.abs(next.col - frogCol);
        energy -= jumpDist * 2;

        frogRow = next.row;
        frogCol = next.col;

        // 检查是否落水（荷叶刚好下沉）
        if (terrain[frogRow][frogCol] == WATER) {
            System.out.println("糟糕！荷叶下沉，青蛙落水了！");
            return false;
        }

        return true;
    }

可视化与主程序

    /**
     * 打印当前游戏画面
     */
    public void printScene() {
        char[][] display = new char[ROWS][COLS];
        for (int r = 0; r < ROWS; r++) {
            for (int c = 0; c < COLS; c++) {
                switch (terrain[r][c]) {
                    case LAND: display[r][c] = '='; break;
                    case WATER: display[r][c] = '~'; break;
                    case LILY_PAD: display[r][c] = sinkTimer[r][c] ? 'x' : 'O'; break;
                    case STONE: display[r][c] = '@'; break;
                    case LOG: display[r][c] = '-'; break;
                    case TURTLE: display[r][c] = 'T'; break;
                    case CROC: display[r][c] = 'C'; break;
                    default: display[r][c] = '?';
                }
            }
        }
        // 绘制青蛙
        display[frogRow][frogCol] = 'F';
        // 绘制目标标记
        if (terrain[targetRow][targetCol] == LAND) {
            display[targetRow][targetCol] = 'G';
        }

        System.out.println("能量: " + energy + "  位置: (" + frogRow + "," + frogCol + ")");
        System.out.println("+" + "-".repeat(COLS) + "+");
        for (int r = 0; r < ROWS; r++) {
            System.out.print("|");
            for (int c = 0; c < COLS; c++) {
                System.out.print(display[r][c]);
            }
            System.out.println("|");
        }
        System.out.println("+" + "-".repeat(COLS) + "+");
        System.out.println();
    }

    /**
     * 预计算并显示完整路径
     */
    public void showPlannedPath() {
        List<Node> path = findPath(frogRow, frogCol, targetRow, targetCol);
        if (path == null) {
            System.out.println("无法找到到达对岸的路径！");
            return;
        }

        char[][] display = new char[ROWS][COLS];
        for (int r = 0; r < ROWS; r++) {
            for (int c = 0; c < COLS; c++) {
                display[r][c] = (terrain[r][c] == WATER) ? '~' : '.';
            }
        }

        // 标记路径
        for (int i = 0; i < path.size(); i++) {
            Node n = path.get(i);
            display[n.row][n.col] = (char)('0' + (i % 10));
        }
        display[frogRow][frogCol] = 'F';
        display[targetRow][targetCol] = 'G';

        System.out.println("=== A*规划路径（共" + (path.size() - 1) + "步） ===");
        for (int r = 0; r < ROWS; r++) {
            for (int c = 0; c < COLS; c++) {
                System.out.print(display[r][c]);
            }
            System.out.println();
        }
    }

    public static void main(String[] args) throws InterruptedException {
        AStarFrogRiver game = new AStarFrogRiver();

        System.out.println("=== A*青蛙过河 ===");
        game.printScene();
        game.showPlannedPath();
        Thread.sleep(1000);

        int step = 0;
        int maxSteps = 200;

        while (step < maxSteps && game.frogAIStep()) {
            step++;
            game.updateEnvironment();
            game.printScene();
            Thread.sleep(300);

            // 环境变化后重新显示路径
            if (step % 5 == 0) {
                game.showPlannedPath();
            }
        }

        System.out.println("游戏结束，共移动 " + step + " 步");
    }
}

算法复杂度分析

A*在最坏情况下等同于BFS（O(V+E)），但在良好启发式引导下，实际搜索节点数远少于网格总数。

优化方向

1. 加权A（Weighted A）：适当放大启发式权重，牺牲最优性换取更快求解
2. ** anytime repairing A（ARA）**：动态调整权重，逐步逼近最优解
3. 跳跃点搜索（JPS）：在均匀代价网格中进一步减少扩展节点
4. 分层导航：先规划粗略路径（大区域），再细化局部移动

总结

A*算法凭借其可采纳的启发式函数，在青蛙过河这类网格路径规划问题中表现出色。曼哈顿距离作为启发式估计，既计算高效又保证不会高估实际代价。通过引入风险评估和动态重规划机制，AI能够应对荷叶下沉、木头漂移等时变因素，在不确定环境中稳健前行。