每日算法 — 使用java实现火焰纹章：战棋移动范围BFS与伤害期望最优决策

游戏简介

火焰纹章（Fire Emblem）是任天堂旗下Intelligent Systems开发的经典战棋策略角色扮演游戏。游戏在网格地图上展开，玩家控制各单位移动、攻击、使用道具，通过策略部署击败敌军。本文将用Java实现战棋游戏的核心系统，重点讲解BFS计算单位移动范围、地形影响与攻击范围判定、伤害期望值计算，以及AI最优目标选择策略。

核心数据结构

地图与单位

战棋地图由二维网格构成，每个格子包含地形信息（影响移动消耗和防御加成）。单位具有移动力、攻击力、防御力等属性。

public class Terrain {
    public static final int PLAIN = 0;
    public static final int FOREST = 1;
    public static final int MOUNTAIN = 2;
    public static final int RIVER = 3;
    public static final int WALL = 4;

    private int type;
    private int moveCost;      // 移动力消耗
    private int defenseBonus;  // 防御加成
    private int avoidBonus;    // 回避加成

    public Terrain(int type) {
        this.type = type;
        switch (type) {
            case PLAIN -> { moveCost = 1; defenseBonus = 0; avoidBonus = 0; }
            case FOREST -> { moveCost = 2; defenseBonus = 1; avoidBonus = 20; }
            case MOUNTAIN -> { moveCost = 3; defenseBonus = 2; avoidBonus = 40; }
            case RIVER -> { moveCost = 3; defenseBonus = 0; avoidBonus = 0; }
            case WALL -> { moveCost = 99; defenseBonus = 0; avoidBonus = 0; }
        }
    }

    // getters...
    public int getMoveCost() { return moveCost; }
    public int getDefenseBonus() { return defenseBonus; }
    public int getAvoidBonus() { return avoidBonus; }
}

public class Unit {
    private String name;
    private int x, y;           // 当前位置
    private int moveRange;      // 移动力
    private int attackRange;    // 攻击范围（最小-最大）
    private int minRange;       // 最小攻击距离
    private int hp, maxHp;      // 生命值
    private int strength;       // 力量（影响物理攻击）
    private int magic;          // 魔力（影响魔法攻击）
    private int skill;          // 技巧（影响命中）
    private int speed;          // 速度（影响回避和追击）
    private int luck;           // 幸运
    private int defense;        // 防御
    private int resistance;     // 魔防
    private UnitType unitType;  // 单位类型
    private Team team;          // 所属阵营

    // 武器信息
    private Weapon equippedWeapon;

    public enum UnitType { INFANTRY, CAVALRY, FLYING, ARMORED }
    public enum Team { PLAYER, ENEMY, ALLY }

    public Unit(String name, Team team, int moveRange, int minRange, int maxRange) {
        this.name = name;
        this.team = team;
        this.moveRange = moveRange;
        this.minRange = minRange;
        this.attackRange = maxRange;
    }

    // getters and setters...
    public int getX() { return x; }
    public int getY() { return y; }
    public void setPosition(int x, int y) { this.x = x; this.y = y; }
    public int getMoveRange() { return moveRange; }
    public int getAttackRange() { return attackRange; }
    public int getMinRange() { return minRange; }
    public Team getTeam() { return team; }
    public boolean isAlive() { return hp > 0; }
}

public class Weapon {
    private String name;
    private int might;      // 威力
    private int hit;        // 命中
    private int crit;       // 必杀
    private int weight;     // 重量（影响追击判定）
    private WeaponType type;

    public enum WeaponType { SWORD, LANCE, AXE, BOW, MAGIC }

    public Weapon(String name, int might, int hit, int crit, int weight) {
        this.name = name;
        this.might = might;
        this.hit = hit;
        this.crit = crit;
        this.weight = weight;
    }

    public int getMight() { return might; }
    public int getHit() { return hit; }
    public int getCrit() { return crit; }
    public int getWeight() { return weight; }
}

BFS移动范围计算

每个单位的可移动范围取决于其移动力和各格子的地形消耗。使用BFS（或Dijkstra，当地形消耗不同时）从单位位置出发，计算所有可到达的格子。

public class MoveRangeCalculator {

    private static final int[] DX = {-1, 1, 0, 0}; // 上、下、左、右
    private static final int[] DY = {0, 0, -1, 1};

