老鹰捉小鸡是经典的儿童追逐游戏，老鹰需要绕过母鸡的拦截去抓捕小鸡。本文用Java实现这一游戏的AI决策系统，重点讲解追逐算法中的视线追逐、最短拦截路径计算，以及基于A*搜索和BFS的路径规划策略。
问题建模
将游戏场地抽象为二维网格地图：
– 老鹰（Eagle）：追逐者，每回合可移动1格，目标是抓捕到小鸡
– 母鸡（Hen）：拦截者，每回合可移动1格，阻挡老鹰与小鸡之间的路径
– 小鸡（Chicks）：被追逐者，每回合可移动1格，逃离老鹰
核心问题是：在动态环境中，老鹰如何计算最优追逐路径，同时避开母鸡的拦截？
核心算法
1. A*寻路 + 动态障碍物
A*算法用于计算从老鹰当前位置到目标小鸡的最短路径，同时将母鸡及其影响范围视为动态障碍物。
2. 拦截点预测
预判母鸡的移动意图，计算老鹰是否能在母鸡到达拦截位置之前完成抓捕。
3. 多目标决策
当存在多只小鸡时，老鹰需要选择最优目标——综合考虑距离、母鸡拦截难度和逃生方向。
完整Java实现
import java.util.*;
/**
* 老鹰捉小鸡 — 追逐算法与最短拦截路径规划
* 基于A*搜索的动态路径规划与多目标决策系统
*/
public class EagleChaseGame {
// 地图尺寸
private final int width;
private final int height;
// 四方向移动
private static final int[][] DIRS = {{-1,0}, {1,0}, {0,-1}, {0,1}};
public EagleChaseGame(int width, int height) {
this.width = width;
this.height = height;
}
/**
* A*寻路算法：计算从start到goal的最短路径
* 将母鸡位置及其邻接格视为高代价区域（而非完全阻塞）
*/
public List<int[]> astarSearch(int[] start, int[] goal,
List<int[]> henPositions,
Set<String> obstacles) {
PriorityQueue<Node> open = new PriorityQueue<>(Comparator.comparingInt(n -> n.f));
Map<String, Node> allNodes = new HashMap<>();
Node startNode = new Node(start[0], start[1], 0, heuristic(start, goal), null);
open.add(startNode);
allNodes.put(key(start), startNode);
Set<String> closed = new HashSet<>();
while (!open.isEmpty()) {
Node current = open.poll();
String curKey = key(current.x, current.y);
if (closed.contains(curKey)) continue;
closed.add(curKey);
// 到达目标
if (current.x == goal[0] && current.y == goal[1]) {
return reconstructPath(current);
}
// 扩展邻居
for (int[] d : DIRS) {
int nx = current.x + d[0];
int ny = current.y + d[1];
String nKey = key(nx, ny);
if (!inBounds(nx, ny)) continue;
if (obstacles.contains(nKey)) continue;
if (closed.contains(nKey)) continue;
// 代价计算：基础代价 + 母鸡拦截惩罚
int moveCost = 1;
for (int[] hen : henPositions) {
int distToHen = Math.abs(nx - hen[0]) + Math.abs(ny - hen[1]);
if (distToHen <= 1) {
moveCost += 5; // 紧邻母鸡代价极高
} else if (distToHen <= 2) {
moveCost += 2; // 附近母鸡有额外代价
}
}
int newG = current.g + moveCost;
Node neighbor = allNodes.get(nKey);
if (neighbor == null || newG < neighbor.g) {
neighbor = new Node(nx, ny, newG,
newG + heuristic(new int[]{nx, ny}, goal), current);
allNodes.put(nKey, neighbor);
open.add(neighbor);
}
}
}
return Collections.emptyList(); // 无路径
}
/**
* 计算拦截点：母鸡应该在哪些位置设置拦截
* 基于"老鹰到小鸡的最短路径"计算拦截效率最高的点
*/
public List<int[]> computeInterceptionPoints(int[] eagle, int[] chick,
List<int[]> hens,
Set<String> obstacles) {
// 先计算老鹰到小鸡的最短路径（忽略母鸡）
List<int[]> directPath = astarSearch(eagle, chick, Collections.emptyList(), obstacles);
if (directPath.isEmpty()) return Collections.emptyList();
List<int[]> interceptionPoints = new ArrayList<>();
// 对路径上的每个点，评估母鸡能否及时到达
for (int i = 0; i < directPath.size(); i++) {
int[] pathPoint = directPath.get(i);
for (int[] hen : hens) {
// 母鸡到该拦截点的距离
int henDist = Math.abs(hen[0] - pathPoint[0]) + Math.abs(hen[1] - pathPoint[1]);
// 老鹰到该点的步数
int eagleSteps = i;
// 如果母鸡能在老鹰之前或同时到达，则该点是有效拦截点
if (henDist <= eagleSteps) {
interceptionPoints.add(new int[]{pathPoint[0], pathPoint[1], henDist, eagleSteps});
}
}
}
// 按拦截效率排序（母鸡越早到达越好）
interceptionPoints.sort((a, b) -> {
double effA = (double) a[3] / (a[2] + 1);
double effB = (double) b[3] / (b[2] + 1);
return Double.compare(effB, effA);
});
return interceptionPoints;
}
/**
* 老鹰目标选择：评估每只小鸡的"抓捕价值"
* 综合考虑距离、母鸡密度、逃跑方向
*/
public int[] selectBestTarget(int[] eagle,
List<int[]> chicks,
List<int[]> hens,
Set<String> obstacles) {
double bestScore = Double.NEGATIVE_INFINITY;
int[] bestTarget = null;
for (int[] chick : chicks) {
// 路径长度（距离）
List<int[]> path = astarSearch(eagle, chick, hens, obstacles);
if (path.isEmpty()) continue;
int distance = path.size();
// 母鸡拦截密度：路径上母鸡影响范围
int henDensity = 0;
for (int[] point : path) {
for (int[] hen : hens) {
if (Math.abs(point[0] - hen[0]) + Math.abs(point[1] - hen[1]) <= 2) {
henDensity++;
}
}
}
// 逃跑空间评估：小鸡周围的空旷区域
int escapeSpace = countEscapeSpace(chick, hens, obstacles);
// 综合评分：距离近 + 拦截少 + 逃跑空间小 = 高价值
double score = -distance * 3.0 - henDensity * 2.0 - escapeSpace * 0.5;
if (score > bestScore) {
bestScore = score;
bestTarget = chick;
}
}
return bestTarget;
}
/**
* 小鸡逃生策略：选择使得到老鹰距离最大化，同时靠近母鸡的方向
*/
public int[] chickEscapeMove(int[] chick, int[] eagle,
List<int[]> hens, Set<String> obstacles) {
int[] bestMove = null;
double bestScore = Double.NEGATIVE_INFINITY;
for (int[] d : DIRS) {
int nx = chick[0] + d[0];
int ny = chick[1] + d[1];
if (!inBounds(nx, ny) || obstacles.contains(key(nx, ny))) continue;
// 到新位置后与老鹰的距离
int distToEagle = Math.abs(nx - eagle[0]) + Math.abs(ny - eagle[1]);
// 到最近母鸡的距离（越近越安全）
int minDistToHen = Integer.MAX_VALUE;
for (int[] hen : hens) {
int dth = Math.abs(nx - hen[0]) + Math.abs(ny - hen[1]);
minDistToHen = Math.min(minDistToHen, dth);
}
// 评分：远离老鹰 + 靠近母鸡
double score = distToEagle * 2.0 - minDistToHen * 1.5;
if (score > bestScore) {
bestScore = score;
bestMove = new int[]{nx, ny};
}
}
return bestMove != null ? bestMove : chick;
}
/**
* 母鸡拦截策略：移动到最佳拦截位置
*/
public int[] henInterceptMove(int[] hen, int[] eagle, int[] targetChick,
Set<String> obstacles) {
// 计算老鹰到小鸡的最短路径
List<int[]> eaglePath = astarSearch(eagle, targetChick,
Collections.emptyList(), obstacles);
if (eaglePath.isEmpty()) return hen;
// 寻找路径上母鸡能最先到达的拦截点
int[] bestIntercept = null;
int bestPriority = Integer.MAX_VALUE;
for (int i = 1; i < eaglePath.size(); i++) {
int[] point = eaglePath.get(i);
int dist = Math.abs(hen[0] - point[0]) + Math.abs(hen[1] - point[1]);
// 优先级：能拦截且越早越好
if (dist <= i && dist < bestPriority) {
bestPriority = dist;
bestIntercept = point;
}
}
if (bestIntercept == null) {
// 无法拦截，尝试靠近小鸡
bestIntercept = targetChick;
}
// 向拦截点移动一步（A*一步）
List<int[]> movePath = astarSearch(hen, bestIntercept,
Collections.emptyList(), obstacles);
return movePath.size() > 1 ? movePath.get(1) : hen;
}
/**
* 游戏主循环：模拟一回合
*/
public GameState simulateTurn(GameState state) {
// 老鹰选择目标
int[] target = selectBestTarget(state.eagle, state.chicks, state.hens, state.obstacles);
if (target == null) return state; // 无目标
// 母鸡移动（拦截）
List<int[]> newHens = new ArrayList<>();
for (int[] hen : state.hens) {
int[] move = henInterceptMove(hen, state.eagle, target, state.obstacles);
newHens.add(move);
}
// 小鸡移动（逃跑）
List<int[]> newChicks = new ArrayList<>();
for (int[] chick : state.chicks) {
// 检查是否已被抓捕
if (chick[0] == state.eagle[0] && chick[1] == state.eagle[1]) {
continue; // 已被抓捕，移除
}
int[] move = chickEscapeMove(chick, state.eagle, newHens, state.obstacles);
newChicks.add(move);
}
// 老鹰移动（追逐）
List<int[]> eaglePath = astarSearch(state.eagle, target, newHens, state.obstacles);
int[] newEagle = eaglePath.size() > 1 ? eaglePath.get(1) : state.eagle;
return new GameState(newEagle, newHens, newChicks, state.obstacles);
}
// 辅助：计算逃跑空间
private int countEscapeSpace(int[] pos, List<int[]> hens, Set<String> obstacles) {
int count = 0;
for (int[] d : DIRS) {
int nx = pos[0] + d[0];
int ny = pos[1] + d[1];
if (inBounds(nx, ny) && !obstacles.contains(key(nx, ny))) {
count++;
}
}
return count;
}
private int heuristic(int[] a, int[] b) {
return Math.abs(a[0] - b[0]) + Math.abs(a[1] - b[1]); // 曼哈顿距离
}
private boolean inBounds(int x, int y) {
return x >= 0 && x < width && y >= 0 && y < height;
}
private String key(int[] pos) {
return pos[0] + "," + pos[1];
}
private String key(int x, int y) {
return x + "," + y;
}
private List<int[]> reconstructPath(Node node) {
LinkedList<int[]> path = new LinkedList<>();
while (node != null) {
path.addFirst(new int[]{node.x, node.y});
node = node.parent;
}
return path;
}
// A*节点
private static class Node {
int x, y, g, f;
Node parent;
Node(int x, int y, int g, int f, Node parent) {
this.x = x; this.y = y; this.g = g; this.f = f; this.parent = parent;
}
}
// 游戏状态
public static class GameState {
public final int[] eagle;
public final List<int[]> hens;
public final List<int[]> chicks;
public final Set<String> obstacles;
public GameState(int[] eagle, List<int[]> hens,
List<int[]> chicks, Set<String> obstacles) {
this.eagle = eagle;
this.hens = hens;
this.chicks = chicks;
this.obstacles = obstacles;
}
public void print() {
char[][] grid = new char[10][10];
for (char[] row : grid) Arrays.fill(row, '.');
for (String obs : obstacles) {
String[] p = obs.split(",");
grid[Integer.parseInt(p[1])][Integer.parseInt(p[0])] = '#';
}
for (int[] h : hens) grid[h[1]][h[0]] = 'H';
for (int[] c : chicks) grid[c[1]][c[0]] = 'C';
grid[eagle[1]][eagle[0]] = 'E';
System.out.println(" 0123456789");
for (int y = 0; y < 10; y++) {
System.out.print(y + " ");
for (int x = 0; x < 10; x++) {
System.out.print(grid[y][x]);
}
System.out.println();
}
}
}
public static void main(String[] args) {
EagleChaseGame game = new EagleChaseGame(10, 10);
// 初始状态
int[] eagle = {0, 0};
List<int[]> hens = Arrays.asList(new int[]{3, 3}, new int[]{6, 4});
List<int[]> chicks = Arrays.asList(new int[]{8, 8}, new int[]{9, 2}, new int[]{7, 9});
Set<String> obstacles = new HashSet<>(Arrays.asList("4,4", "4,5", "5,4", "5,5"));
GameState state = new GameState(eagle, hens, chicks, obstacles);
System.out.println("===== 老鹰捉小鸡模拟 =====");
System.out.println("E=老鹰 H=母鸡 C=小鸡 #=障碍物");
System.out.println("\n初始状态:");
state.print();
// 老鹰选择目标
int[] target = game.selectBestTarget(state.eagle, state.chicks, state.hens, state.obstacles);
System.out.println("\n老鹰选定目标: (" + target[0] + "," + target[1] + ")");
// 计算拦截点
List<int[]> intercepts = game.computeInterceptionPoints(
state.eagle, target, state.hens, state.obstacles);
System.out.println("有效拦截点数量: " + intercepts.size());
// 模拟10回合
for (int turn = 1; turn <= 10 && !state.chicks.isEmpty(); turn++) {
state = game.simulateTurn(state);
System.out.println("\n第" + turn + "回合:");
state.print();
System.out.println("剩余小鸡: " + state.chicks.size());
}
}
}
算法核心要点
动态代价A*搜索
传统A*使用固定地图，而本实现将母鸡位置转化为动态代价函数：
– 紧邻母鸡：代价+5
– 附近母鸡：代价+2
– 空旷区域：代价+1
这保证了老鹰会主动绕开母鸡的防守区域，同时不会在完全无路可走时陷入死锁。
多智能体协同
三方角色各有策略：
– 老鹰：最大化抓捕效率，动态重选目标
– 母鸡：预判老鹰路径，抢占拦截点
– 小鸡：逃离老鹰同时靠近母鸡寻求庇护
复杂度分析
| 模块 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| A*寻路 | O(b^d)，b为分支因子，d为解深度 | O(V) |
| 目标选择 | O(c × (A*代价))，c为小鸡数量 | O(V) |
| 拦截点计算 | O(path × h)，h为母鸡数量 | O(path × h) |
| 单回合模拟 | O(c + h)次A*搜索 | O(V) |
总结
老鹰捉小鸡将多智能体路径规划问题具象化为熟悉的游戏场景。通过A*搜索的动态代价扩展、多目标评分函数和拦截点预判，我们构建了一个能自主决策的三方博弈系统。这种”追逐-拦截-逃逸”的框架广泛适用于机器人足球、军事仿真和无人机编队等实际场景。
