游戏 AI / 系统课时

多个NPC一起寻路会发生什么

多个NPC一起寻路会发生什么

单个 NPC 的 A* 搜索很快,不代表几十个角色同时请求路径也安全。本课把问题拆成“计算峰值从哪里来、怎样把请求摊到多帧、每帧该处理多少”,最终得到一个可直接接入游戏循环的限额调度器。

学习目标

  • 识别多 NPC 同帧寻路造成卡顿的原因
  • 用队列和每帧预算把寻路请求分散执行
  • 根据等待时间和帧预算调整调度策略

为什么同帧搜索会形成尖峰

A* 的主要成本来自开放集合维护、邻居扩展和代价比较。一个 NPC 的搜索节点数可能只有几百,但如果 50 个 NPC 在同一帧因为“发现玩家”同时调用寻路,CPU 工作量会直接叠加。

真正需要控制的不是“NPC 总数”,而是同一帧启动了多少次搜索,以及每次搜索扩展了多少节点。因此常见策略不是禁止多个 NPC 寻路,而是给寻路系统建立统一入口,由调度器决定何时执行。

多NPC寻路从同帧尖峰改为分帧限额调度

用每帧限额控制请求量

下面的 Java 示例不实现 A* 本体,而是实现 A* 外层的请求调度。真实项目中,把 Runnable 替换为“执行一次路径搜索并回调结果”的任务即可。

java
import java.util.ArrayDeque;
import java.util.Queue;

public class PathRequestSchedulerDemo {
    static class PathRequestScheduler {
        private final Queue<Runnable> queue = new ArrayDeque<>();
        private final int maxRequestsPerFrame;

        PathRequestScheduler(int maxRequestsPerFrame) {
            if (maxRequestsPerFrame <= 0) {
                throw new IllegalArgumentException("maxRequestsPerFrame must be > 0");
            }
            this.maxRequestsPerFrame = maxRequestsPerFrame;
        }

        void submit(Runnable request) {
            queue.add(request);
        }

        void update() {
            // 每帧只消费固定数量的请求,避免搜索集中在同一帧。
            int budget = maxRequestsPerFrame;
            while (budget > 0 && !queue.isEmpty()) {
                queue.remove().run();
                budget--;
            }
        }

        int pendingCount() {
            return queue.size();
        }
    }

    public static void main(String[] args) {
        PathRequestScheduler scheduler = new PathRequestScheduler(2);

        for (int npcId = 1; npcId <= 6; npcId++) {
            int id = npcId;
            scheduler.submit(() -> System.out.println("search npc-" + id));
        }

        int frame = 1;
        while (scheduler.pendingCount() > 0) {
            System.out.println("frame " + frame);
            scheduler.update();
            System.out.println("pending=" + scheduler.pendingCount());
            frame++;
        }
    }
}

预期输出

text
frame 1
search npc-1
search npc-2
pending=4
frame 2
search npc-3
search npc-4
pending=2
frame 3
search npc-5
search npc-6
pending=0

这个实现把 6 次搜索从一帧拆成 3 帧。它没有减少总计算量,但降低了单帧峰值,这通常比“所有 NPC 立即获得新路径”更符合实时游戏的帧预算目标。

限额之外还要处理重复请求

只做 FIFO 队列还不够。追逐移动目标时,同一个 NPC 可能在旧请求尚未执行前再次提交新目标,最终队列里堆满已经过时的请求。

工程上通常再加三条规则:同一 NPC 只保留最新请求;目标位移未超过阈值时不重算;高优先级 NPC 可以进入更高优先级队列。这样控制的是有效搜索次数,而不只是把无效工作延后执行。

怎么确定每帧预算

先测单次搜索的典型耗时,再给寻路系统分配一小段稳定预算。例如单次搜索约 0.2 ms,希望寻路每帧控制在 1 ms 左右,那么初始限额可以从 4~5 次尝试,而不是凭 NPC 数量猜测。

如果单次搜索耗时波动很大,仅按“请求个数”限额仍可能产生尖峰,此时应进一步限制“本帧最多扩展多少节点”,把一次大搜索也切成可暂停、可继续的增量任务。无论采用哪种方式,上层 NPC 都应允许短暂等待,并继续沿旧路径移动或保持原地,而不是因为新路径尚未完成就进入异常状态。

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

目录与阅读设置

阅读设置

17

记录一个想法

多个NPC一起寻路会发生什么

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

登录哪都通