每日算法 — 使用java实现吃豆人：幽灵AI状态机与A*寻路追击策略

吃豆人（Pac-Man）是街机游戏史上最具影响力的作品之一。其魅力不仅在于简单的操作，更在于四个幽灵（Ghost）各具特色的追击AI——它们并非盲目追逐，而是遵循一套精妙的状态机与寻路策略协同工作。本文将用Java复刻这套经典AI，深入讲解状态机模式管理幽灵行为、A*寻路计算追击路线，以及四种幽灵截然不同的”个性”算法。

一、问题建模：吃豆人的游戏世界

我们将游戏抽象为一个二维网格地图，包含以下元素：

1.1 核心数据结构

/**
 * 地图单元格类型
 */
public enum CellType {
    WALL,       // 墙壁
    DOT,        // 普通豆子
    POWER_DOT,  // 能量豆
    EMPTY       // 空地
}

/**
 * 二维坐标点
 */
public record Position(int x, int y) {
    public Position add(int dx, int dy) {
        return new Position(x + dx, y + dy);
    }

    /**
     * 曼哈顿距离（A*启发函数的基础）
     */
    public int manhattanDistance(Position other) {
        return Math.abs(this.x - other.x) + Math.abs(this.y - other.y);
    }

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

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

1.2 游戏地图类

import java.util.*;

/**
 * 游戏地图，负责碰撞检测与路径查询
 */
public class GameMap {
    private final int width;
    private final int height;
    private final CellType[][] grid;
    private final Set<Position> dots;
    private final Set<Position> powerDots;
    private Position pacmanStart;
    private final List<Position> ghostStarts;

    public GameMap(String[] layout) {
        this.height = layout.length;
        this.width = layout[0].length();
        this.grid = new CellType[height][width];
        this.dots = new HashSet<>();
        this.powerDots = new HashSet<>();
        this.ghostStarts = new ArrayList<>();

        for (int y = 0; y < height; y++) {
            for (int x = 0; x < width; x++) {
                char c = layout[y].charAt(x);
                switch (c) {
                    case '#' -> grid[y][x] = CellType.WALL;
                    case '.' -> {
                        grid[y][x] = CellType.DOT;
                        dots.add(new Position(x, y));
                    }
                    case 'O' -> {
                        grid[y][x] = CellType.POWER_DOT;
                        powerDots.add(new Position(x, y));
                    }
                    case 'P' -> {
                        grid[y][x] = CellType.EMPTY;
                        pacmanStart = new Position(x, y);
                    }
                    case 'G' -> {
                        grid[y][x] = CellType.EMPTY;
                        ghostStarts.add(new Position(x, y));
                    }
                    default -> grid[y][x] = CellType.EMPTY;
                }
            }
        }
    }

    public boolean isWalkable(int x, int y) {
        return x >= 0 && x < width && y >= 0 && y < height && grid[y][x] != CellType.WALL;
    }

    public boolean isWalkable(Position p) {
        return isWalkable(p.x(), p.y());
    }

    public int getWidth() { return width; }
    public int getHeight() { return height; }
    public Position getPacmanStart() { return pacmanStart; }
    public List<Position> getGhostStarts() { return ghostStarts; }
    public Set<Position> getDots() { return dots; }
    public Set<Position> getPowerDots() { return powerDots; }

    /**
     * 获取某位置的可行走邻居（四方向）
     */
    public List<Position> getNeighbors(Position p) {
        List<Position> neighbors = new ArrayList<>();
        int[][] dirs = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
        for (int[] d : dirs) {
            Position np = p.add(d[0], d[1]);
            if (isWalkable(np)) {
                neighbors.add(np);
            }
        }
        return neighbors;
    }
}

二、状态机：幽灵行为的四大模式

原版吃豆人的幽灵AI由四种状态驱动，状态之间的切换由定时器和游戏事件触发。这是有限状态机（Finite State Machine, FSM）的经典应用。

2.1 状态定义

/**
 * 幽灵AI的四种核心状态
 */
public enum GhostState {
    SCATTER,      // 散点模式：幽灵前往各自角落，不给玩家太大压力
    CHASE,        // 追击模式：幽灵主动追击吃豆人
    FRIGHTENED,   // 受惊模式：吃豆人吃了能量豆，幽灵随机逃窜
    DEAD          // 死亡模式：被吃豆人吃掉，返回出生点重生
}

2.2 状态转换规则

/**
 * 状态机控制器，管理全局的散点/追击切换时序
 * 原版游戏采用固定的时间表循环切换 SCATTER 和 CHASE
 */
public class StateMachineScheduler {
    // 原版街机的时间表（秒）：散点时长 -> 追击时长 -> 散点 -> 追击 ...
    private static final int[] SCATTER_DURATIONS = {7, 7, 5, 5};
    private static final int[] CHASE_DURATIONS = {20, 20, 20, Integer.MAX_VALUE};

