每日算法 — 使用java实现坦克大战：A星寻路与有限状态机敌人AI

坦克大战（Battle City）是FC平台上最经典的射击游戏之一。玩家在二维迷宫中操控坦克摧毁敌方基地，同时躲避敌方坦克的追击。看似简单的规则背后，敌方AI的设计是游戏可玩性的核心——敌人需要在”追击玩家”、”规避炮弹”、”巡逻警戒”和”围攻基地”之间智能切换。本文用Java实现完整的坦克大战AI引擎，核心聚焦两大算法：A星寻路计算最短移动路径，以及有限状态机（FSM）驱动敌人行为决策。

游戏地图与实体建模

游戏地图由可破坏的砖墙、不可破坏的钢墙、河流和草地组成。每个实体占据一个网格单元，坦克只能在没有障碍的单元格中移动。

/**
 * 地图单元格类型枚举
 */
public enum CellType {
    EMPTY(0),      // 空地，可通行
    BRICK(1),      // 砖墙，可被破坏
    STEEL(2),      // 钢墙，不可破坏
    RIVER(3),      // 河流，不可通行
    GRASS(4),      // 草地，可通行但遮挡视野
    BASE(5);       // 玩家基地

    final int code;
    CellType(int code) { this.code = code; }

    public boolean isPassable() {
        return this == EMPTY || this == GRASS;
    }

    public boolean isBreakable() {
        return this == BRICK;
    }
}

/**
 * 二维游戏地图
 * 使用二维数组表示网格，支持动态破坏（砖墙被击中后变为空地）
 */
public class GameMap {
    private final int rows;
    private final int cols;
    private final CellType[][] grid;

    public GameMap(int rows, int cols) {
        this.rows = rows;
        this.cols = cols;
        this.grid = new CellType[rows][cols];
        // 默认全部初始化为空地
        for (int r = 0; r < rows; r++) {
            Arrays.fill(grid[r], CellType.EMPTY);
        }
    }

    public void setCell(int row, int col, CellType type) {
        if (inBounds(row, col)) grid[row][col] = type;
    }

    public CellType getCell(int row, int col) {
        return inBounds(row, col) ? grid[row][col] : CellType.STEEL;
    }

    public boolean inBounds(int row, int col) {
        return row >= 0 && row < rows && col >= 0 && col < cols;
    }

    public boolean isPassable(int row, int col) {
        return inBounds(row, col) && getCell(row, col).isPassable();
    }

    /**
     * 炮弹击中后更新地图：砖墙被破坏
     */
    public void onBulletHit(int row, int col) {
        if (inBounds(row, col) && grid[row][col] == CellType.BRICK) {
            grid[row][col] = CellType.EMPTY;
        }
    }

    public int getRows() { return rows; }
    public int getCols() { return cols; }
}

核心算法一：A星寻路

敌方坦克要追击玩家，需要计算从当前位置到玩家位置的最短可通行路径。A星（A*）算法是游戏寻路的标准方案，它结合了Dijkstra算法的全局最优性与贪心策略的启发式引导。

算法原理

A星维护两个集合：
– OpenSet：待探索的节点，按 f = g + h 排序
– ClosedSet：已探索的节点

其中：
– g(n)：从起点到节点n的实际代价（路径长度）
– h(n)：从节点n到目标的估计代价（启发函数，使用曼哈顿距离）
– f(n) = g(n) + h(n)：总估计代价

Java实现

import java.util.*;

/**
 * A星寻路算法实现
 * 为坦克在网格地图中寻找最短可通行路径
 */
public class AStarPathfinder {

    /**
     * 寻路节点，记录位置、g/h/f值与父节点用于路径回溯
     */
    static class Node implements Comparable<Node> {
        final int row, col;
        double g;      // 从起点到当前节点的实际代价
        double h;      // 到目标的启发估计代价
        double f;      // f = g + h
        Node parent;   // 父节点，用于路径回溯

