每日算法 — 使用java实现合金弹头：有限状态机敌人AI与A*寻路策略

引言

合金弹头（Metal Slug）是经典的横版射击游戏，其敌人AI系统虽然看似简单，却蕴含了丰富的算法设计：敌人需要根据玩家位置决策巡逻、追击、攻击和躲避，在复杂地形中寻找可行路径。本文将用Java实现一个简化版的合金弹头敌人AI系统，深入讲解有限状态机（FSM）的行为控制、A*寻路在平台地形中的应用，以及视线检测与射击决策算法。

一、游戏世界建模

1.1 地图与地形表示

使用二维网格表示游戏世界，每个格子可以是空地、墙壁、平台或梯子。

1.2 实体系统设计

游戏中有两类主要实体：玩家（Player）和敌人（Enemy）。敌人AI需要实时感知玩家位置、地形信息和自身状态，做出合理的行动决策。

二、Java核心实现

import java.util.*;

/**
 * 地形类型枚举
 */
enum TerrainType {
    EMPTY(0),   // 空地
    WALL(1),    // 墙壁（不可通过）
    PLATFORM(2),// 平台（可站立）
    LADDER(3),  // 梯子（可攀爬）
    WATER(4);   // 水域（减速）

    final int value;
    TerrainType(int value) { this.value = value; }
}

/**
 * 游戏世界坐标点
 */
class GamePoint {
    int x, y;

    public GamePoint(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof GamePoint)) return false;
        GamePoint p = (GamePoint) o;
        return x == p.x && y == p.y;
    }

    @Override
    public int hashCode() {
        return x * 31 + y;
    }

    @Override
    public String toString() {
        return "(" + x + "," + y + ")";
    }

    public int distanceTo(GamePoint other) {
        return Math.abs(x - other.x) + Math.abs(y - other.y);
    }
}

/**
 * 游戏地图类
 */
public class GameMap {
    private final int width;
    private final int height;
    private final TerrainType[][] grid;

    public GameMap(int width, int height) {
        this.width = width;
        this.height = height;
        this.grid = new TerrainType[height][width];
        // 默认全部为空地
        for (int y = 0; y < height; y++) {
            Arrays.fill(grid[y], TerrainType.EMPTY);
        }
    }

    public void setTerrain(int x, int y, TerrainType type) {
        if (isValid(x, y)) {
            grid[y][x] = type;
        }
    }

    public TerrainType getTerrain(int x, int y) {
        if (!isValid(x, y)) return TerrainType.WALL;
        return grid[y][x];
    }

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

    /**
     * 检查点是否可通过（敌人可站立的位置）
     * 规则：下方必须有平台或墙壁支撑
     */
    public boolean isWalkable(int x, int y) {
        if (!isValid(x, y)) return false;
        if (grid[y][x] == TerrainType.WALL) return false;
        // 下方必须有支撑（平台或墙壁）
        if (y + 1 < height && (grid[y + 1][x] == TerrainType.PLATFORM || 
                               grid[y + 1][x] == TerrainType.WALL)) {
            return true;
        }
        // 或者在梯子上
        return grid[y][x] == TerrainType.LADDER;
    }

    /**
     * 检查是否可以跳跃到达（简化：检查目标下方是否有支撑）
     */
    public boolean isJumpLanding(int x, int y) {
        return isValid(x, y) && isValid(x, y + 1) && 
               (grid[y + 1][x] == TerrainType.PLATFORM || grid[y + 1][x] == TerrainType.WALL);
    }

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

    /**
     * 打印地图（调试用）
     */
    public void print() {
        for (int y = 0; y < height; y++) {
            for (int x = 0; x < width; x++) {
                switch (grid[y][x]) {
                    case WALL: System.out.print("#"); break;
                    case PLATFORM: System.out.print("="); break;
                    case LADDER: System.out.print("H"); break;
                    case WATER: System.out.print("~"); break;
                    default: System.out.print("."); break;
                }
            }
            System.out.println();
        }
    }
}

/**
 * 玩家类
 */
class Player {
    GamePoint position;
    int health;
    boolean isAlive;

    public Player(int x, int y) {
        this.position = new GamePoint(x, y);
        this.health = 100;
        this.isAlive = true;
    }

    public void moveTo(int x, int y) {
        position.x = x;
        position.y = y;
    }
}

/**
 * 敌人AI状态枚举
 */
enum EnemyState {
    IDLE("待机"),           // 原地巡逻
    PATROL("巡逻"),         // 在区域内移动
    ALERT("警戒"),          // 发现异常，准备搜索
    CHASE("追击"),          // 追踪玩家
    ATTACK("攻击"),         // 在射程内射击
    RETREAT("撤退"),        // 血量低时撤退
    DEAD("死亡");           // 死亡状态

