游戏 AI / 系统课时
搜索节点怎样保存状态
搜索节点怎样保存状态
GOAP 搜索不能只保存“当前选了哪个动作”,还必须知道这个动作从什么状态来、已经付出了多少代价。搜索节点把世界状态、父节点、产生该节点的动作和累计代价绑在一起,才能在找到目标后稳定重建完整计划。
学习目标
- 理解搜索节点中四类核心数据的职责
- 能用父节点链重建动作路径
- 能根据累计代价比较不同候选路径
一个节点到底记录什么
最小可用的 GOAP 搜索节点通常包含 state、parent、action 和 cost。state 表示执行到这里时的世界状态;parent 指向上一个节点;action 记录从父节点到当前节点执行了什么;cost 则记录从起点累计到当前节点的总代价。

为什么父节点比直接存路径更合适
一种直观做法是在每个节点里直接保存完整动作列表,例如 plan=["find_key", "unlock_door"]。但每扩展一个节点都要复制这份列表,分支越多,重复数据越多。
父节点指针则把公共前缀共享起来。节点只保存“我是从谁、通过什么动作得到的”,等真正找到目标节点时再沿 parent 一层层向前回溯。这样既方便搜索扩展,也方便统一处理不同分支。
用数据结构实现节点
下面示例展示一个可运行的最小节点结构,并演示如何从目标节点恢复动作计划。它不依赖第三方库。
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)预期输出:
['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)$,其中 是节点累计代价, 是到目标的估计代价。无论采用哪种策略,节点中的 parent 都仍然负责最终路径重建。
搜索节点设计的关键不是字段越多越好,而是每个字段都服务于“判断状态、扩展节点、比较代价、恢复路径”这四件事。把这条边界守住,后续替换搜索策略或增加启发式函数时,节点结构通常无需大改。