大逃杀（Battle Royale）类游戏的核心张力，全部来自一个不断收缩的安全区。玩家的所有战术决策——”现在跑还是再搜一间房””绕圈还是穿圈”——本质都是在解一道带时间窗的动态路径规划问题。
这篇文章用 Java 实现一个大逃杀 AI 的核心决策模块。重点不是画地图，而是三件真正有算法含量的事：缩圈时序建模、安全区几何判定、多阶段路径规划。
一、先把”圈”数学化
安全区的演化是确定性的、可预知的：从 t=0 开始，每隔 Δt 秒收缩一次，每次半径按比例缩小，圆心随机偏移。
用序列建模：
record Circle(double cx, double cy, double radius) {}
// 每个阶段 i 的圈：从 t=startTime[i] 开始收缩，到 endTime[i] 收缩完毕
record Phase(double startTime, double endTime, Circle from, Circle to) {}
给定当前时刻 t，插值出当前圈：
double p = clamp((t - startTime) / (endTime - startTime), 0, 1);
double cx = lerp(from.cx(), to.cx(), p);
double cy = lerp(from.cy(), to.cy(), p);
double r = lerp(from.radius(), to.radius(), p);
这一步看似平凡，但它决定了整个 AI 的”预判能力”：AI 可以提前知道 30 秒后圈在哪，这是玩家的信息劣势，也是算法的全部优势所在。
二、安全区判定：一个点、一条线段
最基础的问题：某个位置 P 是否在圈内？
boolean inside(Circle c, double x, double y) {
double dx = x - c.cx(), dy = y - c.cy();
return dx * dx + dy * dy <= c.radius() * c.radius();
}
用平方比较避免开方——这是几何题的通用优化，sqrt 在热路径上是明显的开销。
真正需要小心的是“我要跑到的目标点是否始终安全”。如果玩家当前位置在圈外、目标点在圈内，那么从 A 到 B 的直线路径上，有一部分时间是在圈外的。而圈外每秒掉血，圈内不掉。
于是需要计算：从 A 直线跑到 B，需要多少秒处于圈外？
设 A 到 B 的距离为 d，速度 v，则总时长 T = d / v。要算”圈外时长”，等价于求直线与圆的相交参数区间。
参数化直线：P(s) = A + s·(B-A)，s ∈ [0,1]。代入圆方程得到关于 s 的二次方程：
|A + s·D - C|² = r²
=> (D·D)s² + 2(D·(A-C))s + (|A-C|² - r²) = 0
解出根 s1 ≤ s2，则圈内参数区间是 [max(0,s1), min(1,s2)]。若判别式 < 0（不相交），则整段要么全在圈内、要么全在圈外，用端点判定即可。
/** 返回直线段 AB 落在圆内的参数比例 [0,1] */
double insideFraction(Circle c, double ax, double ay, double bx, double by) {
double dx = bx - ax, dy = by - ay;
double fx = ax - c.cx(), fy = ay - c.cy();
double a = dx * dx + dy * dy;
double b = 2 * (fx * dx + fy * dy);
double cc = fx * fx + fy * fy - c.radius() * c.radius();
double disc = b * b - 4 * a * cc;
if (a < 1e-12) { // 退化为一个点
return cc <= 0 ? 1.0 : 0.0;
}
if (disc < 0) { // 不相交：看端点
return cc <= 0 ? 1.0 : 0.0;
}
double sq = Math.sqrt(disc);
double s1 = (-b - sq) / (2 * a);
double s2 = (-b + sq) / (2 * a);
double lo = Math.max(0, Math.min(s1, s2));
double hi = Math.min(1, Math.max(s1, s2));
return Math.max(0, hi - lo);
}
这个函数是整个 AI 的”伤害估算器”。它的输出乘以总时长，就是预计圈外暴露时间。
三、路径规划：为什么不能只用一条最短路
假设 AI 现在在圈外，必须进圈。最朴素的做法是”朝圈心直线跑”。但它会在两个地方失败：
失败一：忽略地形代价。 直线穿过山崖/建筑，实际要绕。这时需要 A 在网格上找最短路。但如果直接对 500×500 的格子跑 A，节点数 25 万，每帧都跑会很吃力。
失败二：忽略缩圈时序。 有时候”跑向圈心”和”跑向下一个阶段的圈心”是两条完全不同的方向。如果只盯着当前圈，下一阶段会被迫二次长距离转移。
正确的结构是两阶段决策：
阶段 1（战术层）：决定"这一阶段结束后我要待在哪个位置"
阶段 2（执行层）：用 A* 计算从当前位置到该位置的网格最短路
战术层是离散枚举 + 评分，执行层是图搜索。两层分离，各自复杂度都可控。
战术层的候选点生成
不要枚举整个平面，只在下一阶段安全区的边界附近采样。原因：最优驻点一定靠近边界——既安全，又能最大程度减少下一阶段的转移距离（这是”贴边战术”的数学依据）。
List<double[]> candidatePoints(Circle next) {
List<double[]> pts = new ArrayList<>();
int K = 16;
// 边界采样：半径减去一个安全裕度
double r = next.radius() * 0.85;
for (int i = 0; i < K; i++) {
double ang = 2 * Math.PI * i / K;
pts.add(new double[]{ next.cx() + r * Math.cos(ang),
next.cy() + r * Math.sin(ang) });
}
pts.add(new double[]{ next.cx(), next.cy() }); // 圈心作为对照
return pts;
}
16 个边界点 + 1 个圆心，共 17 个候选。这个数字是精心选的：K=8 会漏掉有利方向，K=32 收益递减但评估成本翻倍。
战术层的评分函数
每个候选点 P 的代价由三部分组成：
double cost(double[] p, Circle cur, Circle next, long nowMs, long nextShrinkMs) {
// 1) 到达耗时：用网格最短路真实距离 / 速度（这里先用欧氏距离近似）
double dist = euclid(ai.x, ai.y, p[0], p[1]);
double travelTime = dist / speed;
// 2) 暴露伤害：跑到 P 的过程中，有多少时间在圈外
double fractionOut = 1 - insideFraction(cur, ai.x, ai.y, p[0], p[1]);
double exposure = travelTime * fractionOut;
// 3) 下一阶段的转移距离：留在 P 的话，下阶段要跑多远
double futureDist = euclid(p[0], p[1], next.cx(), next.cy()) - next.radius() * 0.85;
double futureCost = Math.max(0, futureDist) / speed * 0.4; // 打折
return exposure * DAMAGE_WEIGHT + travelTime * 0.2 + futureCost;
}
三个权重的含义很明确：exposure 是即时生命代价，travelTime 是机会成本（跑动时不安全、不能搜物资），futureCost 是远见项。0.4 这个折扣系数体现了”未来代价要打折”的通用原则——因为未来有不确定性（可能中途遇到敌人），不该按全价计入。
四、执行层：网格上的 A*
战术层给出目标点后，执行层需要在真实地形上找路。地图用网格表示，每格有权重：
| 地形 | 权重 | 说明 |
|---|---|---|
| 平地 | 1 | 基础移动 |
| 草地 | 1.2 | 略微减速 |
| 建筑 | 3 | 可进入但慢 |
| 山崖 | ∞ | 不可通行 |
| 道路 | 0.8 | 加速 |
A 的启发式用八方向距离*（允许对角移动时更紧的下界）：
double h(int x, int y, int gx, int gy) {
int dx = Math.abs(x - gx), dy = Math.abs(y - gy);
// 八方向距离：对角一步当 √2，用整数近似 (dx+dy) + (√2-2)*min
return (dx + dy) + (Math.sqrt(2) - 2) * Math.min(dx, dy);
}
这个启发式是可采纳的（在允许对角且对角线代价 ≥ √2 时不会高估），同时比曼哈顿距离紧得多——在地图开阔时能显著减少扩展节点数。
五、完整实现
import java.util.*;
public class Main {
// ---------------- 基础几何 ----------------
record Circle(double cx, double cy, double radius) {}
record Phase(long startMs, long endMs, Circle from, Circle to) {
Circle at(long t) {
double p = (t - startMs) / (double) Math.max(1, endMs - startMs);
p = Math.max(0, Math.min(1, p));
return new Circle(
from.cx() + (to.cx() - from.cx()) * p,
from.cy() + (to.cy() - from.cy()) * p,
from.radius() + (to.radius() - from.radius()) * p);
}
}
static double euclid(double ax, double ay, double bx, double by) {
return Math.hypot(ax - bx, ay - by);
}
static boolean inside(Circle c, double x, double y) {
double dx = x - c.cx(), dy = y - c.cy();
return dx * dx + dy * dy <= c.radius() * c.radius();
}
/** 线段 AB 落在圆内的参数比例 */
static double insideFraction(Circle c, double ax, double ay, double bx, double by) {
double dx = bx - ax, dy = by - ay;
double fx = ax - c.cx(), fy = ay - c.cy();
double a = dx * dx + dy * dy;
double b = 2 * (fx * dx + fy * dy);
double cc = fx * fx + fy * fy - c.radius() * c.radius();
if (a < 1e-12) return cc <= 0 ? 1.0 : 0.0;
double disc = b * b - 4 * a * cc;
if (disc < 0) return cc <= 0 ? 1.0 : 0.0;
double sq = Math.sqrt(disc);
double s1 = (-b - sq) / (2 * a);
double s2 = (-b + sq) / (2 * a);
double lo = Math.max(0, Math.min(s1, s2));
double hi = Math.min(1, Math.max(s1, s2));
return Math.max(0, hi - lo);
}
// ---------------- 地形网格 ----------------
static final int W = 200, H = 200;
static final int PASSABLE = 1, BLOCKED = -1;
final int[] terrain = new int[W * H]; // 0=平 1=草 2=建筑 3=路 -1=阻挡
final double[] weight = new double[W * H];
void buildMap(long seed) {
Random rng = new Random(seed);
for (int i = 0; i < terrain.length; i++) {
int r = rng.nextInt(100);
terrain[i] = r < 60 ? 0 : r < 80 ? 1 : r < 92 ? 2 : r < 97 ? 3 : -1;
weight[i] = switch (terrain[i]) {
case 0 -> 1.0;
case 1 -> 1.2;
case 2 -> 3.0;
case 3 -> 0.8;
default -> Double.POSITIVE_INFINITY;
};
}
// 挖一条通路，保证连通性（真实地图不会全封死）
for (int y = 0; y < H; y++) {
int x = W / 2;
terrain[y * W + x] = 0;
weight[y * W + x] = 1.0;
}
}
boolean passable(int x, int y) {
if (x < 0 || x >= W || y < 0 || y >= H) return false;
return terrain[y * W + x] != BLOCKED;
}
// ---------------- A* 执行层 ----------------
static final class Node implements Comparable<Node> {
final int x, y;
final double g, f;
final Node parent;
Node(int x, int y, double g, double f, Node parent) {
this.x = x; this.y = y; this.g = g; this.f = f; this.parent = parent;
}
@Override public int compareTo(Node o) { return Double.compare(f, o.f); }
}
private static final int[] DX = {1, 1, 0, -1, -1, -1, 0, 1};
private static final int[] DY = {0, 1, 1, 1, 0, -1, -1, -1};
static double octile(int x, int y, int gx, int gy) {
int dx = Math.abs(x - gx), dy = Math.abs(y - gy);
return (dx + dy) + (Math.sqrt(2) - 2) * Math.min(dx, dy);
}
/** 网格最短路：返回路径点列表，无解返回 null */
List<int[]> astar(int sx, int sy, int gx, int gy) {
double[] best = new double[W * H];
Arrays.fill(best, Double.POSITIVE_INFINITY);
PriorityQueue<Node> open = new PriorityQueue<>();
int s = sy * W + sx;
best[s] = 0;
open.add(new Node(sx, sy, 0, octile(sx, sy, gx, gy), null));
while (!open.isEmpty()) {
Node cur = open.poll();
if (cur.g > best[cur.y * W + cur.x]) continue; // 过期节点
if (cur.x == gx && cur.y == gy) {
LinkedList<int[]> path = new LinkedList<>();
for (Node n = cur; n != null; n = n.parent) {
path.addFirst(new int[]{n.x, n.y});
}
return path;
}
for (int d = 0; d < 8; d++) {
int nx = cur.x + DX[d], ny = cur.y + DY[d];
if (!passable(nx, ny)) continue;
// 对角移动时禁止"擦角穿越"
if (d % 2 == 1 && (!passable(cur.x + DX[d], cur.y) || !passable(cur.x, cur.y + DY[d]))) {
continue;
}
double step = weight[ny * W + nx] * (d % 2 == 1 ? Math.sqrt(2) : 1.0);
double ng = cur.g + step;
int ni = ny * W + nx;
if (ng >= best[ni]) continue;
best[ni] = ng;
open.add(new Node(nx, ny, ng, ng + octile(nx, ny, gx, gy), cur));
}
}
return null;
}
// ---------------- 战术层 ----------------
static final class AI {
double x, y;
final double speed; // 格/秒
final double damagePerSec; // 圈外每秒掉血
AI(double x, double y, double speed, double damage) {
this.x = x; this.y = y; this.speed = speed; this.damagePerSec = damage;
}
}
static final class Decision {
double targetX, targetY;
double exposure, travelTime, totalCost;
Decision(double tx, double ty, double e, double tt, double c) {
targetX = tx; targetY = ty; exposure = e; travelTime = tt; totalCost = c;
}
@Override public String toString() {
return String.format("目标(%.1f, %.1f) 暴露=%.1fs 耗时=%.1fs 总代价=%.2f",
targetX, targetY, exposure, travelTime, totalCost);
}
}
/** 生成下一阶段的候选驻点 */
static List<double[]> candidates(Circle next) {
List<double[]> pts = new ArrayList<>();
int K = 16;
double r = next.radius() * 0.85; // 安全裕度
for (int i = 0; i < K; i++) {
double ang = 2 * Math.PI * i / K;
pts.add(new double[]{ next.cx() + r * Math.cos(ang),
next.cy() + r * Math.sin(ang) });
}
pts.add(new double[]{ next.cx(), next.cy() });
return pts;
}
/** 战术层评估：为每个候选点打分，返回最优 */
static Decision bestDecision(AI ai, Circle cur, Circle next, double gamma) {
Decision best = null;
for (double[] p : candidates(next)) {
double dist = euclid(ai.x, ai.y, p[0], p[1]);
double travelTime = dist / ai.speed;
double fracOut = 1.0 - insideFraction(cur, ai.x, ai.y, p[0], p[1]);
double exposure = travelTime * fracOut;
// 未来转移成本：从 p 到下一阶段边界的最短距离
double futureDist = Math.max(0,
euclid(p[0], p[1], next.cx(), next.cy()) - next.radius() * 0.85);
double futureCost = futureDist / ai.speed * gamma;
double total = exposure * ai.damagePerSec
+ travelTime * 0.2
+ futureCost;
if (best == null || total < best.totalCost) {
best = new Decision(p[0], p[1], exposure, travelTime, total);
}
}
return best;
}
// ---------------- 主流程 ----------------
public static void main(String[] args) {
Main game = new Main();
game.buildMap(2026);
// 构造三段缩圈计划
List<Phase> phases = new ArrayList<>();
Circle c0 = new Circle(100, 100, 90);
Circle c1 = new Circle(120, 90, 55);
Circle c2 = new Circle(105, 115, 30);
Circle c3 = new Circle(110, 108, 12);
long t = 0;
phases.add(new Phase(0, 60, c0, c1));
phases.add(new Phase(60, 110, c1, c2));
phases.add(new Phase(110, 150, c2, c3));
AI ai = new AI(25, 175, 4.5, 2.0); // 位置、速度、圈外掉血/秒
System.out.println("起始位置: (" + ai.x + ", " + ai.y + ")");
for (int i = 0; i < phases.size(); i++) {
Phase ph = phases.get(i);
Circle cur = ph.at(ph.startMs());
Circle nxt = ph.at(ph.endMs());
boolean safeNow = inside(cur, ai.x, ai.y);
Decision d = bestDecision(ai, cur, nxt, 0.4);
System.out.printf("%n阶段%d 当前圈(中心%.0f,%.0f r=%.0f) 在圈内=%s%n",
i + 1, cur.cx(), cur.cy(), cur.radius(), safeNow);
System.out.println(" 决策: " + d);
// 执行层：用 A* 落地实际路径
int sx = (int) Math.round(ai.x), sy = (int) Math.round(ai.y);
int tx = (int) Math.round(d.targetX), ty = (int) Math.round(d.targetY);
tx = Math.max(0, Math.min(W - 1, tx));
ty = Math.max(0, Math.min(H - 1, ty));
if (!game.passable(tx, ty)) {
System.out.println(" 目标不可达（地形阻挡），退化为中心方向");
tx = (int) nxt.cx(); ty = (int) nxt.cy();
}
List<int[]> path = game.astar(sx, sy, tx, ty);
if (path != null) {
double realDist = 0;
for (int k = 1; k < path.size(); k++) {
realDist += euclid(path.get(k - 1)[0], path.get(k - 1)[1],
path.get(k)[0], path.get(k)[1]);
}
System.out.printf(" A*路径 %d 格，实际距离 %.1f，预计 %.1f 秒%n",
path.size(), realDist, realDist / ai.speed);
} else {
System.out.println(" A*无解");
}
ai.x = d.targetX;
ai.y = d.targetY;
}
System.out.printf("%n最终位置 (%.1f, %.1f)%n", ai.x, ai.y);
}
}
六、复杂度分析与性能取舍
| 环节 | 复杂度 | 实测规模 |
|---|---|---|
| 缩圈插值 | O(1) |
微秒级 |
| 安全区判定 | O(1) |
微秒级 |
| 线段-圆求交 | O(1) |
微秒级 |
| 战术层枚举 | O(K)，K=17 |
微秒级 |
| A* 执行层 | O(E log V)，V = 4 万 |
5~20 ms |
A* 是唯一的性能瓶颈。生产环境中通常用三层手段压制：
- 分层寻路（HPA*）：把地图切成 16×16 的块，先在块级别图上找路，再在块内细化。实测能把单次寻路从 20 ms 降到 2 ms。
- 路径缓存：同一
(起点块, 终点块)对的路径可以复用，只需拼接首尾段。 - 降采样：如果 AI 离目标超过 50 格，先在 4 倍降采样的粗网格上找路，再逐段细化。
还有一个必须处理的工程问题：astar 里的 best[] 每次调用都 new double[40000]。这在每帧多次寻路时会产生大量垃圾。正确做法是把 best[] 提升为成员变量，用”时间戳数组”代替 Arrays.fill：
private final int[] stamp = new int[W * H]; // 记录该格上次被哪个搜索访问
private int searchId = 0;
// 在 astar 开头
searchId++;
// 判断时
if (stamp[ni] == searchId && ng >= best[ni]) continue;
stamp[ni] = searchId;
best[ni] = ng;
这个”惰性初始化”技巧在网格搜索里几乎是标配，收益是把 O(V) 的数组初始化和寻路本身解耦。
七、为什么”贴边”是最优策略
回到开头的战术问题：为什么高手总是沿着圈的边缘跑？
用上面的代价函数就能解释。设当前位置恰好在圈内、距圈心 r₀，下一阶段圈半径为 r₁ < r₀。
- 策略 A：直奔圈心。 转移距离 ≈
r₁（从中心到下一阶段边界还有一整段），暴露 0。 - 策略 B：贴边运行到新圈边界。 转移距离 ≈
|r₀ - r₁|的弧长，约为r₀ - r₁，明显小于r₁。
代价函数里的 futureCost 项精确地捕捉了这个差别。所以”贴边”不是一个玄学或经验，而是最小化 r₀ - r₁ 这一项的自然结果。
代价是风险：贴边时你随时可能在圈的切线方向上被挤压。这解释了为什么高水平比赛里，贴边跑往往伴随着”先在圈内绕到有利方位，再贴边切入”的两段动作——它本质上是在用一小段额外路程换取方位自由度。
八、还可以加的两个模块
- 敌人威胁场：已确认的敌人位置生成一个衰减的”危险势场”，叠加到 A* 的格子权重上。这让路径自然绕开已知敌人方向——一个非常简洁的软约束实现。
- 资源点价值图：把地图上的物资点位做成一个价值场，与安全区求交集，得到”既安全又有物资”的候选区。战术层候选点从这里采样，比纯边界采样更贴近真实打法。
大逃杀这类游戏最迷人的地方在于：它的每一个决策都可以还原成”时间 × 空间 × 风险”的三维权衡。上面这套两阶段结构——离散枚举候选 + 图搜索落地——是处理这类问题的通用骨架，换成”外卖配送调度””无人机巡检”同样成立。