        Node(int row, int col) {
            this.row = row;
            this.col = col;
            this.g = Double.MAX_VALUE;
            this.h = 0;
            this.f = Double.MAX_VALUE;
        }

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

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof Node)) return false;
            Node node = (Node) o;
            return row == node.row && col == node.col;
        }

        @Override
        public int hashCode() {
            return Objects.hash(row, col);
        }
    }

    private final GameMap map;
    // 四方向移动：上、下、左、右
    private static final int[][] DIRECTIONS = {{-1,0}, {1,0}, {0,-1}, {0,1}};

    public AStarPathfinder(GameMap map) {
        this.map = map;
    }

    /**
     * A星寻路主入口
     * @param startRow 起点行
     * @param startCol 起点列
     * @param targetRow 目标行
     * @param targetCol 目标列
     * @return 从起点到目标的路径节点列表（包含起点和终点），不可达则返回空列表
     */
    public List<Node> findPath(int startRow, int startCol, int targetRow, int targetCol) {
        // 边界与可行性检查
        if (!map.isPassable(startRow, startCol) || !map.isPassable(targetRow, targetCol)) {
            return Collections.emptyList();
        }

        PriorityQueue<Node> openSet = new PriorityQueue<>();
        Set<String> closedSet = new HashSet<>();

        Node start = new Node(startRow, startCol);
        start.g = 0;
        start.h = heuristic(startRow, startCol, targetRow, targetCol);
        start.f = start.g + start.h;
        openSet.add(start);

        while (!openSet.isEmpty()) {
            Node current = openSet.poll();
            String key = current.row + "," + current.col;

            // 已探索过则跳过
            if (closedSet.contains(key)) continue;
            closedSet.add(key);

            // 到达目标，回溯路径
            if (current.row == targetRow && current.col == targetCol) {
                return reconstructPath(current);
            }

            // 扩展四邻域
            for (int[] dir : DIRECTIONS) {
                int nr = current.row + dir[0];
                int nc = current.col + dir[1];

                if (!map.isPassable(nr, nc)) continue;

                Node neighbor = new Node(nr, nc);
                String nKey = nr + "," + nc;
                if (closedSet.contains(nKey)) continue;

                double tentativeG = current.g + 1.0; // 每步代价为1

                // 如果找到更优路径，更新邻居节点
                if (tentativeG < neighbor.g) {
                    neighbor.g = tentativeG;
                    neighbor.h = heuristic(nr, nc, targetRow, targetCol);
                    neighbor.f = neighbor.g + neighbor.h;
                    neighbor.parent = current;
                    openSet.add(neighbor);
                }
            }
        }

        // OpenSet耗尽仍未到达目标，说明不可达
        return Collections.emptyList();
    }

    /**
     * 启发函数：曼哈顿距离
     * 适用于四方向移动的网格地图，满足可采纳性（admissible）
     */
    private double heuristic(int r1, int c1, int r2, int c2) {
        return Math.abs(r1 - r2) + Math.abs(c1 - c2);
    }

    /**
     * 从目标节点回溯到起点，构建完整路径
     */
    private List<Node> reconstructPath(Node target) {
        List<Node> path = new ArrayList<>();
        Node curr = target;
        while (curr != null) {
            path.add(curr);
            curr = curr.parent;
        }
        Collections.reverse(path);
        return path;
    }
}

路径平滑优化

原始A星路径在网格上呈锯齿状。坦克作为连续移动的实体，可以通过拐角裁切来减少不必要的转向：

/**
 * 路径平滑：移除中间不必要的折点
 * 如果点A可以直接看到点C（线段无障碍），则跳过中间点B
 */
public List<Node> smoothPath(GameMap map, List<Node> rawPath) {
    if (rawPath.size() <= 2) return rawPath;

    List<Node> smoothed = new ArrayList<>();
    smoothed.add(rawPath.get(0));
    int i = 0;

    while (i < rawPath.size() - 1) {
        int j = rawPath.size() - 1;
        // 从终点往前找，找到第一个能从当前点直接看到的点
        while (j > i + 1 && !hasLineOfSight(map, rawPath.get(i), rawPath.get(j))) {
            j--;
        }
        smoothed.add(rawPath.get(j));
        i = j;
    }

    return smoothed;
}