    private int phaseIndex = 0;
    private GhostState currentGlobalState = GhostState.SCATTER;
    private int timer = 0;
    private boolean running = true;

    /**
     * 每帧调用，更新全局状态
     */
    public void tick() {
        if (!running || currentGlobalState == GhostState.DEAD) return;

        timer++;
        int limit = (currentGlobalState == GhostState.SCATTER)
                ? SCATTER_DURATIONS[phaseIndex]
                : CHASE_DURATIONS[phaseIndex];

        if (timer >= limit * 60) { // 假设60FPS
            timer = 0;
            if (currentGlobalState == GhostState.SCATTER) {
                currentGlobalState = GhostState.CHASE;
            } else {
                phaseIndex++;
                if (phaseIndex < SCATTER_DURATIONS.length) {
                    currentGlobalState = GhostState.SCATTER;
                }
            }
        }
    }

    public GhostState getCurrentGlobalState() {
        return currentGlobalState;
    }

    /**
     * 当吃豆人吃到能量豆时触发：所有非死亡幽灵进入 frightened 状态
     */
    public void triggerPowerDot() {
        // 注意：frightened 是覆盖态，不修改全局时间表
        // 由各个幽灵自行判断当前是否应该 frightened
    }

    /**
     * 获取当前阶段的剩余时间（用于调试显示）
     */
    public int getRemainingTime() {
        int limit = (currentGlobalState == GhostState.SCATTER)
                ? SCATTER_DURATIONS[phaseIndex]
                : CHASE_DURATIONS[phaseIndex];
        return limit * 60 - timer;
    }
}

2.3 单只幽灵的状态机实现

/**
 * 单个幽灵的状态机，结合全局调度与本地状态
 */
public class GhostStateMachine {
    private GhostState currentState;
    private final Position scatterTarget;   // 散点模式目标角落
    private final Position home;            // 出生点/重生目标
    private int frightenedTimer = 0;
    private static final int FRIGHTENED_DURATION = 6 * 60; // 6秒

    public GhostStateMachine(Position scatterTarget, Position home) {
        this.currentState = GhostState.SCATTER;
        this.scatterTarget = scatterTarget;
        this.home = home;
    }

    /**
     * 根据全局调度和游戏事件更新当前状态
     */
    public void update(GhostState globalState, boolean powerDotActive, boolean eaten) {
        if (eaten) {
            currentState = GhostState.DEAD;
            return;
        }

        if (currentState == GhostState.DEAD) {
            // 到达出生点后复活
            return;
        }

        if (powerDotActive && currentState != GhostState.FRIGHTENED) {
            currentState = GhostState.FRIGHTENED;
            frightenedTimer = FRIGHTENED_DURATION;
        }

        if (currentState == GhostState.FRIGHTENED) {
            frightenedTimer--;
            if (frightenedTimer <= 0) {
                currentState = globalState; // 恢复全局状态
            }
            return;
        }

        // 正常情况下跟随全局调度
        currentState = globalState;
    }

    public GhostState getCurrentState() {
        return currentState;
    }

    public Position getScatterTarget() {
        return scatterTarget;
    }

    public Position getHome() {
        return home;
    }

    public boolean isFrightened() {
        return currentState == GhostState.FRIGHTENED;
    }

    public boolean isDead() {
        return currentState == GhostState.DEAD;
    }
}

三、A*寻路：计算最短追击路线

幽灵在追击吃豆人时，需要计算从当前位置到目标位置的最短路径。由于地图是网格且移动代价均一，A*算法是最佳选择——它在完备性和效率之间取得了完美平衡。

3.1 A*节点与启发函数

import java.util.*;

/**
 * A*寻路器
 */
public class AStarPathfinder {
    private final GameMap map;

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

