游戏 AI / 系统课时

用累计代价比较计划

用累计代价比较计划

当多个行动序列都能达到同一个目标时,GOAP 需要用累计代价而不是单个动作的成本来比较计划。把每一步的成本相加,再从满足目标的候选计划中选择最低值,可以避免 NPC 因为只看眼前动作便走进更昂贵的后续路径。

学习目标

  • 计算一条完整计划的累计成本
  • 在多个可行计划之间选择低成本方案
  • 用代码验证计划排序结果并检查成本构成

为什么不能只看第一步

假设 NPC 要拿到钥匙再开门。计划 A 的第一步移动很便宜,但后面需要绕路;计划 B 的第一步稍贵,却能直接接近目标。如果只比较第一步,规划器很容易选择 A,最终总成本反而更高。

累计成本通常可以写成:

C(plan)=∑i=1ncost(actioni)C(plan)=\sum_{i=1}^{n} cost(action_i)

规划器先确保计划能够从当前世界状态走到目标状态,再在这些可行计划中比较 C(plan)C(plan)。因此,“可达”与“便宜”是两个不同阶段:不能到达目标的计划,即使成本最低,也不应该成为最终答案。

用一个最小例子计算

下面的例子把三个动作建模成字典,并比较两条都能获得钥匙的计划。代码只使用 Python 标准库,运行后会输出每条计划的动作列表和累计成本。

python
plans = [
    {
        "name": "direct_route",
        "actions": [
            {"name": "move_to_gate", "cost": 4},
            {"name": "open_gate", "cost": 2},
            {"name": "take_key", "cost": 5},
        ],
    },
    {
        "name": "safe_route",
        "actions": [
            {"name": "move_to_side_path", "cost": 3},
            {"name": "avoid_guard", "cost": 4},
            {"name": "take_key", "cost": 3},
        ],
    },
]

for plan in plans:
    plan["total_cost"] = sum(action["cost"] for action in plan["actions"])

best_plan = min(plans, key=lambda plan: plan["total_cost"])

for plan in plans:
    print(f"{plan['name']}: {plan['total_cost']}")

print(f"selected: {best_plan['name']}")

预期输出

text
direct_route: 11
safe_route: 10
selected: safe_route

这里的关键不是 min() 本身,而是比较对象已经从“单个动作”提升为“完整计划”。safe_route 的第一步成本只有 3,确实比 direct_route 的 4 便宜;但真正决定选择的是全部动作累加后的 10,而不是第一步的局部最优。

把累计代价放进规划器

实际 GOAP 规划器通常会在扩展状态时生成新的候选节点,并为节点保存已经支付的累计成本。若当前节点成本为 current_cost,新增动作成本为 action_cost,新的计划成本就是 current_cost + action_cost。当同一个世界状态可以通过不同路径到达时,应优先保留成本更低的那条路径,这能减少无意义搜索。

一个实用的记录结构可以包含 state、actions 和 total_cost。调试时同时打印动作序列与总成本,能立即确认规划器是否真的选择了最低成本路径,而不是因为排序、状态去重或终止条件错误而提前结束。

注意负成本和状态去重

默认情况下,动作成本最好保持非负。这样累计成本会随计划扩展而不会下降,搜索过程也更容易比较。若为了表达奖励而使用负成本,必须重新检查搜索算法的正确性,尤其是存在循环动作时,可能产生无限降低的路径。

状态去重也不能只比较“到达过没有”。同一个状态可能被不同路径到达,例如第一次成本为 14,后来发现另一条路径只需 9,那么应该更新为 9,并继续使用更低成本路径扩展。否则规划器可能因为较早到达的高成本节点而错过更优方案。

当所有候选计划都满足目标条件后,累计成本就提供了一条清晰的选择依据。真正上线时,可以再把时间、距离、危险度等原始指标转换成动作成本,并沿用同一套累计规则,这样设计参数和规划算法之间的边界会更加稳定。

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

目录与阅读设置

记录一个想法

用累计代价比较计划

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

登录哪都通