/**
 * Bresenham直线算法判断两点之间是否有视线（无障碍）
 */
private boolean hasLineOfSight(GameMap map, Node a, Node b) {
    int x0 = a.col, y0 = a.row;
    int x1 = b.col, y1 = b.row;
    int dx = Math.abs(x1 - x0), 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.isPassable(y0, x0)) 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;
}

核心算法二：有限状态机敌人AI

单个敌人的行为如果只有”追玩家”，游戏会很快乏味。有限状态机（Finite State Machine, FSM）将敌人行为拆分为若干离散状态，根据环境条件在不同状态间切换。

状态设计

FSM Java实现

/**
 * 敌人AI状态枚举
 */
public enum AIState {
    PATROL,       // 巡逻
    CHASE,        // 追击
    ATTACK_BASE,  // 攻击基地
    EVADE,        // 规避炮弹
    SURROUND      // 围攻
}

/**
 * 有限状态机驱动的敌人坦克AI
 * 根据感知信息动态切换行为状态
 */
public class EnemyTankAI {

    private AIState currentState = AIState.PATROL;
    private final Tank self;           // 自己
    private final Tank player;         // 玩家坦克
    private final GameMap map;
    private final AStarPathfinder pathfinder;
    private final List<Node> currentPath = new ArrayList<>();
    private int pathIndex = 0;
    private int patrolTimer = 0;
    private static final int PATROL_INTERVAL = 60; // 每60帧更换巡逻方向

    public EnemyTankAI(Tank self, Tank player, GameMap map) {
        this.self = self;
        this.player = player;
        this.map = map;
        this.pathfinder = new AStarPathfinder(map);
    }

    /**
     * 每帧调用：感知环境 → 状态转移 → 执行行为
     */
    public void update() {
        Perception perception = perceive();
        transition(perception);
        execute(perception);
    }

    /**
     * 感知层：收集决策所需的全部环境信息
     */
    private Perception perceive() {
        Perception p = new Perception();
        p.playerVisible = hasLineOfSightToPlayer();
        p.playerDistance = Math.abs(self.row - player.row) + Math.abs(self.col - player.col);
        p.bulletApproaching = detectIncomingBullet();
        p.lowHealth = self.hp < self.maxHp * 0.3;
        p.nearAllies = countNearbyAllies();
        p.playerIsolated = p.nearAllies >= 2 && p.playerDistance < 8;
        return p;
    }

    /**
     * 状态转移层：根据感知信息决定下一状态
     */
    private void transition(Perception p) {
        AIState next = currentState;

        switch (currentState) {
            case PATROL:
                if (p.bulletApproaching) next = AIState.EVADE;
                else if (p.playerVisible && !p.lowHealth) next = AIState.CHASE;
                else if (patrolTimer > PATROL_INTERVAL * 3) next = AIState.ATTACK_BASE;
                break;

            case CHASE:
                if (p.bulletApproaching) next = AIState.EVADE;
                else if (!p.playerVisible) next = AIState.PATROL;
                else if (p.playerIsolated) next = AIState.SURROUND;
                else if (p.lowHealth && p.playerDistance < 5) next = AIState.EVADE;
                break;

            case ATTACK_BASE:
                if (p.bulletApproaching) next = AIState.EVADE;
                else if (p.playerVisible && !p.lowHealth) next = AIState.CHASE;
                break;

            case EVADE:
                if (!p.bulletApproaching) {
                    // 安全后恢复追击或巡逻
                    next = p.playerVisible ? AIState.CHASE : AIState.PATROL;
                }
                break;

            case SURROUND:
                if (!p.playerIsolated || p.bulletApproaching) next = AIState.CHASE;
                break;
        }

        // 状态变化时重置路径
        if (next != currentState) {
            currentPath.clear();
            pathIndex = 0;
        }
        currentState = next;
    }

