每日算法 — 使用java实现格斗游戏：帧数据最优决策与有限状态机博弈

游戏简介

格斗游戏（Fighting Game）是电子竞技中最考验反应与策略的类型之一。在经典格斗游戏中，每个角色拥有站立、下蹲、跳跃、攻击、防御等多种状态，每种状态都有特定的持续时间（以帧为单位）。高手对决往往取决于对帧数据的精确掌握——知道哪一帧可以反击、哪一帧处于硬直。本文用Java实现格斗游戏AI的核心决策系统，讲解有限状态机建模与帧数据驱动的最优决策算法。

核心算法思路

有限状态机建模

将格斗角色的行为抽象为有限状态机（FSM）：

• 状态：待机(Idle)、前移(WalkForward)、后移(WalkBackward)、下蹲(Crouch)、跳跃(Jump)、轻拳(LightPunch)、重拳(HeavyPunch)、防御(Block)、受击(Hit)、硬直(Stun)等
• 转移条件：玩家输入、帧计数归零、碰撞检测等
• 帧数据：每个状态有总帧数、活跃帧（可造成伤害的帧数）、硬直帧等属性

帧数据决策算法

AI的核心决策逻辑基于帧数据：

1. 有利帧计算：我方攻击命中后，对方进入硬直，计算我方可以行动的先机帧数
2. ** punish 窗口识别**：对方攻击被防御后，对方有多少帧处于不利状态
3. 最优连段选择：在有利帧窗口内，选择伤害最高且能稳定连接的招式组合
4. 防御决策：当对方处于攻击活跃帧范围内，选择防御或闪避

Java实现

import java.util.*;

/**
 * 格斗游戏AI - 帧数据最优决策与有限状态机
 */
public class FightingGameAI {

    // 角色状态枚举
    enum State {
        IDLE, WALK_FORWARD, WALK_BACKWARD, CROUCH,
        JUMP, LIGHT_PUNCH, HEAVY_PUNCH, BLOCK, HIT, STUN
    }

    // 招式帧数据结构
    static class Move {
        String name;
        int startupFrames;    // 发生帧（出手前）
        int activeFrames;     // 活跃帧（可造成伤害）
        int recoveryFrames;   // 收招硬直帧
        int damage;           // 伤害值
        int hitStun;          // 命中对方造成的硬直
        int blockStun;        // 被防御时对方硬直
        boolean isLow;        // 是否下段攻击

        int totalFrames() {
            return startupFrames + activeFrames + recoveryFrames;
        }

        // 命中后的有利帧 = 对方硬直 - 我方剩余收招帧
        int advantageOnHit() {
            return hitStun - recoveryFrames;
        }

        // 被防御后的有利帧（负值表示不利）
        int advantageOnBlock() {
            return blockStun - recoveryFrames;
        }
    }

    // 角色
    static class Fighter {
        State state = State.IDLE;
        int stateFrame = 0;       // 当前状态已持续帧数
        int hp = 1000;
        int x = 0;                // 位置坐标
        boolean isPlayer = false; // 是否为玩家控制
        List<Move> moves = new ArrayList<>();

        Fighter(boolean isPlayer) {
            this.isPlayer = isPlayer;
            initMoves();
        }

        void initMoves() {
            // 初始化角色招式库
            moves.add(new Move() {{
                name = "轻拳"; startupFrames = 3; activeFrames = 2;
                recoveryFrames = 6; damage = 30; hitStun = 12; blockStun = 8;
                isLow = false;
            }});
            moves.add(new Move() {{
                name = "重拳"; startupFrames = 8; activeFrames = 3;
                recoveryFrames = 15; damage = 80; hitStun = 22; blockStun = 14;
                isLow = false;
            }});
            moves.add(new Move() {{
                name = "下轻脚"; startupFrames = 4; activeFrames = 2;
                recoveryFrames = 8; damage = 25; hitStun = 10; blockStun = 7;
                isLow = true;
            }});
            moves.add(new Move() {{
                name = "升龙拳"; startupFrames = 2; activeFrames = 4;
                recoveryFrames = 20; damage = 120; hitStun = 30; blockStun = 18;
                isLow = false;
            }});
        }
    }

