游戏 AI / 系统课时
用累计代价比较计划
用累计代价比较计划
当多个行动序列都能达到同一个目标时,GOAP 需要用累计代价而不是单个动作的成本来比较计划。把每一步的成本相加,再从满足目标的候选计划中选择最低值,可以避免 NPC 因为只看眼前动作便走进更昂贵的后续路径。
学习目标
- 计算一条完整计划的累计成本
- 在多个可行计划之间选择低成本方案
- 用代码验证计划排序结果并检查成本构成
为什么不能只看第一步
假设 NPC 要拿到钥匙再开门。计划 A 的第一步移动很便宜,但后面需要绕路;计划 B 的第一步稍贵,却能直接接近目标。如果只比较第一步,规划器很容易选择 A,最终总成本反而更高。
累计成本通常可以写成:
规划器先确保计划能够从当前世界状态走到目标状态,再在这些可行计划中比较 。因此,“可达”与“便宜”是两个不同阶段:不能到达目标的计划,即使成本最低,也不应该成为最终答案。
用一个最小例子计算
下面的例子把三个动作建模成字典,并比较两条都能获得钥匙的计划。代码只使用 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']}")预期输出
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,并继续使用更低成本路径扩展。否则规划器可能因为较早到达的高成本节点而错过更优方案。
当所有候选计划都满足目标条件后,累计成本就提供了一条清晰的选择依据。真正上线时,可以再把时间、距离、危险度等原始指标转换成动作成本,并沿用同一套累计规则,这样设计参数和规划算法之间的边界会更加稳定。