    final String description;
    EnemyState(String desc) { this.description = desc; }
}

/**
 * 敌人AI类
 * 使用有限状态机控制行为
 */
public class EnemyAI {
    private GamePoint position;
    private int health;
    private EnemyState currentState;
    private final GameMap map;
    private final Player player;

    // AI参数
    private final int viewRange;      // 视野范围
    private final int attackRange;    // 攻击范围
    private final int patrolRange;    // 巡逻范围
    private final GamePoint spawnPoint; // 出生点

    // 状态机相关
    private int stateTimer;           // 状态持续时间计时器
    private GamePoint patrolTarget;   // 巡逻目标点
    private List<GamePoint> path;     // 当前路径
    private int pathIndex;            // 路径当前索引
    private int lastPlayerX;          // 上次看到玩家的位置
    private int lastPlayerY;

    public EnemyAI(int x, int y, GameMap map, Player player,
                   int viewRange, int attackRange, int patrolRange) {
        this.position = new GamePoint(x, y);
        this.spawnPoint = new GamePoint(x, y);
        this.health = 100;
        this.currentState = EnemyState.IDLE;
        this.map = map;
        this.player = player;
        this.viewRange = viewRange;
        this.attackRange = attackRange;
        this.patrolRange = patrolRange;
        this.stateTimer = 0;
        this.path = new ArrayList<>();
        this.pathIndex = 0;
        this.lastPlayerX = -1;
        this.lastPlayerY = -1;
    }

    /**
     * 每帧更新AI状态和行为
     */
    public void update() {
        if (currentState == EnemyState.DEAD) return;

        stateTimer++;

        // 状态转换决策
        EnemyState nextState = decideNextState();
        if (nextState != currentState) {
            onStateExit(currentState);
            currentState = nextState;
            onStateEnter(currentState);
        }

        // 执行当前状态行为
        executeCurrentState();
    }

    /**
     * 决策下一状态（状态机核心）
     */
    private EnemyState decideNextState() {
        if (health <= 0) return EnemyState.DEAD;
        if (health < 30 && currentState != EnemyState.RETREAT) return EnemyState.RETREAT;

        boolean canSeePlayer = canSeePlayer();
        int distToPlayer = position.distanceTo(player.position);

        switch (currentState) {
            case IDLE:
                if (canSeePlayer) return EnemyState.CHASE;
                if (stateTimer > 60) return EnemyState.PATROL; // 2秒后切换到巡逻
                return EnemyState.IDLE;

            case PATROL:
                if (canSeePlayer) return EnemyState.CHASE;
                if (stateTimer > 180) return EnemyState.IDLE; // 6秒后休息
                return EnemyState.PATROL;

            case ALERT:
                if (canSeePlayer) return EnemyState.CHASE;
                if (stateTimer > 120) return EnemyState.PATROL; // 4秒后放弃搜索
                return EnemyState.ALERT;

            case CHASE:
                if (!canSeePlayer && stateTimer > 90) return EnemyState.ALERT;
                if (distToPlayer <= attackRange) return EnemyState.ATTACK;
                return EnemyState.CHASE;

            case ATTACK:
                if (!canSeePlayer) return EnemyState.ALERT;
                if (distToPlayer > attackRange) return EnemyState.CHASE;
                return EnemyState.ATTACK;

            case RETREAT:
                if (health > 50) return EnemyState.PATROL;
                return EnemyState.RETREAT;

            default:
                return currentState;
        }
    }

    /**
     * 进入状态时的初始化
     */
    private void onStateEnter(EnemyState state) {
        stateTimer = 0;
        path.clear();
        pathIndex = 0;

        switch (state) {
            case PATROL:
                // 随机选择巡逻目标
                patrolTarget = generatePatrolTarget();
                path = findPath(position, patrolTarget);
                break;
            case CHASE:
                // 记录玩家位置并开始追击
                lastPlayerX = player.position.x;
                lastPlayerY = player.position.y;
                path = findPath(position, player.position);
                break;
            case ALERT:
                // 移动到上次看到玩家的位置
                if (lastPlayerX >= 0) {
                    path = findPath(position, new GamePoint(lastPlayerX, lastPlayerY));
                }
                break;
            case RETREAT:
                // 撤退到出生点
                path = findPath(position, spawnPoint);
                break;
            default:
                break;
        }
    }

    private void onStateExit(EnemyState state) {
        // 状态退出时的清理工作
    }