    /**
     * 使用BFS计算单位的移动范围
     * @param unit 要计算移动范围的单位
     * @param map 地形地图
     * @param allUnits 所有单位列表（用于检测被占据的格子）
     * @return 可到达的位置集合，以及到达每个位置消耗的移动力
     */
    public static Map<Position, Integer> calculateMoveRange(Unit unit, 
                                                            Terrain[][] map, 
                                                            List<Unit> allUnits) {
        Map<Position, Integer> reachable = new HashMap<>();
        Queue<MoveNode> queue = new LinkedList<>();
        boolean[][] visited = new boolean[map.length][map[0].length];

        Position start = new Position(unit.getX(), unit.getY());
        queue.offer(new MoveNode(start, 0));
        reachable.put(start, 0);
        visited[start.y][start.x] = true;

        while (!queue.isEmpty()) {
            MoveNode current = queue.poll();

            for (int i = 0; i < 4; i++) {
                int nx = current.pos.x + DX[i];
                int ny = current.pos.y + DY[i];

                // 边界检查
                if (nx < 0 || nx >= map[0].length || ny < 0 || ny >= map.length) continue;
                if (visited[ny][nx]) continue;

                // 地形移动消耗
                int terrainCost = map[ny][nx].getMoveCost();

                // 不同单位类型对地形有不同处理
                if (unit.getUnitType() == Unit.UnitType.FLYING) {
                    terrainCost = 1; // 飞行单位无视地形
                } else if (unit.getUnitType() == Unit.UnitType.CAVALRY && terrainCost > 2) {
                    continue; // 骑兵无法通过复杂地形
                }

                int newCost = current.cost + terrainCost;
                if (newCost > unit.getMoveRange()) continue;

                // 检查目标格子是否被敌方/友方单位占据（通常不能穿过）
                // 注意：有些游戏允许穿过友军，这里简化为不允许穿过任何单位
                Unit occupant = getUnitAt(nx, ny, allUnits);
                if (occupant != null && occupant != unit) continue;

                Position newPos = new Position(nx, ny);
                reachable.put(newPos, newCost);
                visited[ny][nx] = true;
                queue.offer(new MoveNode(newPos, newCost));
            }
        }

        return reachable;
    }

    /**
     * 计算从某位置可以攻击到的所有格子
     */
    public static Set<Position> calculateAttackRange(Position from, int minRange, 
                                                      int maxRange, int mapWidth, int mapHeight) {
        Set<Position> attackRange = new HashSet<>();

        for (int r = minRange; r <= maxRange; r++) {
            // 曼哈顿距离为r的所有位置
            for (int dx = -r; dx <= r; dx++) {
                int dy = r - Math.abs(dx);
                addIfValid(attackRange, from.x + dx, from.y + dy, mapWidth, mapHeight);
                if (dy != 0) {
                    addIfValid(attackRange, from.x + dx, from.y - dy, mapWidth, mapHeight);
                }
            }
        }

        return attackRange;
    }

    private static void addIfValid(Set<Position> set, int x, int y, int w, int h) {
        if (x >= 0 && x < w && y >= 0 && y < h) {
            set.add(new Position(x, y));
        }
    }

    private static Unit getUnitAt(int x, int y, List<Unit> units) {
        for (Unit u : units) {
            if (u.isAlive() && u.getX() == x && u.getY() == y) return u;
        }
        return null;
    }

    static class MoveNode {
        Position pos;
        int cost;
        MoveNode(Position pos, int cost) {
            this.pos = pos;
            this.cost = cost;
        }
    }
}

record Position(int x, int y) {
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Position)) return false;
        Position p = (Position) o;
        return x == p.x && y == p.y;
    }
    @Override
    public int hashCode() {
        return x * 1000 + y;
    }
}

伤害计算与期望值

火焰纹章的伤害计算涉及命中率、必杀率、攻防差值、武器三角等多个因素。AI在做决策时需要计算期望伤害，而非单纯的最大伤害。

基础伤害公式

public class CombatCalculator {

    /**
     * 计算战斗预测结果
     */
    public static CombatResult simulateCombat(Unit attacker, Unit defender, Terrain defTerrain) {
        CombatResult result = new CombatResult();

        // 1. 计算命中率
        int hitRate = calculateHitRate(attacker, defender, defTerrain);
        result.hitRate = Math.max(0, Math.min(100, hitRate));

        // 2. 计算伤害
        int damage = calculateDamage(attacker, defender, defTerrain);
        result.damage = Math.max(0, damage);

        // 3. 计算必杀率
        int critRate = calculateCritRate(attacker, defender);
        result.critRate = Math.max(0, Math.min(100, critRate));

        // 4. 计算期望伤害
        double expectedDamage = result.hitRate / 100.0 * result.damage;
        double critBonus = result.hitRate / 100.0 * result.critRate / 100.0 * result.damage * 2;
        result.expectedDamage = expectedDamage + critBonus;

        // 5. 判定是否能追击（速度差≥4时追击）
        int attackerSpeed = attacker.getSpeed() - attacker.getEquippedWeapon().getWeight();
        int defenderSpeed = defender.getSpeed() - (defender.getEquippedWeapon() != null ? 
                                                   defender.getEquippedWeapon().getWeight() : 0);
        result.canDouble = (attackerSpeed - defenderSpeed) >= 4;
        if (result.canDouble) {
            result.expectedDamage *= 2;
        }

        // 6. 计算击杀概率（简化：假设独立判定）
        int hitsToKill = (int) Math.ceil(defender.getHp() / result.expectedDamage);
        result.canKill = result.expectedDamage >= defender.getHp();

        return result;
    }