    /**
     * A*搜索：从start到goal的最短路径
     * @return 路径上的位置列表（不含起点，含终点），不可达则返回空列表
     */
    public List<Position> findPath(Position start, Position goal) {
        // openSet：待探索的节点，按fScore排序
        PriorityQueue<Node> openSet = new PriorityQueue<>(Comparator.comparingInt(n -> n.fScore));
        // closedSet：已探索的节点
        Set<Position> closedSet = new HashSet<>();
        // cameFrom：记录路径来源
        Map<Position, Position> cameFrom = new HashMap<>();
        // gScore：从起点到当前节点的实际代价
        Map<Position, Integer> gScore = new HashMap<>();

        openSet.add(new Node(start, 0, start.manhattanDistance(goal)));
        gScore.put(start, 0);

        while (!openSet.isEmpty()) {
            Node current = openSet.poll();
            Position currentPos = current.position;

            if (currentPos.equals(goal)) {
                return reconstructPath(cameFrom, currentPos, start);
            }

            if (closedSet.contains(currentPos)) continue;
            closedSet.add(currentPos);

            for (Position neighbor : map.getNeighbors(currentPos)) {
                if (closedSet.contains(neighbor)) continue;

                int tentativeG = gScore.get(currentPos) + 1;

                if (!gScore.containsKey(neighbor) || tentativeG < gScore.get(neighbor)) {
                    cameFrom.put(neighbor, currentPos);
                    gScore.put(neighbor, tentativeG);
                    int fScore = tentativeG + neighbor.manhattanDistance(goal);
                    openSet.add(new Node(neighbor, tentativeG, fScore));
                }
            }
        }

        return Collections.emptyList(); // 不可达
    }

    private List<Position> reconstructPath(Map<Position, Position> cameFrom, Position current, Position start) {
        LinkedList<Position> path = new LinkedList<>();
        while (!current.equals(start)) {
            path.addFirst(current);
            current = cameFrom.get(current);
        }
        return path;
    }

    private record Node(Position position, int gScore, int fScore) {}
}

3.2 复杂度分析

由于启发函数可采纳（admissible），A*保证找到最优解。

四、四种幽灵的”个性”：目标选择策略

原版吃豆人的四大幽灵（Blinky、Pinky、Inky、Clyde）之所以让玩家感到”有灵性”，关键在于它们各自采用了不同的目标点计算策略。它们共享同一套A*寻路引擎，但输入的目标点各不相同。

4.1 目标策略接口与实现

/**
 * 幽灵目标选择策略接口
 */
public interface TargetStrategy {
    Position selectTarget(Position ghostPos, Position pacmanPos,
                          Direction pacmanDir, GameMap map);
}

/**
 * 移动方向枚举
 */
public enum Direction {
    UP(0, -1), DOWN(0, 1), LEFT(-1, 0), RIGHT(1, 0);
    public final int dx, dy;
    Direction(int dx, int dy) { this.dx = dx; this.dy = dy; }
}

/**
 * Blinky（赤鬼）：直接追击吃豆人当前位置
 * 特点：最积极、最直接的追击者
 */
public class BlinkyStrategy implements TargetStrategy {
    @Override
    public Position selectTarget(Position ghostPos, Position pacmanPos,
                                  Direction pacmanDir, GameMap map) {
        return pacmanPos;
    }
}

/**
 * Pinky（粉鬼）：预判吃豆人前方4格位置
 * 特点：试图"堵截"吃豆人的前进路线
 */
public class PinkyStrategy implements TargetStrategy {
    private static final int LOOK_AHEAD = 4;

    @Override
    public Position selectTarget(Position ghostPos, Position pacmanPos,
                                  Direction pacmanDir, GameMap map) {
        Position target = pacmanPos.add(pacmanDir.dx * LOOK_AHEAD, pacmanDir.dy * LOOK_AHEAD);
        // 如果目标点在墙里，退而求其次使用吃豆人当前位置
        return map.isWalkable(target) ? target : pacmanPos;
    }
}

/**
 * Inky（青鬼）：基于Blinky位置和吃豆人前方位置的对称点
 * 特点：最复杂、最难预测，依赖队友位置
 */
public class InkyStrategy implements TargetStrategy {
    private final TargetStrategy blinkyStrategy;
    private Position blinkyPos;

    public InkyStrategy() {
        this.blinkyStrategy = new BlinkyStrategy();
    }

    public void setBlinkyPosition(Position pos) {
        this.blinkyPos = pos;
    }

