引言
老鹰捉小鸡是无数人童年记忆中的经典团体游戏。一只”老鹰”试图抓住队伍末尾的”小鸡”，而”母鸡”则伸展双臂左右移动保护身后的一串小鸡。看似简单的追逐背后，蕴含着追捕-逃避博弈（Pursuit-Evasion Game）的深刻数学原理。本文将用Java实现老鹰捉小鸡游戏，并讲解如何运用Voronoi图划分控制区域，帮助老鹰制定最优追捕策略。
一、游戏规则与数学建模
1.1 基本规则
- 场地上有 $N$ 个角色：1只老鹰、1只母鸡、$K$ 只小鸡
- 小鸡排成一列，每只小鸡抓住前一只的衣角
- 母鸡左右移动保护小鸡，老鹰试图绕过母鸡抓住最后一只小鸡
- 老鹰速度略快于母鸡，但转弯灵活性较差
1.2 追捕-逃避博弈模型
追捕-逃避博弈是博弈论与微分博弈的经典问题。设老鹰位置为 $P_e(t)$，母鸡位置为 $P_m(t)$，第 $i$ 只小鸡位置为 $P_{c_i}(t)$。
老鹰的目标是最小化捕获时间：
$$
\min_{u_e} T \quad \text{s.t.} \quad |P_e(T) – P_{c_K}(T)| \leq \epsilon
$$
母鸡和小鸡的目标则是最大化捕获时间或避免被捕获。
1.3 Voronoi图与区域控制
Voronoi图将平面划分为若干区域，每个区域包含距离某个”站点”最近的所有点。在老鹰捉小鸡中：
- 以老鹰和母鸡为站点构建Voronoi图
- Voronoi边界是双方”势力范围”的分界线
- 老鹰的最优策略是沿Voronoi边界寻找突破口，或逼迫母鸡移动暴露出小鸡
二、核心算法设计
2.1 角色运动学模型
每个角色具有位置、速度和朝向。老鹰速度最快但转弯半径大，母鸡灵活性高但速度较慢。
2.2 Voronoi边界计算
对于两个站点（老鹰和母鸡），Voronoi边界是它们连线的中垂线。对于多个小鸡的情况，可以构建多站点Voronoi图。
2.3 老鹰AI决策算法
老鹰的决策采用分层策略：
- 目标选择：确定当前最容易捕获的小鸡（通常是队尾）
- 路径规划：计算绕过母鸡的最短路径
- Voronoi突破：寻找Voronoi边界上母鸡控制力最弱的点进行突破
- 追击执行：沿规划路径以最大速度追击
三、Java完整实现
import java.util.*;
/**
* 老鹰捉小鸡 — 追捕逃避博弈与Voronoi区域覆盖策略
*
* 核心设计：
* 1. 角色运动学模型（位置、速度、朝向）
* 2. Voronoi图划分势力范围
* 3. 老鹰分层AI决策（目标选择 → 路径规划 → 突破追击）
*/
public class EagleChickGame {
// 场地参数
private static final double FIELD_WIDTH = 100.0;
private static final double FIELD_HEIGHT = 60.0;
private static final double CAPTURE_RADIUS = 2.0; // 捕获半径
// 角色参数
private static final double EAGLE_SPEED = 5.0;
private static final double EAGLE_TURN_RATE = Math.PI / 6; // 最大转向角速度
private static final double HEN_SPEED = 3.5;
private static final double HEN_TURN_RATE = Math.PI / 4;
private static final double CHICK_SPEED = 3.0;
private static final double CHAIN_DISTANCE = 2.5; // 小鸡之间保持距离
// 角色类
static class Agent {
double x, y; // 位置
double vx, vy; // 速度向量
double speed; // 最大速度
double turnRate; // 最大转向率
String name;
Agent(String name, double x, double y, double speed, double turnRate) {
this.name = name;
this.x = x;
this.y = y;
this.speed = speed;
this.turnRate = turnRate;
this.vx = 0;
this.vy = 0;
}
void move() {
x += vx;
y += vy;
// 边界约束
x = Math.max(0, Math.min(FIELD_WIDTH, x));
y = Math.max(0, Math.min(FIELD_HEIGHT, y));
}
double distanceTo(Agent other) {
return Math.hypot(x - other.x, y - other.y);
}
double distanceTo(double px, double py) {
return Math.hypot(x - px, y - py);
}
}
private Agent eagle;
private Agent hen;
private List<Agent> chicks;
private Random random;
private int capturedCount;
public EagleChickGame(int chickCount) {
this.random = new Random();
this.capturedCount = 0;
// 初始化老鹰（场地右侧）
eagle = new Agent("老鹰", FIELD_WIDTH - 10, FIELD_HEIGHT / 2, EAGLE_SPEED, EAGLE_TURN_RATE);
// 初始化母鸡（场地中央偏左）
hen = new Agent("母鸡", FIELD_WIDTH / 2, FIELD_HEIGHT / 2, HEN_SPEED, HEN_TURN_RATE);
// 初始化小鸡队列（母鸡身后）
chicks = new ArrayList<>();
for (int i = 0; i < chickCount; i++) {
double cx = hen.x - (i + 1) * CHAIN_DISTANCE;
double cy = hen.y;
chicks.add(new Agent("小鸡" + (i + 1), cx, cy, CHICK_SPEED, HEN_TURN_RATE));
}
}
/**
* 计算两点间中垂线参数
* 返回直线 ax + by + c = 0 的系数
*/
static class Line {
double a, b, c;
Line(double a, double b, double c) { this.a = a; this.b = b; this.c = c; }
}
Line perpendicularBisector(double x1, double y1, double x2, double y2) {
double mx = (x1 + x2) / 2.0;
double my = (y1 + y2) / 2.0;
double dx = x2 - x1;
double dy = y2 - y1;
// 中垂线：dx*(x-mx) + dy*(y-my) = 0
// 即 dx*x + dy*y - dx*mx - dy*my = 0
return new Line(dx, dy, -dx * mx - dy * my);
}
/**
* 计算Voronoi边界上距离老鹰最近的点
*
* 对于老鹰-母鸡二元Voronoi图，边界是中垂线。
* 老鹰应寻找边界上距离自己最远的点（即母鸡控制力最弱的点）进行突破。
*/
public double[] findBreakthroughPoint() {
Line bisector = perpendicularBisector(eagle.x, eagle.y, hen.x, hen.y);
// 在场地边界上寻找Voronoi边界与边界的交点
List<double[]> candidates = new ArrayList<>();
// 与四条边界的交点
double[][] boundaries = {
{0, 0, 0, FIELD_HEIGHT}, // 左边界 x=0
{FIELD_WIDTH, 0, FIELD_WIDTH, FIELD_HEIGHT}, // 右边界
{0, 0, FIELD_WIDTH, 0}, // 下边界 y=0
{0, FIELD_HEIGHT, FIELD_WIDTH, FIELD_HEIGHT} // 上边界
};
for (double[] b : boundaries) {
double[] intersect = lineIntersection(
bisector.a, bisector.b, bisector.c,
b[1] - b[3], b[2] - b[0], b[0] * (b[3] - b[1]) + b[1] * (b[0] - b[2])
);
if (intersect != null && isInField(intersect[0], intersect[1])) {
candidates.add(intersect);
}
}
// 选择距离老鹰最远的点（母鸡难以防守）
double[] best = null;
double maxDist = -1;
for (double[] p : candidates) {
double d = Math.hypot(p[0] - eagle.x, p[1] - eagle.y);
if (d > maxDist) {
maxDist = d;
best = p;
}
}
return best;
}
/**
* 求两条直线的交点
* 直线1: a1*x + b1*y + c1 = 0
* 直线2: a2*x + b2*y + c2 = 0
*/
double[] lineIntersection(double a1, double b1, double c1, double a2, double b2, double c2) {
double det = a1 * b2 - a2 * b1;
if (Math.abs(det) < 1e-9) return null; // 平行
double x = (b1 * c2 - b2 * c1) / det;
double y = (a2 * c1 - a1 * c2) / det;
return new double[]{x, y};
}
boolean isInField(double x, double y) {
return x >= 0 && x <= FIELD_WIDTH && y >= 0 && y <= FIELD_HEIGHT;
}
/**
* 老鹰AI决策 — 分层策略
*
* 第一层：若有小鸡脱离母鸡保护范围（距离母鸡较远），直接追击
* 第二层：否则寻找Voronoi边界突破点，绕过母鸡
* 第三层：若突破点太远，则正面施压，逼迫母鸡露出破绽
*/
public void eagleDecision() {
Agent target = chicks.get(chicks.size() - 1); // 目标：最后一只小鸡
// 第一层：检查是否有容易捕获的目标
for (int i = chicks.size() - 1; i >= 0; i--) {
Agent chick = chicks.get(i);
double chickToHen = chick.distanceTo(hen);
double eagleToChick = eagle.distanceTo(chick);
// 若小鸡距离母鸡较远且老鹰较近，直接追击
if (chickToHen > 15.0 && eagleToChick < 20.0) {
moveTowards(eagle, chick.x, chick.y);
return;
}
}
// 第二层：Voronoi边界突破策略
double[] breakthrough = findBreakthroughPoint();
if (breakthrough != null) {
double distToBreak = eagle.distanceTo(breakthrough[0], breakthrough[1]);
double henToBreak = hen.distanceTo(breakthrough[0], breakthrough[1]);
// 若老鹰能先到达突破点，则执行突破
if (distToBreak < henToBreak * 0.8) {
moveTowards(eagle, breakthrough[0], breakthrough[1]);
return;
}
}
// 第三层：正面施压，逼迫母鸡移动
// 计算母鸡-目标小鸡连线的垂线方向，预判母鸡移动方向
double dx = target.x - hen.x;
double dy = target.y - hen.y;
double len = Math.hypot(dx, dy);
if (len > 0) {
dx /= len;
dy /= len;
}
// 老鹰朝目标小鸡方向移动，但保持与母鸡的安全距离
double approachX = target.x + dx * 5.0;
double approachY = target.y + dy * 5.0;
moveTowards(eagle, approachX, approachY);
}
/**
* 母鸡AI决策 — 保护小鸡
*
* 策略：始终保持在老鹰与队尾小鸡之间的连线上
*/
public void henDecision() {
if (chicks.isEmpty()) return;
Agent lastChick = chicks.get(chicks.size() - 1);
// 计算老鹰到队尾小鸡的方向
double dx = lastChick.x - eagle.x;
double dy = lastChick.y - eagle.y;
double len = Math.hypot(dx, dy);
if (len > 0) {
dx /= len;
dy /= len;
}
// 母鸡应位于老鹰与小鸡之间，距离小鸡约5个单位
double targetX = lastChick.x - dx * 5.0;
double targetY = lastChick.y - dy * 5.0;
moveTowards(hen, targetX, targetY);
}
/**
* 小鸡AI决策 — 跟随前驱
*
* 每只小鸡朝向前一只小鸡（或母鸡）移动，保持CHAIN_DISTANCE距离
*/
public void chicksDecision() {
for (int i = 0; i < chicks.size(); i++) {
Agent chick = chicks.get(i);
Agent predecessor = (i == 0) ? hen : chicks.get(i - 1);
double dx = predecessor.x - chick.x;
double dy = predecessor.y - chick.y;
double dist = Math.hypot(dx, dy);
if (dist > CHAIN_DISTANCE) {
double targetX = predecessor.x - (dx / dist) * CHAIN_DISTANCE;
double targetY = predecessor.y - (dy / dist) * CHAIN_DISTANCE;
moveTowards(chick, targetX, targetY);
} else {
// 距离合适，减速
chick.vx *= 0.5;
chick.vy *= 0.5;
}
}
}
/**
* 让角色朝目标点移动（带转向约束）
*/
void moveTowards(Agent agent, double tx, double ty) {
double dx = tx - agent.x;
double dy = ty - agent.y;
double dist = Math.hypot(dx, dy);
if (dist < 0.1) {
agent.vx = 0;
agent.vy = 0;
return;
}
// 目标方向
double targetDir = Math.atan2(dy, dx);
double currentDir = Math.atan2(agent.vy, agent.vx);
if (Math.hypot(agent.vx, agent.vy) < 0.1) {
currentDir = targetDir;
}
// 转向约束：不能超过最大转向率
double angleDiff = normalizeAngle(targetDir - currentDir);
double actualTurn = Math.max(-agent.turnRate, Math.min(agent.turnRate, angleDiff));
double newDir = currentDir + actualTurn;
agent.vx = Math.cos(newDir) * agent.speed;
agent.vy = Math.sin(newDir) * agent.speed;
}
double normalizeAngle(double angle) {
while (angle > Math.PI) angle -= 2 * Math.PI;
while (angle < -Math.PI) angle += 2 * Math.PI;
return angle;
}
/**
* 检查捕获
*/
public void checkCapture() {
Iterator<Agent> it = chicks.iterator();
while (it.hasNext()) {
Agent chick = it.next();
if (eagle.distanceTo(chick) <= CAPTURE_RADIUS) {
System.out.println("老鹰捕获了 " + chick.name + "！");
it.remove();
capturedCount++;
}
}
}
/**
* 打印当前状态
*/
public void printState() {
System.out.printf("老鹰(%.1f, %.1f) | 母鸡(%.1f, %.1f) | 剩余小鸡: %d | 已捕获: %d%n",
eagle.x, eagle.y, hen.x, hen.y, chicks.size(), capturedCount);
}
/**
* 运行单轮游戏
*/
public void runGame() {
System.out.println("=== 老鹰捉小鸡 游戏开始 ===");
printState();
int round = 0;
while (!chicks.isEmpty() && round < 200) {
// AI决策
eagleDecision();
henDecision();
chicksDecision();
// 移动
eagle.move();
hen.move();
for (Agent chick : chicks) chick.move();
// 检查捕获
checkCapture();
round++;
if (round % 20 == 0) {
printState();
}
}
System.out.println("\n=== 游戏结束 ===");
System.out.println("总回合数: " + round);
System.out.println("捕获小鸡数: " + capturedCount);
System.out.println(chicks.isEmpty() ? "老鹰胜利！全部捕获！" : "母鸡胜利！保护成功！");
}
public static void main(String[] args) {
EagleChickGame game = new EagleChickGame(5);
game.runGame();
}
}
四、算法复杂度分析
| 模块 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| Voronoi边界计算 | $O(1)$ | $O(1)$ | 二元Voronoi为直线解析解 |
| 边界交点计算 | $O(1)$ | $O(1)$ | 固定4条边界 |
| 老鹰AI决策 | $O(K)$ | $O(1)$ | $K$为小鸡数量 |
| 母鸡AI决策 | $O(1)$ | $O(1)$ | 单次向量计算 |
| 小鸡跟随 | $O(K)$ | $O(1)$ | 每只小鸡独立计算 |
| 单轮更新 | $O(K)$ | $O(K)$ | 整体复杂度 |
五、策略扩展与改进
5.1 多老鹰协同
引入多只老鹰时，可以构建多站点Voronoi图，每只老鹰负责不同的区域，协同包围小鸡队列。
5.2 小鸡分散策略
小鸡不再排成一列，而是可以分散逃跑。此时问题转化为图论中的图搜索问题，老鹰需要在图中寻找最短捕获路径。
5.3 学习型AI
使用强化学习（Q-Learning或PPO）训练老鹰和母鸡的策略网络，让AI通过自对弈发现超越人工设计的战术。
六、总结
本文将童年游戏老鹰捉小鸡抽象为追捕-逃避博弈问题，核心算法亮点包括：
- Voronoi图：划分老鹰与母鸡的势力范围，为突破策略提供数学基础
- 分层AI：目标选择 → 路径规划 → 突破追击的三层决策架构
- 运动学约束：考虑转向率限制，使运动更真实
读者可以在此基础上添加图形渲染（JavaFX）、多老鹰协同模式或在线对战功能，将算法原型扩展为完整的多人游戏。
