每日算法 — 使用java实现拳皇：连招状态机与帧数据最优决策

拳皇（The King of Fighters）是经典格斗游戏系列，其核心魅力在于精准的连招系统与帧级判定。本文用Java实现一个简化的拳皇AI对战引擎，讲解有限状态机（FSM）管理角色状态、帧数据表驱动攻击判定，以及贪心策略选择最优连招路径。

核心设计思路

格斗游戏的核心是”帧”——每1/60秒为一帧。每个动作（站立、轻拳、重拳、跳跃）都有对应的启动帧、活跃帧、恢复帧。AI需要在一帧内完成：读取双方状态 → 评估最优动作 → 执行输入。我们将整个系统拆分为三层：

1. 状态管理层：FSM管理角色的站立、蹲下、跳跃、受击、硬直等状态；
2. 帧数据层：每个招式用MoveFrameData记录伤害、命中框、无敌帧；
3. 决策层：基于当前帧差（Frame Advantage）计算最优连招路径。

完整Java实现

import java.util.*;

/**
 * 拳皇AI对战引擎核心框架
 * 包含：有限状态机、帧数据表、连招图、贪心决策器
 */
public class KofEngine {

    // ==================== 状态定义 ====================
    enum State {
        IDLE, CROUCH, JUMP_START, JUMP_UP, JUMP_DOWN,
        ATTACK_STARTUP, ATTACK_ACTIVE, ATTACK_RECOVERY,
        HITSTUN, BLOCKSTUN, KNOCKDOWN
    }

    // ==================== 帧数据结构 ====================
    static class MoveFrameData {
        String name;           // 招式名称
        int startupFrames;     // 启动帧（可被打断）
        int activeFrames;      // 活跃帧（产生命中框）
        int recoveryFrames;    // 恢复帧（硬直）
        int damage;            // 伤害值
        int hitstunFrames;     // 对手受击硬直
        int blockstunFrames;   // 对手防御硬直
        int range;             // 攻击距离
        boolean isLow;         // 是否下段攻击
        boolean isOverhead;    // 是否中段攻击

        MoveFrameData(String name, int su, int ac, int re, int dmg,
                      int hs, int bs, int range, boolean low, boolean oh) {
            this.name = name;
            this.startupFrames = su;
            this.activeFrames = ac;
            this.recoveryFrames = re;
            this.damage = dmg;
            this.hitstunFrames = hs;
            this.blockstunFrames = bs;
            this.range = range;
            this.isLow = low;
            this.isOverhead = oh;
        }

        // 总帧数
        int totalFrames() { return startupFrames + activeFrames + recoveryFrames; }

        // 帧优势 = 对手硬直 - 自身恢复帧
        int frameAdvantageOnHit() { return hitstunFrames - recoveryFrames; }
        int frameAdvantageOnBlock() { return blockstunFrames - recoveryFrames; }
    }

    // ==================== 角色实体 ====================
    static class Fighter {
        String name;
        int hp = 1000;
        int x;                 // 位置
        int y;                 // 0=地面, >0=空中
        State state = State.IDLE;
        int stateTimer = 0;    // 当前状态剩余帧数
        boolean facingRight = true;
        MoveFrameData currentMove = null;

        // 输入缓冲区：记录未来N帧的预输入
        Deque<String> inputBuffer = new ArrayDeque<>();

        Fighter(String name, int x) {
            this.name = name;
            this.x = x;
        }

        boolean isIdle() {
            return state == State.IDLE || state == State.CROUCH;
        }

        boolean isInHitstun() {
            return state == State.HITSTUN || state == State.BLOCKSTUN;
        }

        boolean isAirborne() {
            return state == State.JUMP_UP || state == State.JUMP_DOWN;
        }
    }

    // ==================== 全局招式库 ====================
    static final Map<String, MoveFrameData> MOVE_DB = new HashMap<>();
    static {
        // 轻拳：快、短、安全
        MOVE_DB.put("5LP", new MoveFrameData("5LP", 4, 2, 6, 30, 12, 9, 35, false, false));
        // 重拳：慢、长、高伤
        MOVE_DB.put("5HP", new MoveFrameData("5HP", 8, 3, 18, 90, 20, 15, 55, false, false));
        // 蹲下轻脚：下段
        MOVE_DB.put("2LK", new MoveFrameData("2LK", 5, 2, 8, 40, 14, 10, 40, true, false));
        // 跳跃重拳：空中攻击
        MOVE_DB.put("jHP", new MoveFrameData("jHP", 6, 6, 0, 100, 18, 12, 50, false, true));
        // 升龙拳：对空无敌
        MOVE_DB.put("DP", new MoveFrameData("DP", 3, 12, 25, 140, 24, 18, 45, false, false));
        // 波动拳：远程
        MOVE_DB.put("Hadoken", new MoveFrameData("Hadoken", 13, 0, 32, 60, 16, 12, 200, false, false));
    }

