每日算法 — 使用java实现冒险岛：A星寻路与动态难度评估

引言

冒险岛是一款经典的横版平台跳跃游戏，玩家控制角色在多层平台上奔跑、跳跃、攀爬，躲避敌人并收集宝物。本文用Java实现冒险岛的核心关卡AI系统，讲解A*寻路算法在平台跳跃场景中的适配、动态难度评估模型以及敌人巡逻路径规划，提供完整的项目代码。

游戏地图建模

节点图表示法

将平台跳跃地图抽象为图结构：

• 节点（Node）：角色可站立的位置（平台表面、梯子顶端、传送点）
• 边（Edge）：节点之间的可达路径，分为三类：
• 水平行走边：同一平台上的左右移动
• 跳跃边：从一个平台跳到另一个平台
• 攀爬边：沿梯子上下移动

public class PlatformNode {
    int id;
    double x, y;           // 节点坐标
    double platformWidth;  // 所在平台宽度
    boolean hasLadder;     // 是否有梯子
    List<Edge> edges;      // 出边列表

    public PlatformNode(int id, double x, double y, double width) {
        this.id = id;
        this.x = x;
        this.y = y;
        this.platformWidth = width;
        this.edges = new ArrayList<>();
    }
}

public class Edge {
    PlatformNode to;
    EdgeType type;      // WALK, JUMP, CLIMB
    double cost;        // 通过耗时或能量消耗
    double jumpPower;   // 跳跃力度（仅JUMP类型）

    public Edge(PlatformNode to, EdgeType type, double cost) {
        this.to = to;
        this.type = type;
        this.cost = cost;
    }
}

A*寻路算法适配

标准A*算法需要适配平台跳跃场景。关键在于设计合理的启发式函数：

public class PlatformAStar {

    /**
     * A*寻路：从起点到终点的最优平台路径
     * 启发式函数综合考虑水平距离、垂直高度差和跳跃难度
     */
    public List<PlatformNode> findPath(PlatformNode start, PlatformNode goal) {
        PriorityQueue<AStarNode> openSet = new PriorityQueue<>();
        Set<PlatformNode> closedSet = new HashSet<>();
        Map<PlatformNode, PlatformNode> cameFrom = new HashMap<>();
        Map<PlatformNode, Double> gScore = new HashMap<>();

        openSet.offer(new AStarNode(start, 0));
        gScore.put(start, 0.0);

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

            if (current.node.id == goal.id) {
                return reconstructPath(cameFrom, current.node);
            }

            closedSet.add(current.node);

            for (Edge edge : current.node.edges) {
                PlatformNode neighbor = edge.to;
                if (closedSet.contains(neighbor)) continue;

                double tentativeG = gScore.getOrDefault(current.node, Double.MAX_VALUE) 
                                    + edge.cost;

                if (tentativeG < gScore.getOrDefault(neighbor, Double.MAX_VALUE)) {
                    cameFrom.put(neighbor, current.node);
                    gScore.put(neighbor, tentativeG);
                    double fScore = tentativeG + heuristic(neighbor, goal);
                    openSet.offer(new AStarNode(neighbor, fScore));
                }
            }
        }

        return Collections.emptyList(); // 无路径
    }

    /**
     * 平台跳跃场景启发式函数
     * 综合考虑：曼哈顿距离 + 高度惩罚 + 跳跃成本估计
     */
    private double heuristic(PlatformNode node, PlatformNode goal) {
        double dx = Math.abs(node.x - goal.x);
        double dy = Math.abs(node.y - goal.y);

        // 基础曼哈顿距离
        double base = dx + dy;

        // 高度惩罚：向上跳跃比向下困难
        double heightPenalty = 0;
        if (goal.y > node.y) {
            heightPenalty = (goal.y - node.y) * 2.0; // 向上移动更耗时
        }

        // 水平跨度过大时需要多次跳跃
        double jumpPenalty = 0;
        if (dx > 200) { // 假设最大跳跃水平距离200像素
            jumpPenalty = (dx / 200.0) * 1.5;
        }

        return base + heightPenalty + jumpPenalty;
    }

    private List<PlatformNode> reconstructPath(Map<PlatformNode, PlatformNode> cameFrom,
                                                PlatformNode current) {
        List<PlatformNode> path = new ArrayList<>();
        path.add(current);
        while (cameFrom.containsKey(current)) {
            current = cameFrom.get(current);
            path.add(0, current);
        }
        return path;
    }
}

跳跃可达性判断

角色能否从平台A跳到平台B是地图构建的关键：

public class JumpCalculator {
    private static final double GRAVITY = 0.5;
    private static final double MAX_H_SPEED = 5.0;  // 最大水平速度
    private static final double MAX_V_SPEED = 12.0; // 最大起跳速度