    /**
     * 执行当前状态的具体行为
     */
    private void executeCurrentState() {
        switch (currentState) {
            case IDLE:
                // 待机：原地左右张望
                break;

            case PATROL:
                followPath();
                // 到达目标后选择新目标
                if (pathIndex >= path.size()) {
                    patrolTarget = generatePatrolTarget();
                    path = findPath(position, patrolTarget);
                    pathIndex = 0;
                }
                break;

            case CHASE:
                // 每30帧重新计算路径（玩家可能移动）
                if (stateTimer % 30 == 0) {
                    path = findPath(position, player.position);
                    pathIndex = 0;
                }
                followPath();
                break;

            case ATTACK:
                // 攻击玩家
                performAttack();
                break;

            case RETREAT:
                followPath();
                break;

            default:
                break;
        }
    }

    /**
     * 沿当前路径移动
     */
    private void followPath() {
        if (path == null || pathIndex >= path.size()) return;

        GamePoint nextStep = path.get(pathIndex);
        if (canMoveTo(nextStep.x, nextStep.y)) {
            position.x = nextStep.x;
            position.y = nextStep.y;
            pathIndex++;
        }
    }

    /**
     * 检查是否可以移动到目标位置
     */
    private boolean canMoveTo(int x, int y) {
        return map.isWalkable(x, y);
    }

    /**
     * 执行攻击
     */
    private void performAttack() {
        // 简化的攻击逻辑：检查射击线是否通畅
        if (hasClearShot()) {
            System.out.println("Enemy at " + position + " attacks Player at " + player.position);
            // 实际游戏中这里会减少玩家血量
        }
    }

    /**
     * 视线检测：使用Bresenham直线算法检查是否能直接看到玩家
     */
    private boolean canSeePlayer() {
        int dist = position.distanceTo(player.position);
        if (dist > viewRange) return false;

        return hasLineOfSight(position.x, position.y, player.position.x, player.position.y);
    }

    /**
     * Bresenham直线算法检测视线
     */
    private boolean hasLineOfSight(int x0, int y0, int x1, int y1) {
        int dx = Math.abs(x1 - x0);
        int dy = Math.abs(y1 - y0);
        int sx = x0 < x1 ? 1 : -1;
        int sy = y0 < y1 ? 1 : -1;
        int err = dx - dy;

        while (true) {
            // 检查当前点是否被墙壁阻挡
            if (map.getTerrain(x0, y0) == TerrainType.WALL) {
                return false;
            }

            if (x0 == x1 && y0 == y1) break;

            int e2 = 2 * err;
            if (e2 > -dy) {
                err -= dy;
                x0 += sx;
            }
            if (e2 < dx) {
                err += dx;
                y0 += sy;
            }
        }

        return true;
    }

    /**
     * 检查是否有清晰的射击线
     */
    private boolean hasClearShot() {
        return hasLineOfSight(position.x, position.y, player.position.x, player.position.y);
    }

    /**
     * 生成随机巡逻目标
     */
    private GamePoint generatePatrolTarget() {
        Random rand = new Random();
        int attempts = 0;
        while (attempts < 20) {
            int nx = spawnPoint.x + rand.nextInt(patrolRange * 2 + 1) - patrolRange;
            int ny = spawnPoint.y + rand.nextInt(patrolRange * 2 + 1) - patrolRange;
            if (map.isWalkable(nx, ny)) {
                return new GamePoint(nx, ny);
            }
            attempts++;
        }
        return spawnPoint;
    }

    /**
     * A*寻路算法
     */
    private List<GamePoint> findPath(GamePoint start, GamePoint goal) {
        PriorityQueue<AStarNode2> openSet = new PriorityQueue<>();
        Set<GamePoint> closedSet = new HashSet<>();
        Map<GamePoint, Double> gScore = new HashMap<>();

        openSet.add(new AStarNode2(start, 0, heuristic(start, goal), null));
        gScore.put(start, 0.0);

        // 四方向 + 下方向（掉落）+ 上方向（跳跃）
        int[][] directions = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};

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

            if (current.point.equals(goal)) {
                return reconstructPath(current);
            }

            closedSet.add(current.point);

            for (int[] dir : directions) {
                int nx = current.point.x + dir[0];
                int ny = current.point.y + dir[1];
                GamePoint neighbor = new GamePoint(nx, ny);

                if (closedSet.contains(neighbor)) continue;
                if (!canMoveTo(nx, ny)) continue;

                double tentativeG = current.g + 1;

                if (!gScore.containsKey(neighbor) || tentativeG < gScore.get(neighbor)) {
                    gScore.put(neighbor, tentativeG);
                    double h = heuristic(neighbor, goal);
                    openSet.add(new AStarNode2(neighbor, tentativeG, h, current));
                }
            }
        }

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

    private double heuristic(GamePoint a, GamePoint b) {
        return Math.abs(a.x - b.x) + Math.abs(a.y - b.y);
    }

    private List<GamePoint> reconstructPath(AStarNode2 endNode) {
        List<GamePoint> path = new ArrayList<>();
        AStarNode2 current = endNode;
        while (current != null) {
            path.add(current.point);
            current = current.parent;
        }
        Collections.reverse(path);
        return path;
    }

    // Getters
    public GamePoint getPosition() { return position; }
    public EnemyState getState() { return currentState; }
    public int getHealth() { return health; }
    public void takeDamage(int dmg) { health -= dmg; }
}

