游戏 AI / 系统课时
重复状态为什么必须去重
重复状态为什么必须去重
规划器在搜索动作组合时,很容易从不同路径回到同一个世界状态;如果不识别这种重复,搜索会反复展开无意义分支,甚至在可循环动作中永远无法结束。本篇用已访问集合把状态空间控制在可管理范围内。
学习目标
- 能识别规划搜索中的重复状态与循环路径
- 能用规范化状态和已访问集合避免重复展开
- 能判断去重粒度,避免错误合并不同状态
重复状态从哪里产生
GOAP 的搜索节点不是“执行过哪个动作”,而是“当前世界状态是什么”。例如从 A → B → C 得到的状态,可能与另一条 A → D → C 完全相同。只要后续动作的可用条件只依赖当前状态,这两个节点就没有必要再次搜索。
常见循环来自可逆动作,例如开门后又关门、向左移动后又向右移动。如果搜索只记录动作历史,循环路径仍然会不断产生新节点;记录状态后,可以在第二次遇到同一状态时直接跳过。
把状态变成可比较的键
去重的关键不是直接比较可变对象,而是为“会影响规划”的事实建立稳定表示。布尔事实可以用排序后的元组表示,数值事实则需要明确精度或离散规则;不参与前置条件与效果计算的运行时字段不应放进规划状态键。
例如,一个状态可以表示为 frozenset。它不关心事实插入顺序,因此适合做集合键。真正的工程实现还应保证动作效果完成后得到确定性的状态对象,否则同一逻辑状态可能因为表示方式不同而无法命中去重集合。

用已访问集合停止重复展开
下面的最小示例模拟一个 GOAP 状态搜索。动作既可以开门也可以关门,因此图中存在循环;visited 记录已经展开过的状态,重复状态不会再次进入队列。
from collections import deque
ACTIONS = [
("get_key", {"near_chest": True}, {"has_key": True}),
("open_door", {"has_key": True, "door_open": False}, {"door_open": True}),
("close_door", {"door_open": True}, {"door_open": False}),
]
def state_key(state):
return tuple(sorted(state.items()))
def applicable(state, preconditions):
return all(state.get(k) == v for k, v in preconditions.items())
def apply_effects(state, effects):
next_state = dict(state)
next_state.update(effects)
return next_state
def search(start, goal):
queue = deque([(start, [])])
visited = {state_key(start)}
while queue:
state, path = queue.popleft()
if all(state.get(k) == v for k, v in goal.items()):
return path
for name, preconditions, effects in ACTIONS:
if not applicable(state, preconditions):
continue
next_state = apply_effects(state, effects)
key = state_key(next_state)
# 同一状态再次出现时,后续搜索没有新增信息。
if key in visited:
continue
visited.add(key)
queue.append((next_state, path + [name]))
return None
start = {"near_chest": True, "has_key": False, "door_open": False}
goal = {"door_open": True}
print(search(start, goal))预期输出:
['get_key', 'open_door']这个结果说明 close_door 虽然允许把状态变回 door_open=False,但不会让搜索无限扩张。visited 不是简单的“动作去重”,而是“状态去重”:只要规范化后的状态键相同,就只保留首次到达的节点。
去重粒度怎么定
状态键过粗会导致错误规划,过细则会让搜索规模重新膨胀。最稳妥的原则是:状态键只包含会改变动作前置条件、效果判断或目标判断的规划事实。
例如 has_key、door_open 属于规划事实;NPC 当前动画帧、脚步粒子计时器通常不属于规划事实。若把这些短暂字段全部加入状态键,同一个逻辑状态会被拆成大量“不同状态”,去重效果随之下降。
当状态包含连续数值,例如位置、速度或剩余距离时,需要先定义离散化策略,否则几乎相等的浮点值会被当成不同状态。GOAP 的搜索边界因此不只是算法问题,还取决于你如何定义“两个状态在规划意义上是否相同”。