    /**
     * 命中率 = 攻击方技巧*2 + 攻击方幸运/2 + 武器命中 + 支援加成 - 防御方速度*2 - 防御方幸运/2 - 地形回避
     */
    private static int calculateHitRate(Unit attacker, Unit defender, Terrain terrain) {
        int baseHit = attacker.getSkill() * 2 + attacker.getLuck() / 2;
        int weaponHit = attacker.getEquippedWeapon().getHit();
        int avoid = defender.getSpeed() * 2 + defender.getLuck() / 2 + terrain.getAvoidBonus();
        return baseHit + weaponHit - avoid;
    }

    /**
     * 伤害 = 攻击方力/魔 + 武器威力 + 支援加成 - 防御方防/魔防 - 地形防御
     */
    private static int calculateDamage(Unit attacker, Unit defender, Terrain terrain) {
        boolean isMagic = attacker.getEquippedWeapon().getType() == Weapon.WeaponType.MAGIC;
        int attackStat = isMagic ? attacker.getMagic() : attacker.getStrength();
        int defenseStat = isMagic ? defender.getResistance() : defender.getDefense();
        int weaponMight = attacker.getEquippedWeapon().getMight();

        // 武器三角克制：剑克斧，斧克枪，枪克剑，魔法无克制
        int triangleBonus = calculateWeaponTriangle(attacker, defender);

        return attackStat + weaponMight + triangleBonus - defenseStat - terrain.getDefenseBonus();
    }

    /**
     * 武器三角计算：优势+1伤害，劣势-1伤害
     */
    private static int calculateWeaponTriangle(Unit attacker, Unit defender) {
        Weapon.WeaponType a = attacker.getEquippedWeapon().getType();
        Weapon.WeaponType d = defender.getEquippedWeapon() != null ? 
                              defender.getEquippedWeapon().getType() : null;

        if (d == null) return 0;

        if ((a == Weapon.WeaponType.SWORD && d == Weapon.WeaponType.AXE) ||
            (a == Weapon.WeaponType.AXE && d == Weapon.WeaponType.LANCE) ||
            (a == Weapon.WeaponType.LANCE && d == Weapon.WeaponType.SWORD)) {
            return 1;
        }
        if ((a == Weapon.WeaponType.AXE && d == Weapon.WeaponType.SWORD) ||
            (a == Weapon.WeaponType.LANCE && d == Weapon.WeaponType.AXE) ||
            (a == Weapon.WeaponType.SWORD && d == Weapon.WeaponType.LANCE)) {
            return -1;
        }
        return 0;
    }

    /**
     * 必杀率 = 武器必杀 + 技巧/2
     */
    private static int calculateCritRate(Unit attacker, Unit defender) {
        int baseCrit = attacker.getEquippedWeapon().getCrit();
        int skillBonus = attacker.getSkill() / 2;
        int critAvoid = defender.getLuck(); // 幸运抵消必杀
        return baseCrit + skillBonus - critAvoid;
    }
}

class CombatResult {
    int hitRate;           // 命中率（0-100）
    int damage;            // 单次伤害
    int critRate;          // 必杀率（0-100）
    double expectedDamage; // 期望总伤害
    boolean canDouble;     // 是否能追击
    boolean canKill;       // 是否能击杀

    @Override
    public String toString() {
        return String.format("命中:%d%% 伤害:%d 必杀:%d%% 期望:%.1f %s%s",
            hitRate, damage, critRate, expectedDamage,
            canDouble ? "[追击]" : "", canKill ? "[可击杀]" : "");
    }
}

AI最优目标选择策略

敌AI需要综合考虑伤害期望、击杀概率、反击风险、地形优劣等因素，选择最优的行动方案。

public class AIDecisionMaker {

