引言
Pac-Man（吃豆人）是1980年由Namco发布的经典街机游戏，至今仍是游戏AI算法研究的标杆案例。本文将用Java完整实现Pac-Man的核心机制，重点讲解四个幽灵（Blinky、Pinky、Inky、Clyde）的AI行为：基于A*寻路算法计算最短追逐路径，结合有限状态机（FSM）实现追逐、散射、受惊、死亡四种行为模式切换。
核心算法设计
1. 游戏地图表示
Pac-Man地图由网格构成，每个格子分为墙壁、通道、豆子、能量豆四种类型。我们用二维整数数组表示地图，0为通道，1为墙壁，2为普通豆子，3为能量豆。
2. A*寻路算法
A*算法是启发式搜索的代表，公式为：f(n) = g(n) + h(n)，其中g(n)为从起点到n的实际代价，h(n)为n到终点的曼哈顿距离估计。
3. 幽灵状态机
四个幽灵各有独特的追逐策略：
– Blinky（红色）：直接追逐Pac-Man当前位置
– Pinky（粉色）：预判Pac-Man前方4格
– Inky（青色）：结合Blinky和Pac-Man位置计算反射目标
– Clyde（橙色）：距离近时追逐，距离远时随机游荡
完整Java实现
import java.util.*;
/**
* Pac-Man 核心实现：A*寻路与幽灵状态机
*/
public class PacManGame {
// 地图类型常量
static final int WALL = 1, DOT = 2, POWER = 3, EMPTY = 0;
// 方向向量：上、下、左、右
static final int[][] DIRS = {{-1,0},{1,0},{0,-1},{0,1}};
int rows, cols;
int[][] map; // 游戏地图
int score;
boolean gameOver;
Pacman pacman;
Ghost[] ghosts;
public PacManGame(int[][] map) {
this.map = map;
this.rows = map.length;
this.cols = map[0].length;
this.pacman = new Pacman(1, 1);
initGhosts();
}
void initGhosts() {
ghosts = new Ghost[4];
ghosts[0] = new Ghost(rows-2, 1, GhostType.BLINKY);
ghosts[1] = new Ghost(rows-2, cols-2, GhostType.PINKY);
ghosts[2] = new Ghost(1, cols-2, GhostType.INKY);
ghosts[3] = new Ghost(rows/2, cols/2, GhostType.CLYDE);
}
/** Pac-Man 玩家类 */
class Pacman {
int r, c, dir;
Pacman(int r, int c) { this.r=r; this.c=c; }
void move(int dr, int dc) {
int nr = r + dr, nc = c + dc;
if (isValid(nr, nc) && map[nr][nc] != WALL) {
r = nr; c = nc; dir = dr*2 + dc; // 简化方向编码
eatDot();
}
}
void eatDot() {
if (map[r][c] == DOT) { map[r][c] = EMPTY; score += 10; }
else if (map[r][c] == POWER) {
map[r][c] = EMPTY; score += 50; frightenGhosts();
}
}
}
/** 幽灵类型枚举 */
enum GhostType { BLINKY, PINKY, INKY, CLYDE }
/** 幽灵状态 */
enum GhostState { CHASE, SCATTER, FRIGHTENED, DEAD }
/** 幽灵类 */
class Ghost {
int r, c;
GhostType type;
GhostState state = GhostState.SCATTER;
int scatterTargetR, scatterTargetC;
Ghost(int r, int c, GhostType type) {
this.r=r; this.c=c; this.type=type;
// 每个幽灵有固定的散射角落目标
scatterTargetR = (type==GhostType.BLINKY||type==GhostType.PINKY)?0:rows-1;
scatterTargetC = (type==GhostType.BLINKY||type==GhostType.INKY)?0:cols-1;
}
/** 根据状态选择目标点，再调用A*移动一步 */
void moveStep() {
int[] target = selectTarget();
int[] next = aStarMove(r, c, target[0], target[1]);
if (next != null) { r = next[0]; c = next[1]; }
}
/** 不同幽灵的不同追逐策略 */
int[] selectTarget() {
switch (state) {
case SCATTERED: return new int[]{scatterTargetR, scatterTargetC};
case FRIGHTENED: return randomValidPoint();
case DEAD: return new int[]{rows/2, cols/2}; // 回巢复活
case CHASE:
default:
return chaseTarget();
}
}
int[] chaseTarget() {
int pr = pacman.r, pc = pacman.c;
switch (type) {
case BLINKY: return new int[]{pr, pc};
case PINKY:
// 预判Pac-Man前方4格
int[] pd = pacmanDirVector();
return new int[]{pr+pd[0]*4, pc+pd[1]*4};
case INKY:
// 以Blinky到Pac-Man前方2格的反射点为目标
int[] blinkyPos = ghosts[0] != this ? new int[]{ghosts[0].r, ghosts[0].c} : new int[]{r,c};
int[] pd2 = pacmanDirVector();
int pivotR = pr + pd2[0]*2, pivotC = pc + pd2[1]*2;
return new int[]{pivotR*2 - blinkyPos[0], pivotC*2 - blinkyPos[1]};
case CLYDE:
// 距离>8时追逐，<=8时回散射点
int dist = Math.abs(r-pr) + Math.abs(c-pc);
return dist > 8 ? new int[]{pr, pc} : new int[]{scatterTargetR, scatterTargetC};
default: return new int[]{pr, pc};
}
}
int[] pacmanDirVector() {
// 简化：假设Pac-Man向上移动，实际应从pacman.dir解析
return new int[]{-1, 0};
}
int[] randomValidPoint() {
// 受惊时随机选可达点
Random rand = new Random();
while (true) {
int rr = rand.nextInt(rows), cc = rand.nextInt(cols);
if (map[rr][cc] != WALL) return new int[]{rr, cc};
}
}
}
/** A*寻路：返回从(sr,sc)到(tr,tc)的下一步坐标 */
int[] aStarMove(int sr, int sc, int tr, int tc) {
// 边界检查与目标可达性修正
tr = Math.max(0, Math.min(rows-1, tr));
tc = Math.max(0, Math.min(cols-1, tc));
while (map[tr][tc] == WALL) { // 目标不可达时找最近可达点
if (tr > 0 && map[tr-1][tc] != WALL) { tr--; break; }
if (tr < rows-1 && map[tr+1][tc] != WALL) { tr++; break; }
if (tc > 0 && map[tr][tc-1] != WALL) { tc--; break; }
if (tc < cols-1 && map[tr][tc+1] != WALL) { tc++; break; }
tr = sr; tc = sc; break;
}
PriorityQueue<Node> open = new PriorityQueue<>(Comparator.comparingInt(n->n.f));
boolean[][] closed = new boolean[rows][cols];
Node[][] nodes = new Node[rows][cols];
Node start = new Node(sr, sc, 0, heuristic(sr, sc, tr, tc), null);
open.offer(start);
nodes[sr][sc] = start;
while (!open.isEmpty()) {
Node cur = open.poll();
if (cur.r == tr && cur.c == tc) break;
if (closed[cur.r][cur.c]) continue;
closed[cur.r][cur.c] = true;
for (int[] d : DIRS) {
int nr = cur.r + d[0], nc = cur.c + d[1];
if (!isValid(nr, nc) || map[nr][nc] == WALL || closed[nr][nc]) continue;
int ng = cur.g + 1;
Node neighbor = nodes[nr][nc];
if (neighbor == null || ng < neighbor.g) {
neighbor = new Node(nr, nc, ng, ng + heuristic(nr, nc, tr, tc), cur);
nodes[nr][nc] = neighbor;
open.offer(neighbor);
}
}
}
// 回溯找第一步
Node end = nodes[tr][tc];
if (end == null) return null;
while (end.parent != null && end.parent.parent != null) {
end = end.parent;
}
return end.parent == start ? new int[]{end.r, end.c} : null;
}
int heuristic(int r1, int c1, int r2, int c2) {
return Math.abs(r1-r2) + Math.abs(c1-c2); // 曼哈顿距离
}
boolean isValid(int r, int c) {
return r >= 0 && r < rows && c >= 0 && c < cols;
}
void frightenGhosts() {
for (Ghost g : ghosts) {
if (g.state != GhostState.DEAD) g.state = GhostState.FRIGHTENED;
}
}
/** A*节点 */
class Node {
int r, c, g, f;
Node parent;
Node(int r, int c, int g, int f, Node p) { this.r=r; this.c=c; this.g=g; this.f=f; this.parent=p; }
}
// 主循环框架
void gameLoop() {
Scanner sc = new Scanner(System.in);
while (!gameOver) {
printMap();
System.out.print("Move (W/A/S/D): ");
char cmd = sc.next().toUpperCase().charAt(0);
switch (cmd) {
case 'W': pacman.move(-1,0); break;
case 'S': pacman.move(1,0); break;
case 'A': pacman.move(0,-1); break;
case 'D': pacman.move(0,1); break;
}
for (Ghost g : ghosts) g.moveStep();
checkCollision();
}
System.out.println("Game Over! Score: " + score);
}
void checkCollision() {
for (Ghost g : ghosts) {
if (g.r == pacman.r && g.c == pacman.c) {
if (g.state == GhostState.FRIGHTENED) {
g.state = GhostState.DEAD; score += 200;
} else if (g.state != GhostState.DEAD) {
gameOver = true;
}
}
}
}
void printMap() {
for (int i=0;i<rows;i++) {
for (int j=0;j<cols;j++) {
if (pacman.r==i && pacman.c==j) { System.out.print('P'); continue; }
boolean isGhost = false;
for (Ghost g : ghosts) if (g.r==i && g.c==j) { System.out.print('G'); isGhost=true; break; }
if (isGhost) continue;
System.out.print(map[i][j]==WALL?'#':map[i][j]==DOT?'.':map[i][j]==POWER?'*':' ');
}
System.out.println();
}
}
public static void main(String[] args) {
int[][] map = {
{1,1,1,1,1,1,1,1,1},
{1,2,2,2,2,2,2,2,1},
{1,2,1,1,2,1,1,2,1},
{1,2,2,2,2,2,2,2,1},
{1,2,1,2,1,2,1,2,1},
{1,2,2,2,2,2,2,2,1},
{1,2,1,1,2,1,1,2,1},
{1,2,2,2,2,2,2,2,1},
{1,1,1,1,1,1,1,1,1}
};
new PacManGame(map).gameLoop();
}
}
复杂度分析
- A*寻路：时间复杂度为
O(b^d)，其中b为分支因子（最大4），d为解深度；空间复杂度为O(V)，V为访问节点数。在 Pac-Man 网格地图中，由于曼哈顿距离的可采纳性，A*通常仅需探索少量节点即可找到最优路径。 - 状态机切换：四种状态切换为
O(1)操作，整体游戏循环每帧时间复杂度为O(幽灵数量 × A*寻路)。
总结
本文实现了 Pac-Man 的完整核心逻辑：A*寻路保证幽灵追逐路径最优，四种差异化的追逐策略（Blinky直接追、Pinky预判、Inky反射、Clyde距离切换）让游戏AI富有层次感，有限状态机管理散射/追逐/受惊/死亡四种模式。读者可以在此基础上扩展地图编辑器、分数系统、关卡递进等完整功能。