/**
 * A*寻路节点（内部类）
 */
class AStarNode2 implements Comparable<AStarNode2> {
    GamePoint point;
    double g, h;
    AStarNode2 parent;

    AStarNode2(GamePoint point, double g, double h, AStarNode2 parent) {
        this.point = point;
        this.g = g;
        this.h = h;
        this.parent = parent;
    }

    double getF() { return g + h; }

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

三、游戏主循环与测试

/**
 * 合金弹头AI演示主程序
 */
public class MetalSlugAIApp {
    public static void main(String[] args) {
        // 创建地图
        GameMap map = new GameMap(20, 10);

        // 构建平台地形
        for (int x = 0; x < 20; x++) {
            map.setTerrain(x, 9, TerrainType.PLATFORM); // 地面
        }
        // 中层平台
        for (int x = 3; x < 8; x++) map.setTerrain(x, 5, TerrainType.PLATFORM);
        for (int x = 12; x < 17; x++) map.setTerrain(x, 5, TerrainType.PLATFORM);
        // 顶层平台
        for (int x = 6; x < 14; x++) map.setTerrain(x, 2, TerrainType.PLATFORM);

        // 梯子
        map.setTerrain(5, 6, TerrainType.LADDER);
        map.setTerrain(5, 7, TerrainType.LADDER);
        map.setTerrain(5, 8, TerrainType.LADDER);
        map.setTerrain(13, 3, TerrainType.LADDER);
        map.setTerrain(13, 4, TerrainType.LADDER);
        map.setTerrain(13, 5, TerrainType.LADDER);
        map.setTerrain(13, 6, TerrainType.LADDER);
        map.setTerrain(13, 7, TerrainType.LADDER);
        map.setTerrain(13, 8, TerrainType.LADDER);

        System.out.println("游戏地图：");
        map.print();

        // 创建玩家和敌人
        Player player = new Player(2, 8);
        EnemyAI enemy = new EnemyAI(17, 8, map, player, 10, 3, 5);

        System.out.println("\n===== AI行为模拟 =====");
        System.out.println("初始状态：");
        System.out.println("  玩家位置: " + player.position);
        System.out.println("  敌人位置: " + enemy.getPosition());
        System.out.println("  敌人状态: " + enemy.getState().description);

        // 模拟游戏循环
        System.out.println("\n模拟60帧游戏循环：");
        for (int frame = 0; frame < 60; frame++) {
            // 玩家移动（模拟）
            if (frame == 15) {
                player.moveTo(8, 8);
                System.out.println("\n[第" + frame + "帧] 玩家移动到 " + player.position);
            }
            if (frame == 30) {
                player.moveTo(10, 4);
                System.out.println("\n[第" + frame + "帧] 玩家移动到 " + player.position);
            }
            if (frame == 45) {
                player.moveTo(5, 4);
                System.out.println("\n[第" + frame + "帧] 玩家移动到 " + player.position);
            }

            // 更新敌人AI
            EnemyState prevState = enemy.getState();
            enemy.update();

            // 状态变化时输出信息
            if (enemy.getState() != prevState || frame % 15 == 0) {
                System.out.println("[第" + frame + "帧] 敌人状态: " + enemy.getState().description + 
                                 ", 位置: " + enemy.getPosition());
            }
        }

        // 测试视线检测
        System.out.println("\n===== 视线检测测试 =====");
        player.moveTo(10, 8);
        enemy = new EnemyAI(15, 8, map, player, 10, 3, 5);
        System.out.println("玩家: " + player.position + ", 敌人: " + enemy.getPosition());
        System.out.println("敌人能看到玩家: " + enemy.canSeePlayer());

        // 添加墙壁阻挡视线
        map.setTerrain(12, 8, TerrainType.WALL);
        map.setTerrain(12, 7, TerrainType.WALL);
        System.out.println("\n添加墙壁后：");
        System.out.println("敌人能看到玩家: " + enemy.canSeePlayer());
    }
}

四、算法分析

五、总结与扩展

本文实现了一个完整的横版射击游戏敌人AI系统，涵盖有限状态机行为控制、A寻路、视线检测等核心算法。状态机使敌人行为逻辑清晰可维护，A确保敌人能智能地在复杂地形中追踪玩家。

扩展方向：
1. 行为树：用行为树替代状态机，实现更复杂的决策逻辑
2. 群体AI：多个敌人之间的协作与包抄策略
3. 学习AI：使用Q-Learning让敌人学习玩家行为模式
4. 完整物理：加入重力、跳跃轨迹预测，实现更真实的平台移动