游戏 AI / 系统课时

追击目标时如何减少重算

追击目标时如何减少重算

追击移动目标时,如果每帧都重新执行 A*,路径会很新,但 CPU 会被大量重复搜索消耗;如果很久才重算,NPC 又会追着旧位置跑。本节把“目标移动距离、最短重算间隔和异常路径”组合成一套可执行的重算策略。

学习目标

  • 识别追击场景中真正需要重新寻路的触发条件
  • 用距离阈值与时间节流共同限制 A* 调用频率
  • 为路径失效等异常情况保留立即重算通道

不要把目标每次移动都当成新任务

移动目标几乎每帧都会改变坐标,但这并不意味着路径拓扑每帧都发生了值得处理的变化。目标从上一帧移动几厘米时,旧路径通常仍然足够好;真正值得重算的是目标已经离开上次规划位置一段距离,或者当前路径已经无效。

判断时要比较当前目标位置与“上次成功规划时的目标位置”,而不是与上一帧目标位置比较。后者每次只看到很小的增量,目标即使累计跑出很远,也可能永远达不到重算阈值。

把距离阈值和时间节流叠加

一个稳定策略可以分成三层:第一次追击必须计算;路径失效时立即重算;正常情况下同时满足“距离变化足够大”和“距离上次规划已经过了最短间隔”才重算。

追击目标的路径重算判定流程

这样做的意义是把两个不同问题拆开:距离阈值控制“路径是否已经明显过时”,最短间隔控制“最多多久允许算一次”。二者缺一都会有明显副作用。

实现一个最小重算策略

下面用纯 C# 写一个可运行的策略类。示例中的 1.5 和 0.5 只是便于观察结果的演示值,实际项目应根据地图尺度、NPC 速度和寻路成本测量后确定。

csharp
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);
        }
    }
}

预期输出:

text
t=0.0 => REPATH
t=0.2 => KEEP
t=0.6 => KEEP
t=0.8 => REPATH
t=0.9 => REPATH

0.2 秒时还没到最短间隔;0.6 秒虽然允许检查,但目标累计只移动了 0.8,没有达到阈值;0.8 秒时累计位移达到 2.0,因此重算。最后一次即使刚重算过,只要路径被判定为无效,也直接走异常通道。

重算后要更新的是规划基准

一次 A* 完成后,应同时记录规划时间和本次寻路使用的目标位置。不要在每帧追踪目标时更新 _lastPlannedTarget,否则距离阈值比较的基准会不断跟着目标移动,策略失去“累计偏移”的意义。

如果寻路是异步执行的,还要区分“请求时目标位置”和“完成时目标位置”。通常应把真正送入搜索器的目标点作为规划基准;搜索完成后如果目标已经移动很远,可以立即安排下一次重算,但仍要受并发任务数量控制,避免同一个 NPC 同时挂起多次搜索。

路径质量和CPU要一起验收

重算频率没有通用固定值。地图障碍越复杂、单次 A* 越贵,就越需要放大时间间隔;目标移动越快、战斗对追击精度要求越高,就越需要缩小距离阈值。最终应同时观察两类指标:NPC 与目标的实际追踪误差,以及单位时间内的寻路调用次数和耗时。

当很多 NPC 同时追同一个目标时,还可以在这套策略外再加“错峰调度”,让不同 NPC 分散到不同更新时刻。单个 NPC 先用异常立即重算、正常路径按时间与位移双阈值重算,就已经能避免最常见的每帧 A* 浪费。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

追击目标时如何减少重算

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通