    /**
     * 行为执行层：根据当前状态输出具体的移动和射击指令
     */
    private void execute(Perception p) {
        switch (currentState) {
            case PATROL:
                patrol();
                break;
            case CHASE:
                chasePlayer();
                break;
            case ATTACK_BASE:
                attackBase();
                break;
            case EVADE:
                evade();
                break;
            case SURROUND:
                surround();
                break;
        }

        // 状态无关：如果可以直线射击玩家则开火
        if (canShootPlayer()) {
            self.fire();
        }
    }

    /**
     * 巡逻行为：在当前区域随机移动
     */
    private void patrol() {
        patrolTimer++;
        if (patrolTimer % PATROL_INTERVAL == 0 || currentPath.isEmpty()) {
            // 随机选择一个可达的相邻点
            List<int[]> candidates = new ArrayList<>();
            for (int[] d : new int[][]{{-1,0},{1,0},{0,-1},{0,1}}) {
                int nr = self.row + d[0], nc = self.col + d[1];
                if (map.isPassable(nr, nc)) candidates.add(new int[]{nr, nc});
            }
            if (!candidates.isEmpty()) {
                int[] pick = candidates.get(new Random().nextInt(candidates.size()));
                moveTowards(pick[0], pick[1]);
            }
        }
    }

    /**
     * 追击行为：A星寻路到玩家当前位置
     */
    private void chasePlayer() {
        if (currentPath.isEmpty() || pathIndex >= currentPath.size()) {
            List<Node> path = pathfinder.findPath(self.row, self.col, player.row, player.col);
            if (!path.isEmpty()) {
                currentPath.clear();
                currentPath.addAll(path);
                pathIndex = 1; // 从第二个点开始移动（第一个是自身位置）
            }
        }
        if (pathIndex < currentPath.size()) {
            Node next = currentPath.get(pathIndex);
            if (moveTowards(next.row, next.col)) {
                pathIndex++;
            }
        }
    }

    /**
     * 攻击基地行为：寻路到地图底部中央的基地
     */
    private void attackBase() {
        int baseRow = map.getRows() - 2;
        int baseCol = map.getCols() / 2;
        if (currentPath.isEmpty() || pathIndex >= currentPath.size()) {
            List<Node> path = pathfinder.findPath(self.row, self.col, baseRow, baseCol);
            if (!path.isEmpty()) {
                currentPath.clear();
                currentPath.addAll(path);
                pathIndex = 1;
            }
        }
        if (pathIndex < currentPath.size()) {
            Node next = currentPath.get(pathIndex);
            if (moveTowards(next.row, next.col)) {
                pathIndex++;
            }
        }
    }

    /**
     * 规避行为：向垂直于炮弹方向移动
     */
    private void evade() {
        // 简化为：向远离炮弹最近方向的垂直方向移动
        // 实际游戏中应结合炮弹飞行方向计算
        List<int[]> safeDirs = new ArrayList<>();
        for (int[] d : new int[][]{{-1,0},{1,0},{0,-1},{0,1}}) {
            int nr = self.row + d[0] * 2, nc = self.col + d[1] * 2;
            if (map.isPassable(nr, nc)) safeDirs.add(d);
        }
        if (!safeDirs.isEmpty()) {
            int[] pick = safeDirs.get(new Random().nextInt(safeDirs.size()));
            moveTowards(self.row + pick[0], self.col + pick[1]);
        }
    }

    /**
     * 围攻行为：从玩家相对方向的两侧包抄
     */
    private void surround() {
        // 计算玩家到基地的方向向量，从侧翼包抄
        int dr = player.row - self.row;
        int dc = player.col - self.col;
        // 侧向偏移：垂直于追击方向
        int sideR = (dc != 0) ? 1 : 0;
        int sideC = (dr != 0) ? 1 : 0;

        int targetR = player.row + sideR * 2;
        int targetC = player.col + sideC * 2;

        if (currentPath.isEmpty() || pathIndex >= currentPath.size()) {
            List<Node> path = pathfinder.findPath(self.row, self.col, targetR, targetC);
            if (!path.isEmpty()) {
                currentPath.clear();
                currentPath.addAll(path);
                pathIndex = 1;
            }
        }
        if (pathIndex < currentPath.size()) {
            Node next = currentPath.get(pathIndex);
            if (moveTowards(next.row, next.col)) {
                pathIndex++;
            }
        }
    }