    // ==================== 连招图（Combo Graph） ====================
    // key: 当前招式 -> value: 可接续的招式列表（需满足帧优势条件）
    static final Map<String, List<String>> COMBO_GRAPH = new HashMap<>();
    static {
        COMBO_GRAPH.put("5LP", Arrays.asList("5LP", "5HP", "2LK", "DP"));
        COMBO_GRAPH.put("2LK", Arrays.asList("5LP", "DP"));
        COMBO_GRAPH.put("5HP", Arrays.asList("DP", "Hadoken"));
        COMBO_GRAPH.put("DP", Arrays.asList("Hadoken"));
        COMBO_GRAPH.put("jHP", Arrays.asList("5LP", "2LK", "5HP"));
    }

    // ==================== AI决策器 ====================
    static class KofAI {

        /**
         * 主决策入口：每帧调用一次
         * @param self  己方角色
         * @param enemy 敌方角色
         * @return 本帧输入指令
         */
        String decide(Fighter self, Fighter enemy) {
            int distance = Math.abs(self.x - enemy.x);

            // 1. 防御优先：如果对手处于活跃帧且攻击能打到我们
            if (isEnemyAttacking(enemy) && willHit(enemy, self)) {
                if (enemy.currentMove.isLow && self.state != State.CROUCH) {
                    return "CROUCH_BLOCK"; // 下段必须蹲防
                }
                if (enemy.currentMove.isOverhead && self.state == State.CROUCH) {
                    return "STAND_BLOCK";  // 中段必须站防
                }
                return "BLOCK";
            }

            // 2. 惩罚对手收招硬直
            if (enemy.state == State.ATTACK_RECOVERY && distance <= 55) {
                // 贪心选择伤害最高的可命中招式
                String punish = selectBestPunish(self, enemy, distance);
                if (punish != null) return punish;
            }

            // 3. 连招延续：如果当前招式命中，查找下一招
            if (self.currentMove != null && self.state == State.ATTACK_RECOVERY) {
                int fa = self.currentMove.frameAdvantageOnHit();
                if (fa >= 0) { // 有帧优势才能连
                    String next = selectComboFollowup(self, enemy, distance, fa);
                    if (next != null) return next;
                }
            }

            // 4. 起攻：根据距离选择最优起手
            if (self.isIdle()) {
                return selectOpening(self, enemy, distance);
            }

            // 5. 默认保持防御或待机
            return "NEUTRAL";
        }

        // 判断敌方是否处于攻击活跃帧
        boolean isEnemyAttacking(Fighter enemy) {
            return enemy.state == State.ATTACK_ACTIVE;
        }

        // 简化判定：攻击距离是否覆盖双方间距
        boolean willHit(Fighter attacker, Fighter defender) {
            int dist = Math.abs(attacker.x - defender.x);
            return dist <= attacker.currentMove.range;
        }

        // 贪心选择惩罚招式：在对手硬直内，选伤害/帧数比最高的招式
        String selectBestPunish(Fighter self, Fighter enemy, int distance) {
            String best = null;
            double bestScore = -1;
            for (Map.Entry<String, MoveFrameData> e : MOVE_DB.entrySet()) {
                MoveFrameData m = e.getValue();
                if (m.range < distance) continue; // 打不到
                if (m.startupFrames > enemy.stateTimer) continue; // 出手太慢
                double score = (double) m.damage / m.totalFrames();
                if (score > bestScore) {
                    bestScore = score;
                    best = e.getKey();
                }
            }
            return best;
        }

        // 选择连招下一招：在帧优势允许的情况下，最大化期望伤害
        String selectComboFollowup(Fighter self, Fighter enemy, int distance, int frameAdvantage) {
            List<String> candidates = COMBO_GRAPH.getOrDefault(self.currentMove.name, Collections.emptyList());
            String best = null;
            int bestDmg = -1;
            for (String moveName : candidates) {
                MoveFrameData m = MOVE_DB.get(moveName);
                if (m == null) continue;
                if (m.range < distance) continue;
                // 需要启动帧 ≤ 帧优势 + 对手受击硬直（简化判定）
                if (m.startupFrames > frameAdvantage + 6) continue;
                if (m.damage > bestDmg) {
                    bestDmg = m.damage;
                    best = moveName;
                }
            }
            return best;
        }

        // 起攻选择：近距离轻拳压制，中距离波动拳，远距离前冲
        String selectOpening(Fighter self, Fighter enemy, int distance) {
            if (distance <= 40) return "5LP";          // 轻拳起攻
            if (distance <= 100) return "2LK";         // 蹲下轻脚起攻
            if (distance <= 180) return "Hadoken";     // 波动拳牵制
            return "FORWARD_DASH";                     // 前冲拉近距离
        }
    }

    // ==================== 主循环与模拟器 ====================
    static class BattleSimulator {
        Fighter p1 = new Fighter("Kyo", 100);
        Fighter p2 = new Fighter("Iori", 300);
        KofAI ai = new KofAI();
        int frame = 0;