    @Override
    public Position selectTarget(Position ghostPos, Position pacmanPos,
                                  Direction pacmanDir, GameMap map) {
        if (blinkyPos == null) return pacmanPos;

        // 计算吃豆人前方2格
        Position pivot = pacmanPos.add(pacmanDir.dx * 2, pacmanDir.dy * 2);
        // 以pivot为对称中心，计算Blinky的对称点
        int targetX = pivot.x() + (pivot.x() - blinkyPos.x());
        int targetY = pivot.y() + (pivot.y() - blinkyPos.y());
        Position target = new Position(targetX, targetY);

        return map.isWalkable(target) ? target : pacmanPos;
    }
}

/**
 * Clyde（橙鬼）：距离远时追击，距离近时逃回左下角
 * 特点："假装努力"，给玩家喘息机会
 */
public class ClydeStrategy implements TargetStrategy {
    private static final int CHASE_DISTANCE = 8;
    private final Position retreatCorner;

    public ClydeStrategy(Position retreatCorner) {
        this.retreatCorner = retreatCorner;
    }

    @Override
    public Position selectTarget(Position ghostPos, Position pacmanPos,
                                  Direction pacmanDir, GameMap map) {
        int dist = ghostPos.manhattanDistance(pacmanPos);
        if (dist > CHASE_DISTANCE) {
            return pacmanPos; // 距离远，假装追击
        } else {
            return retreatCorner; // 距离近，溜回角落
        }
    }
}

4.2 策略效果对比

四种策略的组合产生了 emergent behavior（涌现行为）：玩家感觉被”包围”，实际上是独立简单规则的叠加效果。

五、幽灵实体：整合状态机、寻路与个性

/**
 * 幽灵实体类：整合状态机、寻路、目标策略
 */
public class Ghost {
    private Position position;
    private final Position home;
    private final GhostStateMachine stateMachine;
    private final TargetStrategy strategy;
    private final AStarPathfinder pathfinder;
    private final GameMap map;
    private final String name;
    private List<Position> currentPath;
    private boolean eaten = false;

    public Ghost(String name, Position start, Position home, Position scatterTarget,
                 TargetStrategy strategy, AStarPathfinder pathfinder, GameMap map) {
        this.name = name;
        this.position = start;
        this.home = home;
        this.strategy = strategy;
        this.pathfinder = pathfinder;
        this.map = map;
        this.stateMachine = new GhostStateMachine(scatterTarget, home);
        this.currentPath = new ArrayList<>();
    }

    /**
     * 幽灵决策核心：根据当前状态选择下一步移动
     */
    public void decide(Position pacmanPos, Direction pacmanDir,
                       GhostState globalState, boolean powerDotActive) {
        stateMachine.update(globalState, powerDotActive, eaten);
        GhostState state = stateMachine.getCurrentState();

        Position target;
        switch (state) {
            case SCATTER -> target = stateMachine.getScatterTarget();
            case CHASE -> target = strategy.selectTarget(position, pacmanPos, pacmanDir, map);
            case FRIGHTENED -> {
                // 受惊时随机选择一个可行走的邻居作为目标
                target = randomEscapeTarget();
            }
            case DEAD -> target = stateMachine.getHome();
            default -> target = pacmanPos;
        }

        currentPath = pathfinder.findPath(position, target);
    }

    /**
     * 执行移动：沿当前路径前进一步
     */
    public void move() {
        if (!currentPath.isEmpty()) {
            position = currentPath.remove(0);
        }

        // 如果死亡状态且已回到出生点，复活
        if (stateMachine.isDead() && position.equals(home)) {
            eaten = false;
            stateMachine.update(GhostState.SCATTER, false, false);
        }
    }

    private Position randomEscapeTarget() {
        List<Position> neighbors = map.getNeighbors(position);
        return neighbors.isEmpty() ? position : neighbors.get((int)(Math.random() * neighbors.size()));
    }

    public void setEaten(boolean eaten) {
        this.eaten = eaten;
    }

    public Position getPosition() { return position; }
    public String getName() { return name; }
    public GhostState getState() { return stateMachine.getCurrentState(); }
    public boolean isFrightened() { return stateMachine.isFrightened(); }

    @Override
    public String toString() {
        return String.format("%s[%s]@(%d,%d)", name, getState(), position.x(), position.y());
    }
}

六、吃豆人游戏主循环

import java.util.*;

/**
 * 吃豆人游戏主类（控制台版本）
 */
public class PacmanGame {
    private final GameMap map;
    private Position pacman;
    private Direction pacmanDir = Direction.RIGHT;
    private final List<Ghost> ghosts;
    private final AStarPathfinder pathfinder;
    private final StateMachineScheduler scheduler;
    private int score = 0;
    private boolean powerDotActive = false;
    private int powerDotTimer = 0;
    private boolean gameOver = false;
    private boolean won = false;

