游戏 AI / 系统课时

重复状态为什么必须去重

重复状态为什么必须去重

规划器在搜索动作组合时,很容易从不同路径回到同一个世界状态;如果不识别这种重复,搜索会反复展开无意义分支,甚至在可循环动作中永远无法结束。本篇用已访问集合把状态空间控制在可管理范围内。

学习目标

  • 能识别规划搜索中的重复状态与循环路径
  • 能用规范化状态和已访问集合避免重复展开
  • 能判断去重粒度,避免错误合并不同状态

重复状态从哪里产生

GOAP 的搜索节点不是“执行过哪个动作”,而是“当前世界状态是什么”。例如从 A → B → C 得到的状态,可能与另一条 A → D → C 完全相同。只要后续动作的可用条件只依赖当前状态,这两个节点就没有必要再次搜索。

常见循环来自可逆动作,例如开门后又关门、向左移动后又向右移动。如果搜索只记录动作历史,循环路径仍然会不断产生新节点;记录状态后,可以在第二次遇到同一状态时直接跳过。

把状态变成可比较的键

去重的关键不是直接比较可变对象,而是为“会影响规划”的事实建立稳定表示。布尔事实可以用排序后的元组表示,数值事实则需要明确精度或离散规则;不参与前置条件与效果计算的运行时字段不应放进规划状态键。

例如,一个状态可以表示为 frozenset。它不关心事实插入顺序,因此适合做集合键。真正的工程实现还应保证动作效果完成后得到确定性的状态对象,否则同一逻辑状态可能因为表示方式不同而无法命中去重集合。

GOAP 重复状态与去重流程

用已访问集合停止重复展开

下面的最小示例模拟一个 GOAP 状态搜索。动作既可以开门也可以关门,因此图中存在循环;visited 记录已经展开过的状态,重复状态不会再次进入队列。

python
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))

预期输出:

text
['get_key', 'open_door']

这个结果说明 close_door 虽然允许把状态变回 door_open=False,但不会让搜索无限扩张。visited 不是简单的“动作去重”,而是“状态去重”:只要规范化后的状态键相同,就只保留首次到达的节点。

去重粒度怎么定

状态键过粗会导致错误规划,过细则会让搜索规模重新膨胀。最稳妥的原则是:状态键只包含会改变动作前置条件、效果判断或目标判断的规划事实。

例如 has_key、door_open 属于规划事实;NPC 当前动画帧、脚步粒子计时器通常不属于规划事实。若把这些短暂字段全部加入状态键,同一个逻辑状态会被拆成大量“不同状态”,去重效果随之下降。

当状态包含连续数值,例如位置、速度或剩余距离时,需要先定义离散化策略,否则几乎相等的浮点值会被当成不同状态。GOAP 的搜索边界因此不只是算法问题,还取决于你如何定义“两个状态在规划意义上是否相同”。

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

目录与阅读设置

记录一个想法

重复状态为什么必须去重

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

登录哪都通