游戏 AI / 系统课时

搜索节点怎样保存状态

搜索节点怎样保存状态

GOAP 搜索不能只保存“当前选了哪个动作”,还必须知道这个动作从什么状态来、已经付出了多少代价。搜索节点把世界状态、父节点、产生该节点的动作和累计代价绑在一起,才能在找到目标后稳定重建完整计划。

学习目标

  • 理解搜索节点中四类核心数据的职责
  • 能用父节点链重建动作路径
  • 能根据累计代价比较不同候选路径

一个节点到底记录什么

最小可用的 GOAP 搜索节点通常包含 state、parent、action 和 cost。state 表示执行到这里时的世界状态;parent 指向上一个节点;action 记录从父节点到当前节点执行了什么;cost 则记录从起点累计到当前节点的总代价。

GOAP 搜索节点的数据关系

为什么父节点比直接存路径更合适

一种直观做法是在每个节点里直接保存完整动作列表,例如 plan=["find_key", "unlock_door"]。但每扩展一个节点都要复制这份列表,分支越多,重复数据越多。

父节点指针则把公共前缀共享起来。节点只保存“我是从谁、通过什么动作得到的”,等真正找到目标节点时再沿 parent 一层层向前回溯。这样既方便搜索扩展,也方便统一处理不同分支。

用数据结构实现节点

下面示例展示一个可运行的最小节点结构,并演示如何从目标节点恢复动作计划。它不依赖第三方库。

python
from dataclasses import dataclass
from typing import Optional

@dataclass
class SearchNode:
    state: frozenset[str]
    parent: Optional["SearchNode"]
    action: Optional[str]
    cost: int


def rebuild_plan(goal_node: SearchNode) -> list[str]:
    actions: list[str] = []
    current = goal_node

    # 从目标向起点回溯,再反转得到实际执行顺序。
    while current.parent is not None:
        if current.action is not None:
            actions.append(current.action)
        current = current.parent

    actions.reverse()
    return actions


start = SearchNode(
    state=frozenset({"has_key", "door_locked"}),
    parent=None,
    action=None,
    cost=0,
)

unlock = SearchNode(
    state=frozenset({"has_key", "door_unlocked"}),
    parent=start,
    action="unlock_door",
    cost=2,
)

goal = SearchNode(
    state=frozenset({"has_key", "door_unlocked", "door_open"}),
    parent=unlock,
    action="open_door",
    cost=3,
)

print(rebuild_plan(goal))
print(goal.cost)

预期输出:

text
['unlock_door', 'open_door']
3

这里 cost=3 是从起点累计到目标节点的总代价,不是当前动作单独的费用。实际搜索时,扩展节点通常会计算 new_cost = current.cost + action.cost,再决定是否把新节点加入待搜索集合。

状态为什么必须属于节点

同一个动作在不同世界状态下可能得到完全不同的后续结果。例如一个节点表示“有钥匙且门锁着”,另一个节点表示“没有钥匙且门锁着”,两者都可能考虑 unlock_door,但后者实际上不可行。

因此,搜索去重时不能只看最后执行的动作,而应至少比较节点状态。最常见的做法是把状态编码成可哈希的事实集合,例如 frozenset,这样可以放入 set 或字典中记录已经访问过的状态。

状态保存还直接关系到路径验证。找到目标节点后,可以沿父节点回溯得到动作链,再按顺序重新应用每个动作检查前置条件;只要中间某一步无法成立,就说明搜索节点或状态转移逻辑存在问题。

累计代价怎样参与搜索

GOAP 的目标通常不只是“找到一条路径”,而是找到满足目标的低代价路径。节点保存累计代价后,就可以比较两条到达相同状态的路径,例如一条代价为 3,另一条代价为 7,搜索可以优先保留前者。

当使用优先队列进行代价搜索时,节点可以按 cost 排序;如果进一步加入启发式估计,则可以比较 $f(n)=g(n)+h(n)$,其中 g(n)g(n) 是节点累计代价,h(n)h(n) 是到目标的估计代价。无论采用哪种策略,节点中的 parent 都仍然负责最终路径重建。

搜索节点设计的关键不是字段越多越好,而是每个字段都服务于“判断状态、扩展节点、比较代价、恢复路径”这四件事。把这条边界守住,后续替换搜索策略或增加启发式函数时,节点结构通常无需大改。

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

目录与阅读设置

阅读设置

17

记录一个想法

搜索节点怎样保存状态

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

登录哪都通