    public PacmanGame() {
        String[] layout = {
            "###################",
            "#........#........#",
            "#.##.###.#.###.##.#",
            "#O...............O#",
            "#.##.#.#####.#.##.#",
            "#....#...#...#....#",
            "####.###.#.###.####",
            "   #.#.......#.#   ",
            "####.#.##G##.#.####",
            "#........P........#",
            "#.##.###.#.###.##.#",
            "#O...............O#",
            "#.##.###.#.###.##.#",
            "#........#........#",
            "###################"
        };

        this.map = new GameMap(layout);
        this.pathfinder = new AStarPathfinder(map);
        this.scheduler = new StateMachineScheduler();
        this.pacman = map.getPacmanStart();

        List<Position> ghostStarts = map.getGhostStarts();
        this.ghosts = new ArrayList<>();

        // Blinky - 赤鬼，直接追击
        ghosts.add(new Ghost("Blinky", ghostStarts.get(0), ghostStarts.get(0),
                new Position(map.getWidth() - 2, 1),
                new BlinkyStrategy(), pathfinder, map));

        // Pinky - 粉鬼，前方拦截
        ghosts.add(new Ghost("Pinky", ghostStarts.get(0), ghostStarts.get(0),
                new Position(1, 1),
                new PinkyStrategy(), pathfinder, map));

        // Inky - 青鬼，对称包抄（需要Blinky位置引用）
        InkyStrategy inkyStrat = new InkyStrategy();
        Ghost inky = new Ghost("Inky", ghostStarts.get(0), ghostStarts.get(0),
                new Position(map.getWidth() - 2, map.getHeight() - 2),
                inkyStrat, pathfinder, map);
        ghosts.add(inky);

        // Clyde - 橙鬼，远近切换
        ghosts.add(new Ghost("Clyde", ghostStarts.get(0), ghostStarts.get(0),
                new Position(1, map.getHeight() - 2),
                new ClydeStrategy(new Position(1, map.getHeight() - 2)), pathfinder, map));
    }

    /**
     * 执行一帧游戏循环
     */
    public void tick() {
        if (gameOver) return;

        scheduler.tick();
        GhostState globalState = scheduler.getCurrentGlobalState();

        // 更新能量豆计时
        if (powerDotActive) {
            powerDotTimer--;
            if (powerDotTimer <= 0) {
                powerDotActive = false;
            }
        }

        // 吃豆人移动（简化版：沿当前方向前进，遇到墙则停止）
        Position nextPacman = pacman.add(pacmanDir.dx, pacmanDir.dy);
        if (map.isWalkable(nextPacman)) {
            pacman = nextPacman;
        }

        // 吃豆子
        if (map.getDots().remove(pacman)) {
            score += 10;
        }
        if (map.getPowerDots().remove(pacman)) {
            score += 50;
            powerDotActive = true;
            powerDotTimer = 6 * 60;
        }

        // 更新Inky的Blinky位置引用
        for (Ghost g : ghosts) {
            if (g.getName().equals("Inky")) {
                Ghost blinky = ghosts.stream().filter(gh -> gh.getName().equals("Blinky"))
                        .findFirst().orElse(null);
                if (blinky != null && g.getStrategy() instanceof InkyStrategy is) {
                    is.setBlinkyPosition(blinky.getPosition());
                }
            }
        }

        // 幽灵决策与移动
        for (Ghost ghost : ghosts) {
            ghost.decide(pacman, pacmanDir, globalState, powerDotActive);
            ghost.move();
        }

        // 碰撞检测
        for (Ghost ghost : ghosts) {
            if (ghost.getPosition().equals(pacman)) {
                if (ghost.isFrightened()) {
                    ghost.setEaten(true);
                    score += 200;
                } else if (!ghost.isDead()) {
                    gameOver = true;
                    return;
                }
            }
        }

        // 胜利条件
        if (map.getDots().isEmpty() && map.getPowerDots().isEmpty()) {
            won = true;
            gameOver = true;
        }
    }