    /**
     * 为AI单位选择最优行动
     */
    public static AIAction chooseBestAction(Unit aiUnit, 
                                             Terrain[][] map,
                                             List<Unit> allUnits,
                                             int mapWidth, int mapHeight) {
        List<AIAction> candidates = new ArrayList<>();

        // 1. 计算所有可移动位置
        Map<Position, Integer> moveRange = MoveRangeCalculator.calculateMoveRange(
            aiUnit, map, allUnits);

        // 2. 对每个可移动位置，计算可能的攻击目标
        for (Map.Entry<Position, Integer> entry : moveRange.entrySet()) {
            Position movePos = entry.getKey();

            // 计算从此位置可攻击的范围
            Set<Position> attackRange = MoveRangeCalculator.calculateAttackRange(
                movePos, aiUnit.getMinRange(), aiUnit.getAttackRange(), mapWidth, mapHeight);

            // 检查每个攻击范围内是否有敌方单位
            for (Position attackPos : attackRange) {
                Unit target = getUnitAt(attackPos.x, attackPos.y, allUnits);
                if (target != null && target.getTeam() != aiUnit.getTeam() && target.isAlive()) {
                    // 评估此行动方案
                    double score = evaluateAction(aiUnit, movePos, target, map, allUnits);
                    candidates.add(new AIAction(movePos, target, score));
                }
            }

            // 也考虑不攻击只移动的情况（如靠近目标、占据有利地形）
            if (candidates.stream().noneMatch(a -> a.movePos.equals(movePos))) {
                double score = evaluateMoveOnly(aiUnit, movePos, map, allUnits);
                candidates.add(new AIAction(movePos, null, score));
            }
        }

        // 3. 选择得分最高的行动
        candidates.sort((a, b) -> Double.compare(b.score, a.score));
        return candidates.isEmpty() ? null : candidates.get(0);
    }

    /**
     * 评估攻击行动的综合得分
     */
    private static double evaluateAction(Unit aiUnit, Position movePos, Unit target,
                                          Terrain[][] map, List<Unit> allUnits) {
        double score = 0;

        // 创建临时单位模拟移动后的战斗
        Unit tempUnit = createTempUnit(aiUnit, movePos);
        CombatResult result = CombatCalculator.simulateCombat(tempUnit, target, 
                                                               map[target.getY()][target.getX()]);

        // 1. 击杀奖励（最高优先级）
        if (result.canKill) {
            score += 1000;
        }

        // 2. 期望伤害得分
        score += result.expectedDamage * 10;

        // 3. 命中率惩罚（避免盲目攻击低命中目标）
        score += result.hitRate * 0.5;

        // 4. 评估反击风险
        if (canCounterAttack(target, movePos, aiUnit)) {
            Unit tempTarget = createTempUnit(target, new Position(target.getX(), target.getY()));
            CombatResult counter = CombatCalculator.simulateCombat(tempTarget, tempUnit,
                                                                    map[movePos.y][movePos.x]);
            score -= counter.expectedDamage * 8; // 反击风险权重较高
            if (counter.canKill) {
                score -= 500; // 可能被反杀是重大风险
            }
        }

        // 5. 地形奖励
        Terrain destTerrain = map[movePos.y][movePos.x];
        score += destTerrain.getDefenseBonus() * 15;
        score += destTerrain.getAvoidBonus() * 0.3;

        // 6. 距离惩罚（避免离其他敌人太近，防止被围攻）
        for (Unit other : allUnits) {
            if (other != target && other.getTeam() != aiUnit.getTeam() && other.isAlive()) {
                int dist = Math.abs(movePos.x - other.getX()) + Math.abs(movePos.y - other.getY());
                if (dist <= other.getAttackRange() + other.getMoveRange()) {
                    score -= 20; // 进入其他敌人的威胁范围
                }
            }
        }

        // 7. 血量越低越保守
        double hpRatio = (double) aiUnit.getHp() / aiUnit.getMaxHp();
        if (hpRatio < 0.3) {
            score -= result.expectedDamage * 5; // 低血量时更看重安全
        }

        return score;
    }

    /**
     * 评估纯移动行动（不攻击）
     */
    private static double evaluateMoveOnly(Unit aiUnit, Position movePos, 
                                            Terrain[][] map, List<Unit> allUnits) {
        double score = 0;

        Terrain terrain = map[movePos.y][movePos.x];
        score += terrain.getDefenseBonus() * 10;
        score += terrain.getAvoidBonus() * 0.2;

        // 靠近最近敌人的奖励（保持压力）
        Unit nearestEnemy = findNearestEnemy(aiUnit, allUnits);
        if (nearestEnemy != null) {
            int dist = Math.abs(movePos.x - nearestEnemy.getX()) + 
                      Math.abs(movePos.y - nearestEnemy.getY());
            score += Math.max(0, 30 - dist); // 距离越近得分越高
        }

        return score;
    }

