GOAP 目标导向型行为计划 AI 算法
全称: Goal-Oriented Action Planning
定义：目标导向型行为计划，参考 STRIPS-like，专门设计用于游戏中自主角色行为实时控制的规划体系结构。
参考：http://alumni.media.mit.edu/~jorkin/goap.html
GOAP 是让 AI 自己去找到解决问题的方法，我们给AI 提供可以执行的行为，对世界的描述，每个行为执行的先决条件，以及执行行为对世界产生的影响效果。
AI 需要有目标（一个或多个均可），通过世界状态，根据自身行为，找到一组或多组可以完成某个目标的行为列表，根据优先级或者综合排序，决策出一个最佳行为队列，并按照顺序执行一系列行为。
例子：
AI 饿了，要找吃的填饱肚子。
AI 有行为：去饭店、买菜、做饭、翻冰箱找面包、吃东西
1.去到饭店可以吃饭
2.买菜回来可以做饭然后吃饭
3.翻冰箱找面包，找到面包可以吃
4.有吃的就可以去吃东西
以上五中行为可以组合成 4 组 达到吃东的目的。
每个行为都是有先决条件和执行效果的。行为是否能够执行必须要考虑到先决条件是否满足。
行为先决条件执行效果Cost去饭店有饭店买到饭(有吃的)30买 菜有超市买到菜15做 饭有 菜做好饭(有吃的)10翻冰箱冰箱有面包找到面包(有吃的)30吃 饭有吃的吃东西（完成吃东西目标）5
AI 遍历所有行为，根据当前世界状态，获取满足执行条件的行为A。将行为A添加到可执行列表中，将A 作为一个行为链的开始，继续遍历剩下的行为，直到可以完成目标为止，为一个可以完成目标的行为链。如此下去最终找到 N 组可以完成目标的行为链。
第一次遍历
世界状态：有超市、没吃的、没菜、没冰箱、有饭店。
遍历所有行为,行为序列为：去饭店、做饭、翻冰箱、买菜、吃饭
去饭店行为要求有饭店 ：条件满足，加入可执行队列
做饭行为要求有菜： 不满足跳过
翻冰箱行为要求有冰箱：不满足跳过
买菜行为要求有超市 ： 条件满足，加入可执行队列
吃饭行为要求有吃的 ： 不满足跳过
第一次遍历完成，可执行行为队列中有行为：去饭店、买菜
遍历可执行行为队列，以队列中每一个行为为开端，重新遍历，这样就会生成两个分支，
分支 1：去饭店
分支 2：去超市买菜
以去超市买菜分支为例，买菜行为做为开端开始遍历
拷贝当前世界状态为 newWorldState。拷贝行为序列 newActionList，排除掉买菜行为。
注意：以任何行为为开端开始执行遍历，都要将该行为从行为序列中删除，否则会出现无限循环，且没有意义
以 newWorldState 为世界状态，newActionList 为行为序列，开始新一轮遍历，将买菜行为执行效果（买到菜/有菜）更新到 newWorldState，判断 newWorldState 是否包含目标 吃饭，如果包含则视为可以完成目标，退出遍历。
newWorldState没有包含吃饭，没有完成目标继续
此时 newWorldState 世界状态为：有超市、没吃的、有菜、没冰箱、有饭店
newActionList 为行为序列为： 去饭店、做饭、翻冰箱、吃饭
去饭店行为要求有饭店 ：条件满足，加入到新的行为队列，以买菜行为为父节点
做饭行为要求有菜 ： 条件满足，加入到新的行为队列，以买菜行为为父节点
翻冰箱行为要求有冰箱 ：不满足跳过
吃饭行为要求有吃的 ：不满足跳过
遍历结束，以买菜行为为开端，加入一个 去饭店行为，一个 做饭行为。
到此去买菜行为又产生两个分支，这两个分支都是从 分支 2 上产生的。
分支 2.1 ： 去超市买菜 -> 去饭店
分支 2.2 ：去超市买菜 -> 做饭
然后遍历 分支 2.1 和 2.2，继续查找可执行序列
以 分支 2.2 为例，做饭行为作为开端开始遍历
拷贝newWorldState状态为 newWorldState_2_2。拷贝newActionList行为序列 newActionList_2_2，排除掉做饭行为。
以 newWorldState_2_2为世界状态，newActionList_2_2 为行为序列，开始新一轮遍历，将做饭行为执行效果（有饭/有吃的）更新到 newWorldState_2_2，判断 newWorldState_2_2 是否包含目标 吃饭，如果包含则视为可以完成目标，退出遍历。
newWorldState_2_2 没有包含吃饭，没有完成目标继续
此时 newWorldState_2_2 世界状态为：有超市、有吃的、有菜、没冰箱、有饭店
newActionList 为行为序列为： 去饭店、翻冰箱、吃饭
去饭店行为要求有饭店 ：条件满足，加入到新的行为队列，以买菜行为为父节点
翻冰箱行为要求有冰箱 ：不满足跳过
吃饭行为要求有吃的 ：条件满足，加入到新的行为队列，以买菜行为为父节点
遍历结束，以分支 2.2 做饭行为为开端，加入一个 去饭店行为，一个吃饭行为。
到此去做饭行为又产生两个分支，这三个分支都是从 分支 2.2 上产生的。
分支 2.2.1 ： 去超市买菜 -> 做饭 -> 去饭店
分支 2.2.2 ： 去超市买菜 -> 做饭 -> 吃饭
到此 分支 2.2.2 分支已可以完成 吃饭目标了，为一个完整的达到目标的可执行序列。保存起来。
上面所有分支都要遍历完成，这里只是讲述原理，不能做到将所有分
引用块内容
支都走一遍。
最终结果大概有如下几种
A ：去饭店 -> 吃饭
B ：去饭店 -> 买 菜 -> 做饭 -> 吃饭
C ：买 菜-> 做饭 -> 去饭店 -> 吃饭
D： 买 菜 -> 做饭 -> 吃饭
E： 买 菜-> 去饭店-> 做饭 -> 吃饭
如何找到最有解，设置每种行为的 消耗 cost，每中方案 总消耗为 所有行为的 cost 相加，找到 总 cost 最小的一个。
那么如上 A – E 几种方案的消耗如下
方案行为序列CostA去饭店 -> 吃饭30+5 = 35B去饭店 -> 买 菜 -> 做饭 -> 吃饭30 + 15 + 10 + 5 = 60C买 菜-> 做饭 -> 去饭店 -> 吃饭15 + 10 + 30 + 5 = 60D买 菜 -> 做饭 -> 吃饭15 + 10 + 5 = 30E买 菜-> 去饭店-> 做饭 -> 吃饭15 + 30 + 10 + 5 = 60
最终确定执行 D 方案为最优解
Demo下载地址