    /**
     * 渲染控制台画面
     */
    public void render() {
        System.out.print("\033[H\033[2J"); // 清屏
        for (int y = 0; y < map.getHeight(); y++) {
            for (int x = 0; x < map.getWidth(); x++) {
                Position p = new Position(x, y);
                if (p.equals(pacman)) {
                    System.out.print("P ");
                } else if (ghosts.stream().anyMatch(g -> g.getPosition().equals(p))) {
                    Ghost g = ghosts.stream().filter(gh -> gh.getPosition().equals(p)).findFirst().get();
                    System.out.print(g.isFrightened() ? "? " : g.getName().charAt(0) + " ");
                } else if (map.getPowerDots().contains(p)) {
                    System.out.print("O ");
                } else if (map.getDots().contains(p)) {
                    System.out.print(". ");
                } else if (!map.isWalkable(p)) {
                    System.out.print("# ");
                } else {
                    System.out.print("  ");
                }
            }
            System.out.println();
        }
        System.out.println("Score: " + score + " | State: " + scheduler.getCurrentGlobalState() +
                " | Power: " + (powerDotActive ? powerDotTimer / 60 + "s" : "off"));
        for (Ghost g : ghosts) {
            System.out.println(g);
        }
    }

    public boolean isGameOver() { return gameOver; }
    public boolean isWon() { return won; }
    public int getScore() { return score; }

    public void setPacmanDirection(Direction dir) {
        this.pacmanDir = dir;
    }

    public static void main(String[] args) throws InterruptedException {
        PacmanGame game = new PacmanGame();
        int maxFrames = 3000;
        int frame = 0;

        System.out.println("=== 吃豆人 AI 演示 ===");
        System.out.println("P = 吃豆人, B = Blinky, K = Pinky, I = Inky, C = Clyde");
        System.out.println("? = 受惊幽灵, # = 墙壁, . = 豆子, O = 能量豆");
        Thread.sleep(2000);

        while (!game.isGameOver() && frame < maxFrames) {
            game.tick();
            game.render();
            Thread.sleep(50); // 约20 FPS
            frame++;
        }

        System.out.println(game.isWon() ? "\n🎉 胜利！Score: " + game.getScore()
                : "\n💀 游戏结束！Score: " + game.getScore());
    }
}

七、项目结构

pacman-ai/
├── src/
│   ├── model/
│   │   ├── CellType.java
│   │   ├── Direction.java
│   │   └── Position.java
│   ├── map/
│   │   └── GameMap.java
│   ├── ai/
│   │   ├── AStarPathfinder.java
│   │   ├── GhostState.java
│   │   ├── GhostStateMachine.java
│   │   └── StateMachineScheduler.java
│   ├── strategy/
│   │   ├── TargetStrategy.java
│   │   ├── BlinkyStrategy.java
│   │   ├── PinkyStrategy.java
│   │   ├── InkyStrategy.java
│   │   └── ClydeStrategy.java
│   ├── entity/
│   │   └── Ghost.java
│   └── game/
│       └── PacmanGame.java
└── README.md

八、算法总结与扩展

8.1 核心设计模式

本文实现了吃豆人幽灵AI的三层架构：

1. 状态机层：GhostStateMachine + StateMachineScheduler 管理行为模式切换，实现 SCATTER → CHASE → FRIGHTENED → DEAD 的完整生命周期
2. 策略层：TargetStrategy 接口封装四种幽灵的独特”个性”，同一套A*引擎驱动不同目标选择逻辑
3. 寻路层：AStarPathfinder 提供高效的最短路径计算，曼哈顿距离作为可采纳启发函数保证最优性

8.2 复杂度回顾

其中 G 为幽灵数量（通常4只），V 为地图可通行格子数。对于标准吃豆人地图（约200个可通行格），单帧计算在微秒级别。

8.3 扩展方向

• 更精细的地图：引入原版吃豆人的隧道（teleport）机制
• 行为树：将状态机升级为行为树，支持更复杂的条件判断
• 机器学习：用强化学习训练幽灵策略，替代手写规则
• 多人对战：增加联网对战模式，玩家可操控幽灵

九、结语

吃豆人的幽灵AI是游戏开发史上简单规则产生复杂行为的典范。四个幽灵仅通过”选择不同的目标点”这一微小差异，就营造出了包围、拦截、包抄、佯攻的丰富战术感。本文用Java完整复现了这套经典系统：状态机管理行为节奏，A算法计算最短路径，策略模式赋予每只幽灵独特的”灵魂”。理解这套设计，不仅有助于掌握寻路算法与状态机模式，更能深刻体会好的AI设计不在于复杂度，而在于规则组合的巧妙*。