    /**
     * 判定防御方能否反击
     */
    private static boolean canCounterAttack(Unit defender, Position attackerPos, Unit attacker) {
        int dist = Math.abs(defender.getX() - attackerPos.x) + 
                   Math.abs(defender.getY() - attackerPos.y);
        return dist >= defender.getMinRange() && dist <= defender.getAttackRange() &&
               defender.getEquippedWeapon() != null;
    }

    private static Unit getUnitAt(int x, int y, List<Unit> units) {
        for (Unit u : units) {
            if (u.isAlive() && u.getX() == x && u.getY() == y) return u;
        }
        return null;
    }

    private static Unit findNearestEnemy(Unit unit, List<Unit> allUnits) {
        Unit nearest = null;
        int minDist = Integer.MAX_VALUE;
        for (Unit other : allUnits) {
            if (other.getTeam() != unit.getTeam() && other.isAlive()) {
                int dist = Math.abs(unit.getX() - other.getX()) + 
                          Math.abs(unit.getY() - other.getY());
                if (dist < minDist) {
                    minDist = dist;
                    nearest = other;
                }
            }
        }
        return nearest;
    }

    private static Unit createTempUnit(Unit original, Position pos) {
        Unit temp = new Unit(original.getName(), original.getTeam(), 
                             original.getMoveRange(), original.getMinRange(), 
                             original.getAttackRange());
        temp.setPosition(pos.x, pos.y);
        // 复制其他属性...
        return temp;
    }
}

class AIAction {
    Position movePos;
    Unit target;
    double score;

    AIAction(Position movePos, Unit target, double score) {
        this.movePos = movePos;
        this.target = target;
        this.score = score;
    }
}

完整可运行示例

public class FireEmblemDemo {
    public static void main(String[] args) {
        // 创建简单地图
        Terrain[][] map = new Terrain[10][10];
        for (int y = 0; y < 10; y++) {
            for (int x = 0; x < 10; x++) {
                map[y][x] = new Terrain(Terrain.PLAIN);
            }
        }
        // 添加一些森林和山地
        map[3][3] = new Terrain(Terrain.FOREST);
        map[3][4] = new Terrain(Terrain.FOREST);
        map[5][6] = new Terrain(Terrain.MOUNTAIN);
        map[5][7] = new Terrain(Terrain.MOUNTAIN);

        // 创建单位
        Unit player = new Unit("主角", Unit.Team.PLAYER, 5, 1, 1);
        player.setPosition(2, 2);
        player.equipWeapon(new Weapon("铁剑", 5, 90, 0, 5));

        Unit enemy = new Unit("山贼", Unit.Team.ENEMY, 4, 1, 1);
        enemy.setPosition(6, 5);
        enemy.equipWeapon(new Weapon("铁斧", 6, 80, 0, 7));

        List<Unit> allUnits = Arrays.asList(player, enemy);

        // 计算移动范围
        Map<Position, Integer> moveRange = MoveRangeCalculator.calculateMoveRange(
            player, map, allUnits);
        System.out.println("主角可移动位置数: " + moveRange.size());

        // 战斗模拟
        CombatResult result = CombatCalculator.simulateCombat(player, enemy, map[5][6]);
        System.out.println("战斗预测: " + result);

        // AI决策
        AIAction action = AIDecisionMaker.chooseBestAction(enemy, map, allUnits, 10, 10);
        if (action != null) {
            System.out.println("AI决策: 移动到 (" + action.movePos.x + "," + action.movePos.y + ")" +
                (action.target != null ? "，攻击 " + action.target.getName() : "") +
                "，得分: " + String.format("%.2f", action.score));
        }
    }
}

复杂度分析

总结

本文实现了火焰纹章风格战棋游戏的核心系统，核心亮点包括：

• BFS移动范围计算：考虑地形消耗、单位类型差异（步兵/骑兵/飞行），精确计算可到达区域
• 攻击范围判定：基于曼哈顿距离的环形攻击范围计算，支持最小-最大射程
• 完整战斗模拟：涵盖命中、伤害、必杀、追击、武器三角克制等经典战棋要素
• 期望伤害评估：综合考虑命中率、必杀率和追击，计算数学期望而非单纯最大伤害
• 多因素AI决策：综合击杀奖励、伤害期望、反击风险、地形优势和位置安全度进行策略选择

读者可以进一步扩展，例如添加职业转职系统、支援关系加成、天气影响、或更复杂的群体AI协同策略，打造更完整的战棋策略体验。