    /**
     * 向目标位置移动一步，成功返回true
     */
    private boolean moveTowards(int targetRow, int targetCol) {
        int dr = Integer.compare(targetRow, self.row);
        int dc = Integer.compare(targetCol, self.col);
        if (dr != 0 && map.isPassable(self.row + dr, self.col)) {
            self.row += dr;
            return true;
        }
        if (dc != 0 && map.isPassable(self.row, self.col + dc)) {
            self.col += dc;
            return true;
        }
        return false;
    }

    /**
     * 检查是否能直线射击玩家（同一直行或同一直列且无遮挡）
     */
    private boolean canShootPlayer() {
        if (self.row == player.row) {
            int min = Math.min(self.col, player.col);
            int max = Math.max(self.col, player.col);
            for (int c = min + 1; c < max; c++) {
                if (!map.getCell(self.row, c).isPassable()) return false;
            }
            return true;
        }
        if (self.col == player.col) {
            int min = Math.min(self.row, player.row);
            int max = Math.max(self.row, player.row);
            for (int r = min + 1; r < max; r++) {
                if (!map.getCell(r, self.col).isPassable()) return false;
            }
            return true;
        }
        return false;
    }

    private boolean hasLineOfSightToPlayer() {
        // 简化为：在一定距离内且A星路径不太长
        int dist = Math.abs(self.row - player.row) + Math.abs(self.col - player.col);
        return dist <= 15;
    }

    private boolean detectIncomingBullet() {
        // 简化检测：检查同一行/列前方是否有敌方炮弹
        // 实际实现中需要遍历所有活跃炮弹
        return false; // 占位，实际游戏接入炮弹管理器
    }

    private int countNearbyAllies() {
        // 占位，实际游戏接入敌人管理器统计距离小于5的友军数量
        return 1;
    }

    public AIState getCurrentState() { return currentState; }
}

/**
 * 感知信息结构体
 */
class Perception {
    boolean playerVisible;     // 玩家是否在感知范围内
    int playerDistance;        // 与玩家的曼哈顿距离
    boolean bulletApproaching; // 是否有炮弹接近
    boolean lowHealth;         // 是否低血量
    int nearAllies;            // 附近友军数量
    boolean playerIsolated;    // 玩家是否被包围
}

/**
 * 坦克实体（简化版）
 */
class Tank {
    int row, col;
    int hp = 3;
    int maxHp = 3;
    Direction dir = Direction.UP;

    void fire() {
        // 发射炮弹
    }
}

enum Direction { UP, DOWN, LEFT, RIGHT }

多智能体协调：围攻策略

当场景中存在多个敌人时，FSM可以扩展为分层状态机。上层协调器为每个敌人分配角色（主攻/侧翼/后卫），下层各敌人仍运行自己的FSM。

/**
 * 多智能体协调器：为每个敌人分配战术角色
 */
public class SquadCoordinator {

    public enum Role {
        ATTACKER,   // 正面主攻
        FLANKER,    // 侧翼包抄
        DEFENDER    // 后方警戒/保护基地
    }

    /**
     * 根据局势为每个敌人分配角色
     */
    public Map<EnemyTankAI, Role> assignRoles(
            List<EnemyTankAI> enemies,
            Tank player,
            GameMap map) {

        Map<EnemyTankAI, Role> assignments = new HashMap<>();
        if (enemies.isEmpty()) return assignments;

        // 距离玩家最近的敌人担任主攻
        enemies.sort(Comparator.comparingInt(e ->
            Math.abs(e.getSelf().row - player.row) + Math.abs(e.getSelf().col - player.col)));

        assignments.put(enemies.get(0), Role.ATTACKER);

        if (enemies.size() >= 2) {
            assignments.put(enemies.get(1), Role.FLANKER);
        }
        if (enemies.size() >= 3) {
            assignments.put(enemies.get(2), Role.DEFENDER);
        }

        // 其余敌人默认攻击
        for (int i = 3; i < enemies.size(); i++) {
            assignments.put(enemies.get(i), Role.ATTACKER);
        }

        return assignments;
    }
}