        void runOneFrame() {
            frame++;
            // AI决策
            String cmd1 = ai.decide(p1, p2);
            String cmd2 = ai.decide(p2, p1); // 简单镜像AI

            // 执行指令（简化版）
            applyCommand(p1, cmd1, p2);
            applyCommand(p2, cmd2, p1);

            // 更新状态机
            updateState(p1);
            updateState(p2);

            // 命中检测
            checkHit(p1, p2);
            checkHit(p2, p1);
        }

        void applyCommand(Fighter f, String cmd, Fighter enemy) {
            if (!f.isIdle() && !f.isInHitstun()) return; // 非可控状态忽略输入
            switch (cmd) {
                case "5LP": case "5HP": case "2LK": case "DP": case "Hadoken":
                    f.currentMove = MOVE_DB.get(cmd);
                    f.state = State.ATTACK_STARTUP;
                    f.stateTimer = f.currentMove.startupFrames;
                    break;
                case "CROUCH_BLOCK":
                    f.state = State.CROUCH;
                    break;
                case "STAND_BLOCK":
                case "BLOCK":
                    f.state = State.IDLE; // 简化：防御即站立
                    break;
                case "FORWARD_DASH":
                    f.x += (f.facingRight ? 1 : -1) * 15;
                    break;
            }
        }

        void updateState(Fighter f) {
            if (f.stateTimer > 0) f.stateTimer--;
            if (f.stateTimer == 0) {
                switch (f.state) {
                    case ATTACK_STARTUP:
                        f.state = State.ATTACK_ACTIVE;
                        f.stateTimer = f.currentMove.activeFrames;
                        break;
                    case ATTACK_ACTIVE:
                        f.state = State.ATTACK_RECOVERY;
                        f.stateTimer = f.currentMove.recoveryFrames;
                        break;
                    case ATTACK_RECOVERY:
                    case HITSTUN:
                    case BLOCKSTUN:
                        f.state = State.IDLE;
                        f.currentMove = null;
                        break;
                    case JUMP_START:
                        f.state = State.JUMP_UP;
                        f.stateTimer = 20;
                        break;
                    case JUMP_UP:
                        f.state = State.JUMP_DOWN;
                        f.stateTimer = 20;
                        break;
                    case JUMP_DOWN:
                        f.state = State.IDLE;
                        f.y = 0;
                        break;
                    default:
                        break;
                }
            }
        }

        void checkHit(Fighter attacker, Fighter defender) {
            if (attacker.state != State.ATTACK_ACTIVE) return;
            if (defender.state == State.HITSTUN || defender.state == State.BLOCKSTUN) return;
            int dist = Math.abs(attacker.x - defender.x);
            if (dist > attacker.currentMove.range) return;

            // 简化防御判定
            boolean blocking = (attacker.currentMove.isLow && defender.state == State.CROUCH)
                    || (!attacker.currentMove.isLow && defender.state == State.IDLE);

            if (blocking) {
                defender.state = State.BLOCKSTUN;
                defender.stateTimer = attacker.currentMove.blockstunFrames;
                System.out.printf("[%s] %s 防御了 %s%n", attacker.name, defender.name, attacker.currentMove.name);
            } else {
                defender.hp -= attacker.currentMove.damage;
                defender.state = State.HITSTUN;
                defender.stateTimer = attacker.currentMove.hitstunFrames;
                System.out.printf("[%s] %s 命中 %s，造成 %d 伤害，敌方剩余 HP=%d%n",
                        attacker.name, attacker.currentMove.name, defender.name,
                        attacker.currentMove.damage, defender.hp);
            }
        }
    }

    public static void main(String[] args) {
        BattleSimulator sim = new BattleSimulator();
        System.out.println("=== 拳皇AI对战模拟开始 ===");
        for (int i = 0; i < 300; i++) {
            sim.runOneFrame();
            if (sim.p1.hp <= 0 || sim.p2.hp <= 0) break;
        }
        System.out.println("=== 对战结束 ===");
        System.out.printf("P1 %s HP=%d%n", sim.p1.name, sim.p1.hp);
        System.out.printf("P2 %s HP=%d%n", sim.p2.name, sim.p2.hp);
    }
}

复杂度分析

实战中对战双方各6个招式，每帧AI决策仅需数十次整数比较，在现代CPU上可轻松达到60FPS的帧级决策。

扩展方向

1. 深度学习AI：用神经网络替代贪心决策，通过自我对弈训练策略网络；
2. 帧精准输入：引入输入缓冲（Input Buffer）与指令预读，实现1帧目押；
3. 完整碰撞系统：用AABB或OBB替代距离判定，支持蹲下、跳跃的不同受击框。

拳皇的竞技深度源于”帧”级别的信息差。通过状态机+帧数据+贪心决策的三层架构，我们搭建了一个可扩展的格斗AI原型，读者可在此基础上继续探索更复杂的博弈策略。