游戏 AI / 系统课时

搜索空间变大怎么定位

搜索空间变大怎么定位

当 GOAP 规划开始变慢时,不要先猜某个动作“太复杂”。应先测出节点扩展量、重复状态数量和单次规划耗时,再把时间消耗定位到搜索规模、去重效率或具体动作分支。

学习目标

  • 能记录每次规划的节点扩展、重复状态与耗时,并区分搜索规模问题和单节点处理问题。
  • 能通过指标判断瓶颈位于候选动作、重复状态、搜索深度还是单次规划逻辑。
  • 能用一个最小示例建立稳定的性能基线。

先看三个核心指标

规划性能排查首先要避免只看“总耗时”。一次规划即使只用了 30 ms,也可能已经扩展了大量节点;下一组世界状态稍有变化,就可能突然放大搜索成本。

最实用的第一层指标是 expandedNodes、duplicateStates 和 planningMs。前者反映搜索工作量,第二个反映去重命中情况,第三个反映真实墙钟时间。三者一起看,比单独看耗时更容易定位问题。

可以把一次规划视为:候选动作不断扩展状态,状态经过规范化后进入 visited 集合;若状态已经出现,则记为重复状态并跳过。若 expandedNodes 很高而 duplicateStates 很低,通常更应检查动作分支数或搜索深度;若 duplicateStates 占比很高,则优先检查状态键是否规范、去重是否有效。

给规划器加最小统计

下面的示例使用 Python 演示一个可运行的计时与计数器。它没有依赖具体游戏引擎,重点是展示应该记录什么,以及怎样把指标放在一次规划调用的边界内。

python
from dataclasses import dataclass
from time import perf_counter


@dataclass
class PlanningMetrics:
    expanded_nodes: int = 0
    duplicate_states: int = 0
    planning_ms: float = 0.0


def plan(initial_state: frozenset[str], goal: frozenset[str]) -> PlanningMetrics:
    metrics = PlanningMetrics()
    queue = [initial_state]
    visited = {initial_state}
    start = perf_counter()

    # 这里只模拟状态扩展,真实项目中这里应调用 GOAP 的动作适配器。
    while queue and metrics.expanded_nodes < 10000:
        state = queue.pop(0)
        metrics.expanded_nodes += 1

        if goal.issubset(state):
            break

        for fact in ("has_key", "door_open", "inside_room"):
            if fact in state:
                continue
            next_state = frozenset((*state, fact))
            if next_state in visited:
                metrics.duplicate_states += 1
                continue
            visited.add(next_state)
            queue.append(next_state)

    metrics.planning_ms = (perf_counter() - start) * 1000
    return metrics


if __name__ == "__main__":
    result = plan(frozenset(), frozenset({"inside_room"}))
    print(f"expandedNodes={result.expanded_nodes}")
    print(f"duplicateStates={result.duplicate_states}")
    print(f"planningMs={result.planning_ms:.3f}")

预期输出

text
expandedNodes=4
duplicateStates=3
planningMs=<TIME>

其中 planningMs 会随机器性能和运行环境变化;真正接入项目时,应在每次规划结束后记录这些字段,而不是只打印一次。

用指标判断搜索瓶颈

定位时可以先看三个关系,而不是直接改算法。第一是 expandedNodes / planningMs:节点不多但耗时高,说明单节点检查、状态复制、启发式计算或动作条件判断可能偏重。第二是 duplicateStates / expandedNodes:重复率很高时,搜索可能在大量无效分支上循环。第三是不同世界状态下的指标变化:如果某个目标或某个动作集合让节点数突然增长,应优先缩小问题范围。

例如,同样是“进入房间”,加入 open_door、find_key、unlock_door 后,如果扩展量从几十增长到数千,不应先提高超时阈值。先记录候选动作数量、每个深度的扩展节点数,以及哪些状态键最常重复,通常能更快找到分支爆炸的位置。

GOAP 搜索性能指标定位链路

从单次慢规划缩小范围

有了指标以后,下一步是做“对照实验”。保持初始状态和目标不变,只减少一类动作;或者保持动作集合不变,只减少世界状态事实。这样可以观察某个变化是否直接降低 expandedNodes。

如果减少动作数量后节点扩展显著下降,瓶颈多半来自动作分支数;如果节点数量变化不大,但 planningMs 明显下降,则更值得检查动作前置条件、状态复制或代价计算。若两个指标都没有明显变化,就继续检查搜索终止条件、重复状态键和是否存在不必要的深度扩展。

一个很实用的运行期记录格式是:goalId、expandedNodes、duplicateStates、maxDepth、planningMs、result。把这些字段放在同一条结构化日志中,才能比较不同目标和不同世界状态下的规划行为。排查性能时,先找到“哪一种输入让指标异常”,再去看具体代码,通常比盲目优化整个规划器更快。

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

目录与阅读设置

记录一个想法

搜索空间变大怎么定位

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

登录哪都通