游戏 AI / 系统课时

目标移动时什么时候要重寻路

目标移动时什么时候要重寻路

追击移动目标时,最容易犯的错是每帧都重新执行 A*。这样既浪费计算,又会让路径频繁变化,NPC 看起来左右抖动。本节用“距离阈值 + 最小间隔 + 强制失效”三类条件,把重寻路变成可控事件。

学习目标

  • 判断目标移动到什么程度才值得重新寻路
  • 用最小重算间隔抑制高频抖动
  • 区分“可延迟重算”和“必须立即重算”的情况

不要把目标位置变化等同于重寻路

目标在移动,不代表当前路径已经失效。如果目标只在终点附近小范围移动,而 NPC 仍沿着一条合理路径接近它,每帧重算只会制造额外开销。

更稳妥的做法是保存上一次用于规划的目标位置 lastPlannedTarget。当当前目标位置与它的距离超过阈值时,才认为“目标已经移动得足够远”。

可以把条件写成:

d=∥ptarget−pplanned∥d = \lVert p_{target} - p_{planned} \rVert

只有当 d≥Td \ge T 时,位置变化才触发重寻路候选。这里的 TT 就是移动阈值。

阈值不能只看单位大小,还要结合地图格子尺度和 NPC 的速度。例如网格边长为 1 米时,把阈值设成 0.05 米通常过于敏感;设成 1~2 个格子往往更稳定。

再加一层时间节流

距离阈值只能过滤小位移,挡不住高速目标连续跨过阈值。为了避免一秒内重算几十次,还需要设置 minRepathInterval。

正常追击时,只有“目标移动超过阈值”和“距离上次规划已经超过最小间隔”同时成立,才执行新的 A*。但如果当前路径已经明确失效,例如下一段被动态障碍封死,就不应该等待节流时间,而应立即重算。

目标移动时的重寻路判断流程

这套顺序有一个重要好处:正常变化被节流,真正失效不被延迟。如果把时间判断放在最前面,动态障碍刚刚封路时,NPC 可能还要等几百毫秒才会重新找路。

用一个可运行的重寻路控制器

下面用纯 C# 实现判定逻辑。示例不依赖游戏引擎,重点是把触发条件拆清楚;接入 Unity、Godot 或自研引擎时,只需要把位置和路径状态换成实际对象。

csharp
using System;
using System.Numerics;

public sealed class RepathController
{
    private readonly float moveThreshold;
    private readonly float minRepathInterval;
    private Vector2 lastPlannedTarget;
    private float lastRepathTime;

    public RepathController(Vector2 initialTarget, float moveThreshold, float minRepathInterval)
    {
        this.lastPlannedTarget = initialTarget;
        this.moveThreshold = moveThreshold;
        this.minRepathInterval = minRepathInterval;
        this.lastRepathTime = 0f;
    }

    public bool ShouldRepath(Vector2 currentTarget, float now, bool pathInvalid)
    {
        // 路径已失效时不受节流限制,优先恢复可达性。
        if (pathInvalid)
        {
            CommitRepath(currentTarget, now);
            return true;
        }

        float moved = Vector2.Distance(currentTarget, lastPlannedTarget);
        bool movedEnough = moved >= moveThreshold;
        bool intervalReady = now - lastRepathTime >= minRepathInterval;

        if (movedEnough && intervalReady)
        {
            CommitRepath(currentTarget, now);
            return true;
        }

        return false;
    }

    private void CommitRepath(Vector2 target, float now)
    {
        lastPlannedTarget = target;
        lastRepathTime = now;
    }
}

public static class Program
{
    public static void Main()
    {
        var controller = new RepathController(
            initialTarget: new Vector2(0f, 0f),
            moveThreshold: 1.0f,
            minRepathInterval: 0.5f);

        Console.WriteLine(controller.ShouldRepath(new Vector2(0.4f, 0f), 0.6f, false));
        Console.WriteLine(controller.ShouldRepath(new Vector2(1.2f, 0f), 0.7f, false));
        Console.WriteLine(controller.ShouldRepath(new Vector2(2.5f, 0f), 0.9f, false));
        Console.WriteLine(controller.ShouldRepath(new Vector2(2.5f, 0f), 1.0f, true));
    }
}

预期输出:

text
False
True
False
True

第二次调用时,目标已经移动 1.2,且距离上次规划时间超过 0.5 秒,因此触发重算。第三次虽然再次移动较远,但只过去 0.2 秒,被最小间隔挡住。第四次把 pathInvalid 设为 true,所以立即重算。

阈值应该跟场景一起调

moveThreshold 越小,NPC 越贴着目标当前位置追,但 CPU 开销更高,路径也更容易抖动;越大,路径更稳定,但高速目标可能出现“追旧位置”的感觉。minRepathInterval 也存在同样的响应速度与稳定性权衡。

实际项目里可以先以“1~2 个导航格”为移动阈值、0.2~0.5 秒为最小间隔起步,再观察目标速度、地图复杂度和 NPC 数量调整。群体追击时还可以把不同 NPC 的重算时间错开,避免同一帧集中执行 A*。

真正需要立即重寻路的情况应单独处理,例如当前路径被新障碍截断、路径节点已经不可通行,或角色偏离路径到无法继续跟随的程度。目标只是小幅移动时,继续沿当前路径走通常比立刻重算更稳定。

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

目录与阅读设置

阅读设置

17

记录一个想法

目标移动时什么时候要重寻路

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

登录哪都通