完整游戏模拟与测试

/**
 * 坦克大战AI测试主程序
 * 创建地图、生成敌人并运行AI循环
 */
public class TankBattleGame {

    public static void main(String[] args) {
        // 创建13x13的测试地图
        GameMap map = new GameMap(13, 13);

        // 设置地图边界为钢墙
        for (int i = 0; i < 13; i++) {
            map.setCell(0, i, CellType.STEEL);
            map.setCell(12, i, CellType.STEEL);
            map.setCell(i, 0, CellType.STEEL);
            map.setCell(i, 12, CellType.STEEL);
        }

        // 随机放置砖墙障碍
        Random rand = new Random(42);
        for (int i = 0; i < 20; i++) {
            int r = 2 + rand.nextInt(9);
            int c = 2 + rand.nextInt(9);
            map.setCell(r, c, CellType.BRICK);
        }

        // 创建玩家与敌人
        Tank player = new Tank();
        player.row = 6; player.col = 6;

        Tank enemyTank = new Tank();
        enemyTank.row = 2; enemyTank.col = 2;

        EnemyTankAI enemyAI = new EnemyTankAI(enemyTank, player, map);
        AStarPathfinder pf = new AStarPathfinder(map);

        // 测试A星寻路
        System.out.println("=== A星寻路测试 ===");
        List<AStarPathfinder.Node> path = pf.findPath(2, 2, 6, 6);
        System.out.println("路径长度: " + path.size());
        for (AStarPathfinder.Node n : path) {
            System.out.print("(" + n.row + "," + n.col + ") ");
        }
        System.out.println();

        // 模拟20帧AI行为
        System.out.println("\n=== FSM行为模拟（20帧）===");
        for (int frame = 0; frame < 20; frame++) {
            enemyAI.update();
            System.out.printf("Frame %2d: 状态=%s, 位置=(%d,%d), 玩家=(%d,%d)%n",
                frame,
                enemyAI.getCurrentState(),
                enemyTank.row, enemyTank.col,
                player.row, player.col);

            // 模拟玩家轻微移动
            if (frame % 5 == 0) {
                player.col = Math.max(2, Math.min(10, player.col + (rand.nextBoolean() ? 1 : -1)));
            }
        }
    }
}

复杂度与扩展分析

进阶扩展方向

1. 带权A星：为草地、泥地设置不同移动代价，使路径更贴近人类直觉。
2. 行为树替代FSM：当状态超过10个时，行为树（Behavior Tree）比FSM更易维护，支持并行节点与条件装饰器。
3. 潜在场法（Potential Field）：用吸引力场引导敌人靠近玩家，排斥力场避开炮弹与障碍，实现更平滑的连续运动。
4. 在线学习：记录玩家常用移动模式，用Q-Learning动态调整敌人预判射击的提前量。

总结

本文从坦克大战这一经典游戏出发，完整实现了 enemy AI 的两个核心模块：

• A星寻路：在动态网格地图中计算最短可通行路径，通过曼哈顿距离启发函数保证搜索效率，配合路径平滑减少机械感。
• 有限状态机：将敌人行为拆解为巡逻、追击、攻击基地、规避和围攻五个状态，通过感知-转移-执行三层架构实现清晰的行为逻辑。

多智能体协调层进一步赋予敌人团队协作能力。读者可在此基础上继续扩展：引入行为树处理更复杂的决策逻辑，使用潜在场法实现连续空间运动，或将A星与JPS（Jump Point Search）结合以加速大规模地图寻路。