    private Fighter player;
    private Fighter ai;
    private int distance; // 双方距离
    private Random rand = new Random(123);

    public FightingGameAI() {
        player = new Fighter(true);
        ai = new Fighter(false);
        player.x = -100;
        ai.x = 100;
        distance = 200;
    }

    /**
     * AI决策主函数，每帧调用
     * @return AI选择的招式名称，null表示不行动
     */
    public String makeDecision() {
        // 分析当前局势
        boolean playerAttacking = isAttacking(player);
        boolean aiInAdvantage = isInAdvantage(ai, player);

        // 决策优先级：punish > 连段 > 防守 > 拉近距离

        // 1. Punish窗口：对方处于不利状态，使用高伤害招式
        if (player.state == State.STUN || player.state == State.RECOVERY) {
            Move punish = findBestPunishMove(ai);
            if (punish != null) return punish.name;
        }

        // 2. 对方正在攻击中，判断是否需要防御
        if (playerAttacking && willHitPlayer(player, ai)) {
            if (shouldBlock(ai, player)) {
                return "防御";
            }
        }

        // 3. 处于有利状态，尝试连段
        if (aiInAdvantage) {
            Move combo = findBestComboMove(ai, player);
            if (combo != null) return combo.name;
        }

        // 4. 距离管理
        if (distance > 150) {
            return "前移";
        } else if (distance < 80) {
            return "后移";
        }

        // 5. 默认：试探性轻攻击
        Move poke = findBestPokeMove(ai);
        if (poke != null && rand.nextDouble() < 0.3) {
            return poke.name;
        }

        return "待机";
    }

    /**
     * 判断角色是否处于攻击状态
     */
    private boolean isAttacking(Fighter f) {
        return f.state == State.LIGHT_PUNCH || f.state == State.HEAVY_PUNCH;
    }

    /**
     * 判断攻击是否会命中目标
     */
    private boolean willHitPlayer(Fighter attacker, Fighter defender) {
        if (!isAttacking(attacker)) return false;
        // 简化判定：在攻击活跃帧内且距离足够
        Move move = attacker.moves.get(0); // 简化处理
        int activeStart = move.startupFrames;
        int activeEnd = activeStart + move.activeFrames;
        boolean inActive = attacker.stateFrame >= activeStart 
                        && attacker.stateFrame < activeEnd;
        return inActive && distance < 120;
    }

    /**
     * 判断AI是否处于有利状态
     */
    private boolean isInAdvantage(Fighter self, Fighter opponent) {
        // 简化：如果对手处于硬直而我方可行动
        return (opponent.state == State.HIT || opponent.state == State.STUN)
                && (self.state == State.IDLE || self.state == State.WALK_FORWARD);
    }

    /**
     * 寻找最佳punish招式（高伤害、能在窗口内命中）
     */
    private Move findBestPunishMove(Fighter f) {
        Move best = null;
        int maxDamage = 0;
        for (Move m : f.moves) {
            // 估算对方剩余硬直帧
            int opponentStunRemaining = 15; // 简化假设
            if (m.startupFrames < opponentStunRemaining && m.damage > maxDamage) {
                best = m;
                maxDamage = m.damage;
            }
        }
        return best;
    }

    /**
     * 寻找最佳连段招式（能接续当前状态的招式）
     */
    private Move findBestComboMove(Fighter self, Fighter opponent) {
        Move best = null;
        double bestScore = -1;
        for (Move m : self.moves) {
            // 评分：伤害/帧数比，有利帧越高越好
            double score = (double) m.damage / m.totalFrames();
            if (m.advantageOnHit() > 5) score *= 1.5; // 能继续连段的奖励
            if (score > bestScore) {
                best = m;
                bestScore = score;
            }
        }
        return best;
    }

    /**
     * 判断是否应当防御
     */
    private boolean shouldBlock(Fighter self, Fighter opponent) {
        // 如果对方攻击活跃帧即将到达且无法反击
        if (self.state != State.IDLE && self.state != State.WALK_FORWARD 
                && self.state != State.WALK_BACKWARD) {
            return true; // 无法做其他动作，只能防御
        }
        // 如果反应时间足够，尝试升龙（对空）反击
        for (Move m : self.moves) {
            if (m.name.equals("升龙拳") && m.startupFrames <= 3) {
                return false; // 可以反击，不防御
            }
        }
        return true;
    }

