游戏 AI / 系统课时
追击目标时如何减少重算
追击目标时如何减少重算
追击移动目标时,如果每帧都重新执行 A*,路径会很新,但 CPU 会被大量重复搜索消耗;如果很久才重算,NPC 又会追着旧位置跑。本节把“目标移动距离、最短重算间隔和异常路径”组合成一套可执行的重算策略。
学习目标
- 识别追击场景中真正需要重新寻路的触发条件
- 用距离阈值与时间节流共同限制 A* 调用频率
- 为路径失效等异常情况保留立即重算通道
不要把目标每次移动都当成新任务
移动目标几乎每帧都会改变坐标,但这并不意味着路径拓扑每帧都发生了值得处理的变化。目标从上一帧移动几厘米时,旧路径通常仍然足够好;真正值得重算的是目标已经离开上次规划位置一段距离,或者当前路径已经无效。
判断时要比较当前目标位置与“上次成功规划时的目标位置”,而不是与上一帧目标位置比较。后者每次只看到很小的增量,目标即使累计跑出很远,也可能永远达不到重算阈值。
把距离阈值和时间节流叠加
一个稳定策略可以分成三层:第一次追击必须计算;路径失效时立即重算;正常情况下同时满足“距离变化足够大”和“距离上次规划已经过了最短间隔”才重算。

这样做的意义是把两个不同问题拆开:距离阈值控制“路径是否已经明显过时”,最短间隔控制“最多多久允许算一次”。二者缺一都会有明显副作用。
实现一个最小重算策略
下面用纯 C# 写一个可运行的策略类。示例中的 1.5 和 0.5 只是便于观察结果的演示值,实际项目应根据地图尺度、NPC 速度和寻路成本测量后确定。
using System;
using System.Numerics;
public sealed class RepathPolicy
{
private readonly float _targetMoveThreshold;
private readonly float _minInterval;
private bool _hasPath;
private float _lastRepathTime;
private Vector2 _lastPlannedTarget;
public RepathPolicy(float targetMoveThreshold, float minInterval)
{
if (targetMoveThreshold <= 0) throw new ArgumentOutOfRangeException(nameof(targetMoveThreshold));
if (minInterval < 0) throw new ArgumentOutOfRangeException(nameof(minInterval));
_targetMoveThreshold = targetMoveThreshold;
_minInterval = minInterval;
}
public bool ShouldRepath(float now, Vector2 currentTarget, bool pathInvalid)
{
if (!_hasPath) return true;
// 无效路径属于异常状态,应立即修复,不受正常节流限制。
if (pathInvalid) return true;
if (now - _lastRepathTime < _minInterval) return false;
float moved = Vector2.Distance(currentTarget, _lastPlannedTarget);
return moved >= _targetMoveThreshold;
}
public void MarkPathBuilt(float now, Vector2 plannedTarget)
{
_hasPath = true;
_lastRepathTime = now;
_lastPlannedTarget = plannedTarget;
}
}
public static class Program
{
public static void Main()
{
var policy = new RepathPolicy(
targetMoveThreshold: 1.5f,
minInterval: 0.5f);
Test(policy, 0.0f, new Vector2(0.0f, 0f), pathInvalid: false);
Test(policy, 0.2f, new Vector2(0.5f, 0f), pathInvalid: false);
Test(policy, 0.6f, new Vector2(0.8f, 0f), pathInvalid: false);
Test(policy, 0.8f, new Vector2(2.0f, 0f), pathInvalid: false);
Test(policy, 0.9f, new Vector2(2.1f, 0f), pathInvalid: true);
}
private static void Test(
RepathPolicy policy,
float now,
Vector2 target,
bool pathInvalid)
{
bool repath = policy.ShouldRepath(now, target, pathInvalid);
Console.WriteLine($"t={now:F1} => {(repath ? "REPATH" : "KEEP")}");
if (repath)
{
policy.MarkPathBuilt(now, target);
}
}
}预期输出:
t=0.0 => REPATH
t=0.2 => KEEP
t=0.6 => KEEP
t=0.8 => REPATH
t=0.9 => REPATH0.2 秒时还没到最短间隔;0.6 秒虽然允许检查,但目标累计只移动了 0.8,没有达到阈值;0.8 秒时累计位移达到 2.0,因此重算。最后一次即使刚重算过,只要路径被判定为无效,也直接走异常通道。
重算后要更新的是规划基准
一次 A* 完成后,应同时记录规划时间和本次寻路使用的目标位置。不要在每帧追踪目标时更新 _lastPlannedTarget,否则距离阈值比较的基准会不断跟着目标移动,策略失去“累计偏移”的意义。
如果寻路是异步执行的,还要区分“请求时目标位置”和“完成时目标位置”。通常应把真正送入搜索器的目标点作为规划基准;搜索完成后如果目标已经移动很远,可以立即安排下一次重算,但仍要受并发任务数量控制,避免同一个 NPC 同时挂起多次搜索。
路径质量和CPU要一起验收
重算频率没有通用固定值。地图障碍越复杂、单次 A* 越贵,就越需要放大时间间隔;目标移动越快、战斗对追击精度要求越高,就越需要缩小距离阈值。最终应同时观察两类指标:NPC 与目标的实际追踪误差,以及单位时间内的寻路调用次数和耗时。
当很多 NPC 同时追同一个目标时,还可以在这套策略外再加“错峰调度”,让不同 NPC 分散到不同更新时刻。单个 NPC 先用异常立即重算、正常路径按时间与位移双阈值重算,就已经能避免最常见的每帧 A* 浪费。