    /**
     * 判断角色是否能从起点跳到目标平台
     * 使用逆向物理模拟：从目标点倒推可行的起跳速度范围
     */
    public boolean canJumpTo(PlatformNode from, PlatformNode to) {
        double dx = to.x - from.x;
        double dy = to.y - from.y;

        // 简化模型：抛物线运动能否到达
        // y = vy * t - 0.5 * g * t^2, x = vx * t
        // 需要存在 vx ∈ [-MAX_H_SPEED, MAX_H_SPEED], vy ∈ [0, MAX_V_SPEED]

        for (double vx = -MAX_H_SPEED; vx <= MAX_H_SPEED; vx += 0.5) {
            if (Math.abs(vx) < 0.1) continue;

            double t = dx / vx; // 到达水平位置所需时间
            if (t <= 0) continue;

            // 计算到达该水平位置时的垂直速度需求
            double requiredVy = (dy + 0.5 * GRAVITY * t * t) / t;

            if (requiredVy >= 0 && requiredVy <= MAX_V_SPEED) {
                // 检查飞行过程中是否穿过其他平台（简化：只检查最高点）
                double maxHeight = requiredVy * requiredVy / (2 * GRAVITY);
                if (from.y - maxHeight < to.y + 50) { // 不穿过太高的障碍
                    return true;
                }
            }
        }

        return false;
    }

    /**
     * 计算从A到B的最小跳跃成本（能量消耗）
     */
    public double jumpCost(PlatformNode from, PlatformNode to) {
        double dx = Math.abs(to.x - from.x);
        double dy = Math.abs(to.y - from.y);
        return dx * 0.01 + dy * 0.05 + 1.0; // 基础成本 + 距离惩罚
    }
}

动态难度评估

根据玩家当前状态动态调整关卡难度：

public class DynamicDifficulty {

    /**
     * 难度评估模型：综合敌人密度、平台间距、收集品分布
     * @return 难度评分 0.0-1.0
     */
    public double evaluateDifficulty(Level level, PlayerState player) {
        double enemyDensity = level.getEnemyCount() / level.getArea();
        double avgPlatformGap = level.getAveragePlatformGap();
        double collectableRatio = level.getCollectableCount() / (double) level.getTotalItems();

        // 敌人密度权重最高
        double enemyScore = Math.min(enemyDensity * 100, 1.0);

        // 平台间距：间距越大难度越高
        double gapScore = Math.min(avgPlatformGap / 300.0, 1.0);

        // 收集品密度越低越难（需要更多探索）
        double collectScore = 1.0 - Math.min(collectableRatio * 2, 1.0);

        // 根据玩家历史表现调整权重
        double playerSkill = player.getSuccessRate();
        if (playerSkill > 0.8) {
            // 高手：增加平台间距难度
            return enemyScore * 0.3 + gapScore * 0.5 + collectScore * 0.2;
        } else if (playerSkill < 0.4) {
            // 新手：降低敌人密度影响
            return enemyScore * 0.2 + gapScore * 0.3 + collectScore * 0.5;
        }

        return enemyScore * 0.4 + gapScore * 0.35 + collectScore * 0.25;
    }

    /**
     * 根据难度调整敌人巡逻路径
     */
    public void adjustEnemyPatrol(Enemy enemy, double difficulty) {
        double patrolRange = enemy.getBasePatrolRange() * (0.5 + difficulty);
        double patrolSpeed = enemy.getBaseSpeed() * (0.7 + difficulty * 0.6);

        enemy.setPatrolRange(patrolRange);
        enemy.setPatrolSpeed(patrolSpeed);
    }
}

完整项目结构

adventure-island/
├── src/
│   ├── model/
│   │   ├── PlatformNode.java    # 平台节点
│   │   ├── Edge.java            # 路径边
│   │   ├── Enemy.java           # 敌人实体
│   │   └── PlayerState.java     # 玩家状态
│   ├── navigation/
│   │   ├── PlatformAStar.java   # A*寻路
│   │   └── JumpCalculator.java  # 跳跃计算
│   ├── difficulty/
│   │   └── DynamicDifficulty.java # 动态难度
│   └── game/
│       └── LevelGenerator.java  # 关卡生成器
└── Main.java

复杂度分析

总结

本文通过Java实现了冒险岛平台跳跃游戏的核心AI系统。A*寻路算法通过定制化的启发式函数适配平台跳跃场景，跳跃可达性判断基于物理模拟确保路径可行，动态难度评估根据玩家表现实时调整关卡挑战度。这些算法组合可构建出既智能又富有趣味性的横版过关游戏体验。