    /**
     * 寻找最佳试探招式（发生快、破绽小）
     */
    private Move findBestPokeMove(Fighter f) {
        Move best = null;
        double bestScore = -1;
        for (Move m : f.moves) {
            double score = 1.0 / m.startupFrames + 1.0 / m.recoveryFrames;
            if (m.isLow) score *= 1.2; // 下段攻击更难防御
            if (score > bestScore) {
                best = m;
                bestScore = score;
            }
        }
        return best;
    }

    /**
     * 模拟一帧游戏更新
     */
    public void updateFrame() {
        // 更新角色状态帧计数
        updateFighterFrame(player);
        updateFighterFrame(ai);

        // AI决策
        String action = makeDecision();
        System.out.println("AI决策：" + action);

        // 简化位置更新
        if ("前移".equals(action)) ai.x += 2;
        else if ("后移".equals(action)) ai.x -= 2;

        distance = Math.abs(ai.x - player.x);
    }

    private void updateFighterFrame(Fighter f) {
        f.stateFrame++;
        // 简化：状态帧数达到总帧数后回到待机
        if (f.stateFrame > 10) {
            f.state = State.IDLE;
            f.stateFrame = 0;
        }
    }

    public static void main(String[] args) {
        FightingGameAI game = new FightingGameAI();
        System.out.println("=== 格斗游戏AI帧数据决策模拟 ===\n");

        for (int frame = 0; frame < 30; frame++) {
            System.out.println("--- 第 " + frame + " 帧 ---");
            System.out.println("距离：" + game.distance);
            game.updateFrame();
            System.out.println();
        }
    }
}

进阶：Minimax博弈树

在更复杂的格斗游戏AI中，可以引入Minimax算法预测多回合交互：

/**
 * Minimax评估当前局面的价值
 * @param depth 搜索深度（以招为单位）
 * @param isMaximizing 当前是否为AI回合
 */
public int minimax(Fighter ai, Fighter player, int depth, boolean isMaximizing) {
    if (depth == 0 || ai.hp <= 0 || player.hp <= 0) {
        return evaluate(ai, player);
    }

    if (isMaximizing) {
        int maxEval = Integer.MIN_VALUE;
        for (Move m : ai.moves) {
            // 模拟执行招式
            Fighter aiCopy = copy(ai);
            Fighter playerCopy = copy(player);
            simulateMove(aiCopy, playerCopy, m);
            int eval = minimax(aiCopy, playerCopy, depth - 1, false);
            maxEval = Math.max(maxEval, eval);
        }
        return maxEval;
    } else {
        int minEval = Integer.MAX_VALUE;
        for (Move m : player.moves) {
            Fighter aiCopy = copy(ai);
            Fighter playerCopy = copy(player);
            simulateMove(playerCopy, aiCopy, m);
            int eval = minimax(aiCopy, playerCopy, depth - 1, true);
            minEval = Math.min(minEval, eval);
        }
        return minEval;
    }
}

/**
 * 局面评估函数
 */
private int evaluate(Fighter ai, Fighter player) {
    int score = 0;
    score += (ai.hp - player.hp) * 10;      // 血量差
    score += ai.state == State.IDLE ? 50 : 0; // 可行动优势
    score -= player.state == State.IDLE ? 50 : 0;
    score += (500 - distance) / 10;          // 距离控制
    return score;
}

复杂度分析

总结

本文实现了格斗游戏AI的帧数据决策系统，核心要点包括：

• 有限状态机建模角色行为，帧数据驱动状态转移
• 基于有利帧/不利帧的实时决策：punish、防御、连段、拉近距离
• Minimax博弈树用于多步预判，Alpha-Beta剪枝优化搜索效率
• 招式评分函数综合考虑伤害、速度、后续优势

读者可以在此基础上扩展：加入更多状态（投技、必杀技）、实现完整的碰撞检测、引入神经网络评估局面价值。