游戏 AI / 系统课时

搜索节点暴增怎么止损

搜索节点暴增怎么止损

A* 出现性能问题时,真正危险的往往不是某一次搜索慢,而是异常地图或大量请求让展开节点持续增长,最终形成帧耗时尖峰。本节把问题拆成可观测、可中止、可调度三层,让寻路即使遇到最坏情况也不会无限消耗计算资源。

学习目标

  • 用展开节点数、开放集峰值和搜索结果定位异常搜索
  • 为单次 A* 设置明确的计算预算,并区分超限与不可达
  • 通过请求队列和每帧限额削平多个 NPC 同时寻路造成的峰值

先确认节点到底暴增在哪里

不要只记录“寻路耗时 20 ms”。相同耗时背后的原因可能完全不同:有的请求展开了大量节点,有的开放集膨胀严重,还有的只是同一帧集中执行了太多正常请求。至少应给每次搜索记录以下数据。

指标 含义 异常时优先检查
expandedNodes 已从开放集取出并扩展的节点数 地图连通性、启发式、目标距离
openPeak 开放集历史最大元素数 重复入队、代价更新、邻居数量
result SUCCESS、NO_PATH 或预算超限 不要把超限误判成不可达
elapsedMs 单次搜索实际耗时 节点结构、堆操作、GC 与硬件差异

更有价值的是观察分布而不是平均值。例如大多数请求只展开几百个节点,但少量请求突然达到数万节点,平均值可能仍然正常,帧尖峰却已经足以造成卡顿。线上统计应重点查看最大值以及 p95、p99 这类尾部指标。

从寻路请求到预算限制和性能统计的数据流

给单次搜索设置硬上限

搜索预算的作用不是让 A* 更聪明,而是给最坏情况设置成本上界。最直接的限制是最大展开节点数,例如一次搜索最多扩展 5000 个节点;必要时还可以限制开放集大小或墙钟时间。

达到预算后应返回单独的 BUDGET_EXCEEDED,而不是 NO_PATH。前者表示“这次没有继续算完”,后者才表示“在完整搜索范围内确认不可达”。如果混成一个状态,上层 AI 可能错误地认为目标永远到不了。

下面用一个可运行的 Java 示例模拟两层保护:每帧最多处理两个请求,每个请求最多展开 150 个节点。示例中的 estimatedNodes 用于模拟搜索工作量,真实项目应替换为 A* 循环中实际累计的展开节点数。

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

public class PathfindingGuardDemo {
    record Request(int id, int estimatedNodes) {}

    static String search(Request request, int maxExpandedNodes) {
        int expanded = Math.min(request.estimatedNodes(), maxExpandedNodes);
        String result = request.estimatedNodes() > maxExpandedNodes
                ? "BUDGET_EXCEEDED"
                : "SUCCESS";
        return "request=" + request.id()
                + " result=" + result
                + " expanded=" + expanded;
    }

    public static void main(String[] args) {
        Queue<Request> pending = new ArrayDeque<>(List.of(
                new Request(1, 40),
                new Request(2, 120),
                new Request(3, 90),
                new Request(4, 300),
                new Request(5, 70)
        ));

        int maxRequestsPerFrame = 2;
        int maxExpandedNodes = 150;
        int frame = 1;

        while (!pending.isEmpty()) {
            int count = Math.min(maxRequestsPerFrame, pending.size());
            for (int i = 0; i < count; i++) {
                System.out.println("frame=" + frame + " "
                        + search(pending.remove(), maxExpandedNodes));
            }
            System.out.println("frame=" + frame + " remaining=" + pending.size());
            frame++;
        }
    }
}

预期输出:

text
frame=1 request=1 result=SUCCESS expanded=40
frame=1 request=2 result=SUCCESS expanded=120
frame=1 remaining=3
frame=2 request=3 result=SUCCESS expanded=90
frame=2 request=4 result=BUDGET_EXCEEDED expanded=150
frame=2 remaining=1
frame=3 request=5 result=SUCCESS expanded=70
frame=3 remaining=0

这个结果体现了两个不同的上限:第四个请求本身过重,所以被单次搜索预算截断;五个请求也没有在一帧全部执行,而是分三帧逐步消化。

用调度削平正常请求形成的尖峰

即使每次 A* 都只需要 0.3 ms,100 个 NPC 在同一帧重算仍可能形成明显尖峰。因此除了限制一次搜索,还要限制一帧允许启动多少次搜索。常见做法是维护请求队列,每帧从队首取固定数量,剩余请求继续等待。

调度时需要区分优先级。玩家附近、当前路径已经失效或马上要碰撞的 NPC 可以优先处理;远处且仍有可用路径的 NPC 可以延迟几帧。这样优化的是响应顺序,而不是简单地让所有角色一起变慢。

用结果状态决定下一步动作

SUCCESS 可以直接交给移动系统;NO_PATH 通常需要等待地图变化、修改目标或进入失败行为;BUDGET_EXCEEDED 则更适合进入降级路径,例如下一帧重试、降低请求优先级、改用较粗粒度搜索,或者触发后续的分层寻路策略。

真正稳定的止损方案不是把某个上限调得很小,而是让单次搜索成本有上界、同帧请求数量有上界、超限原因可以被统计。做到这三点后,即使地图中出现极端搜索,也不会再以不可控的方式吞掉整帧计算时间。

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

目录与阅读设置

阅读设置

17

记录一个想法

搜索节点暴增怎么止损

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

登录哪都通