游戏AI：在游戏上使用面向目标行为规划系统
在游戏上使用面向目标行为规划系统
本文为本人的翻译文章，原文《Applying Goal-Oriented Planning for Games 》连接为：
http://alumni.media.mit.edu/~jorkin/GOAP_draft_AIWisdom2_2003.pdf
Jeff Orkin – Monolith Productions
有相当数量的游戏已经实现了带有目标导向决策能力的角色。一个目标导向的角色能显示出一些智能的权衡，他们通过自主决定激活一些行为，这些行为会完成那些在任何情况下最有意义的目标。面向对象行为规划（GOAP：Goal-Oriented Action Planning）是一个更进一步的决策架构，它允许角色不只是决定要做什么，还有如何做。但是我们为什么想要让我们的角色拥有这么大的自由度？
一个能规划它自己的计划来完成自己目标的角色，将会表现出很少重复性、可预期的行为，并且可以更好的针对他的当前状况进行行动。另外，GOAP架构的结构本质能促进编写、维护和重用行为。
《No One Live Forever 2: A Spy in H.A.R.M.’s Way(NOLF2)》[Monolith02] 是一个包含了目标导向自主角色的游戏例子，但是它没有规划能力。在NOLF2中的角色时常重估他们的目标，然后选择最有意义的目标去控制他们的行为。那个激活的目标通过一个写死了的状态转换序列，决定了角色的行为。
此文探索游戏可以从一个实时规划系统中能得到什么好处，用NOLF2开发过程中碰到的问题，来说明这些论点。
术语定义
我们在讨论GOAP的好处之前，我们首先需要定义一些属于。一个代理使用一个规划者（planner）去规划（formulate）一个动作（actions）序列，这个序列将完成一些目标（goal）。我们需要定义目标、动作、计划、和规划的含义。
目标Goal
一个目标是一个代理想要完成的任何情况。一个代理将有任何数量的目标。在NOLF2里面的角色基本拥有大概25个目标。任何时刻，都有一个激活的目标，控制着角色的行为。一个目标知道如何计算它当前的相关性，以及知道什么时候它被完成。
在NOLF2中的目标分为三类：轻松型目标，调查型目标，侵略型目标。轻松型目标包括诸如睡觉、工作和巡逻这类被动目标。调查型目标包括更带怀疑性质的调查和搜索。侵略型目标用于战斗场景，好像追赶，冲锋，和从隐蔽处攻击。
虽然概念上相似，但在NOLF2中使用的目标，和GOAP指的目标两者之间，还是有一个关键的不同之处。一旦一个目标被激活，那个角色就从头到尾的执行一遍一个预定义的步骤序列，这个序列是被硬编码在目标里面的。这个内嵌的行为计划可以包含条件分支，但是这些分支都是在目标编写的时候被预先规定好的。在GOAP里的目标不会包含一个行动计划。相反，他们仅仅简单的定义，满足这个目标需要具备什么条件。用于到达这些满足条件的步骤，是实时决定的。
计划Plan
计划只是简单的一个动作序列的名字。满足一个目标的计划，指的是一个可行的动作序列，这个序列可以让一个角色从开始状态走到满足目标的状态。
动作Action
一个动作，指的是在令一个角色做某些事的计划里的，一个简单的，原子的步骤。可能的动作包括移动到位置，激活对象，抽出武器，重新装弹，和攻击。一个动作的持续时间可能很短，也可能是无限长。重新装弹动作在角色完成一个装弹动画后就会结束。攻击动作可能无限存在，直到目标死亡。
每个动作都知道什么时候可以跑，以及可以对这个游戏世界做什么事。换句话说，一个动作知道它的先决条件和效果。先决条件和效果提供一个机制，把动作链接成一个可行的序列。例如，攻击有一个先决条件，是那个角色的武器装好弹了。重新装弹的效果是武器被转好子弹。这很容易看出来重新装弹跟在攻击之后，是一个有效的动作序列。每个动作都可以能有任意数量的先决条件和效果。
一个GOAP系统不会去代替一个有限状态机（FSM）的需求，但会大大简化所需要的FSM。每个动作都代表着一个状态转换，这些动作所组成的一个序列就是一个计划。把状态自己从状态转换逻辑中拆分出来，这个基础的FSM就会非常简单。例如，闪避和重新装弹是不同的动作，但他们都会把角色的状态设置成活动，然后指定一个动画去播放。不同于拥有一个巡逻或者游荡状态，一个GOAP系统可以规划一个计划，命令那个角色到达移动状态，从而在一批巡逻点之间移动。最后，那个移动和活动状态覆盖了那个角色所做的大部分事情；他们仅仅是由于不同的原因去做这些事。动作定义了何时转换进入和转换退出一个状态，以及这个游戏世界发生的事情，作为这个转换的结果。
计划制订Plan Formulation
一个角色，通过供应一些目标去满足一个系统的方式，去实时生成一个计划，这样的角色被成为规划者。规划者在大量动作的范围中搜索出一个动作序列，使一个角色从他的开始状态去到他的目标状态。这个过程被称为规划一个计划。如果规划者成功了，它会返回一个计划给那个角色，让其指挥自己的行为。这个角色执行这个计划直到完成，失效，或者直到另外一个目标变得更加有意义。如果另外一个目标激活了，或者正在执行的计划因为任何原因变得无效，那个角色会取消当前计划然后规划一个新的计划。
图示1. 计划的规划过程
图示1描绘了一个虚拟的计划过程图解。长方形表示开始和目标状态，每个圆形代表一个动作。在图示1里面的目标是杀到一个敌人。因此，目标状态是敌人死掉了的世界的状态。规划者需要为那个角色找到一个动作序列，让这个世界从有活着的敌人，变成有死掉的敌人的状态。
这个过程看起来很像寻路！从某种意义上正式这样。规划者需要找到一条路径，通过动作的空间，让那个角色从他的开始状态到某个目标状态。每个动作都是那条路径上的一步，这些步骤会通过某种方式改变所在世界的状态。动作的先决条件决定了何时从一个动作移动到另外一个动作是可行的。
在很多情况下，存在超过一个可行计划。规划者只需要找到其中一个。类似导航寻路，规划者的搜索算法可以提供指导搜索的提示。例如，消耗可以和动作关联起来，引导规划者找到最小消耗的动作序列，而不是任意的武断序列。
所有这些搜索听起来好像是一大堆工作。它值得吗？现在我们已经定义了我们的术语，我们可以讨论这些决策过程的好处了。
使用GOAP的好处
在开发和运行时都有很多好处。使用GOAP，游戏里的角色可以表现出更多变，更复杂，和更有趣的行为。在诸多行为背后的代码会更结构化，更能重用，和更可维护。
运行时行为的好处
一个在运行时决定他自己的计划的角色，能自主的调整他的行为以适应环境，并且动态的找到问题的解决方案。这最好以一个例子来解释。
想象一下，一个角色X发现了一个想要消灭的敌人。通常来说，最好的行动步骤是掏出装好子弹的武器，然后向这个敌人开火。然而在这种情况下，X没有武器，或者可能没有子弹，所以他需要找到一个替换的方案。幸运的是，在那个X附近有一个固定的激光炮，可以用来炸到敌人。X可以规划一个行动计划，走去那个激光炮那里，激活它，然后用它来杀人。此计划可能看起来像：
走到（激光炮）
激活物体（激光炮）
固定攻击（激光炮）
问题解决了！角色X要求规划者提供到达杀死敌人的目标的方法，然后规划者规划了一个可行的计划去满足它。当规划者想要包含掏出武器动作到他的动作序列里的时候，碰到了一个死胡同，因为掏出武器具有一个先决条件，要求角色有一件武器。相反它找到了一个不需要角色有一个武器的替代方案。
但等等！如果安装的激光炮需要电力，而且发电机被关掉的情况呢？规划者也可以很好的解决这个情况。这个情况的可行方案包含首先去发电机那里打开它，然后使用激光炮。此计划可能像这样：
走到（发电机）
激活物体（发电机）
走到（激光炮）
激活物体（激光炮）
固定攻击（激光炮）
GOAP决策框架运行角色X处理那些在行为开发期没有预期到的依赖性问题。
开发的好处
用手写代码或者脚本处理每一个可能的情况会跑得毛快。想象一下一个为了杀死敌人目标的，带有一个处理前文所述情况的内嵌进计划的代码。那个目标的内嵌计划需要处理角色有、或者没有武器，加上寻路，替换激活毁灭手段。
人们很容易被诱惑，去把杀死敌人目标拆分成多个更小的目标，比如用武器杀死敌人，用固定装置杀死敌人。这就是本质上我们为NOLF2所做的事，但是目标的增生有它自己的问题。越多的目标意味着更多要维护的代码，并且每次设计变化都要再看一遍。
表面上看，是笨拙的额外设计导致NOLF2开发期间的头疼问题。例如这些额外设计，包括掏枪和收枪，进入黑屋子时打开灯，以及打开门之前激活安全键盘。每个这种额外设计都需要重新过一次每个目标的代码，确保内嵌计划可以处理新的需求。
GOAP提供一个更优雅简洁的框架，用以更好的适应变化。那些额外的设计需求以增加动作，安排相关动作的先决条件的方式来解决。这样更直观，并且比重新过一次每个目标接触更少的代码。例如，需要角色进黑屋子前开灯，可以通过给移动到位置增加一个先决条件——目的地的灯必须开着，这种方式来解决。
更进一步的是，GOAP提供了可行计划的保证。手写内嵌计划可能包含错误。一个开发者可能编写一个不能符合每个其他动作的序列。例如，一个角色可能被命令用武器开火，而没有被告诉要先掏出武器。这个情况在通过GOAP系统动态生成的计划里面是不可能出现的，因为动作里的先决条件能防止规划出一个无效的计划。
多样化的好处
强制使用GOAP的结果能完美的创造各种各样的角色类型，他们能表现出不同的行为，并且能在多个项目里面共享行为。规划者被提供了一个了动作池，从这个池子里面规划出计划来。这个池子不需要是拥有所有存在动作的完全池子。不同的角色类型可以使用完全池子的子集，从而产生各种各样的行为。
NOLF2有一大批不同的角色类型，包括士兵，模仿士，忍者，超级士兵，和小兔子。我们尝试在所有这些角色类型中尽量多的共享AI代码。这有时候导致了在行为代码中没预料到的分支。一个难搞的分支，就是关于角色如何处理一个关上的门。一个人类停在门前，打开门，然后走进门去，然而一个半机械超级士兵要把门从铰链上撞碎，然后继续走。处理穿过门的代码，需要一个分支来检查这是否一个粉碎门的角色。
一个GOAP系统可以更优美的处理这种情况，通过提供每个角色类型一个不同的完成同样效果的动作。一个人类角色可以使用开门动作，然而一个超级士兵使用撞门动作。这两个动作都有相同的效果。他们两个都打开了一条之前被门堵上的路。
有其他的方案来解决撞门和开门的问题，但是没有一个和GOAP方案一样灵活。例如，开门和撞门状态可以来源于一个处理门类。使用一个像这样的状态类层次，一个设计者可以分配装到到很多插槽中去，比如处理门插槽，建立具备不同的处理门方法的角色类型。但如果我们想要一个角色在放松的时候是开门的，在激动的时候撞门的，应该怎么办？状态类层次需要一个外部机制，去换出在特定情况下的处理门插槽的状态。GOAP方案允许一个角色始终同时具有开门和撞门两个动作。在每个动作上为所需心情，设置的一个额外先决条件，允许角色实时的选择合适的动作去处理门的事情，而无需任何额外的干预。
实现指引
现在你能看到各种好处，而且对在游戏中使用GOAP的前景非常兴奋，但是你可能需要清楚一些好的和坏的消息。坏的消息是涉及实现一个GOAP系统，会有一大批挑战。第一个挑战是决定搜索动作空间的最佳方法。第二个挑战是世界的表达方法。为了规划出一个计划，规划者必须能够以一种紧凑和简明的形式表达那个世界的状态。这两个话题在学术界都是一个很大的研究领域，一个完整的论述已经超出了这个文章的范围。好消息是我们可以仅仅为游戏领域钉住简单的方案。剩下的篇幅描述了一些合理的方案，以对游戏开发来说有意义的方式，来解决这些挑战。
之前我们观察到，计划制订的过程明显的很像寻路导航。这些过程非常类似，实际上，我们可以使用相同的算法！规划者的搜索可以被一个大多数游戏AI开发者私下里已经很熟悉的算法所驱动：叫做A*。尽管很多游戏开发者认为A*是一个寻路算法，但是它实际上是一个通用的搜索算法。如果A*被实现成模块风格的，类似[Higgins02a]所描述的那样，这个算法的大多数代码都可以在寻轮系统和规划者之间共享。规划者只需要实现它自己的类，用来对应A*的节点(node)、图(map)、和目标(goal)。
A*算法需要节点消耗的计算，以及从一个节点到目标的启发式距离。在规划者的搜索中的节点，代表了世界的状态，节点间的边界是动作。节点的消耗，可以通过汇总所有动作的消耗计算获得，这些动作使世界到达节点所代表的状态。每个动作的消耗可能是多变的，越低消耗的动作是越好的。启发性距离可以用未满足的目标状态的特性汇总起来计算得到。
在用A*搜索时我们有两个选择。我们可以向前搜索，从当前状态开始然后搜索一个通向目标状态的路径，或者我们可以向后搜索，从目标到开始状态。我们来先测试一下向前搜索是如何工作的，我们的例子还是之前描述的情况，当一个没有武装的角色想消灭一个敌人，同时有一个固定的需要电力的激光炮。向前搜索首先会用跑去位置动作告诉角色跑去激光炮那里，然后用固定武器攻击动作告诉角色使用那个激光炮。如果电源没开，固定武器攻击的先决条件会失败。这会让一个详尽的强力搜索得出一个可行的计划，首先让角色去打开发电机，然后使用激光。
一个退化的搜索会更高效和直观。向后搜索会从目标触发，然后发现固定武器攻击动作会满足这个目标。从那里起，这个搜索会继续根据满足固定武器攻击动作的先决条件来查找动作。先决条件会引导角色一步步的到达最终计划，首先打开发电机，然后使用激光炮。
为了搜索动作空间，规划者需要以某种方式描述世界的状态，以便能容易的应用动作的先决条件和效果，并且辨识出合适到达了目标状态。其中一个紧凑的描述世界状态的方法是使用一个世界属性结构列表，它包含一个枚举类型的属性key，一个value，和一个处理某题目的handle。
structSWorldProperty
{
GAME_OBJECT_IDhSubjectID;
WORLD_PROP_KEYeKey;
unionvalue
{
boolbValue;
floatfValue;
intnValue;
...
};
};
这样，如果我们想描述那个能满足杀死敌人目标的世界状态，我们会用一个像下面这样的属性来提供目标状态：
SWorldPropertyProp;
Prop.hSubjectID= hShooterID;
Prop.eKey= kTargetIsDead;
Prop.bValue = true;
以这种方式来描述世界的每个方面，将会是压倒性和不可能的任务，但这是不必要的。我们只需要描述对规划者想要去满足的目标，所相关的世界状态的最小属性集合就可以了。如果规划者尝试去满足杀死敌人这个目标，它就无需去知道射手的体力值，当前位置，或者其他任何事情。规划者甚至不需要知道射手想去杀谁！它只需要找到一个能导致这个射手的目标死掉的动作序列就行了，无论这个目标是谁。
当规划者添加动作，和动作的先决条件一起增加的目标转台，被添加到目标的满足状态中。图示2描述了一个规划者的满足杀死敌人目标的退化搜索。在当前状态匹配目标状态时，这个搜索就成功的完成了。和动作一起增加的目标状态增加了他们的先决条件。当前状态会根据规划者为了满足额外的目标属性所增加的额外动作所增加。
图示2. 规划者的退化搜索
在退化搜索的每一步，规划者尝试去找到一个动作，这个动作拥有一个效果能满足那些未被满足的目标条件。当目标状态的属性和当前状态的属性具有不同的值的时候，这个世界的属性就会被认为是未被满足的。通常，解决一个未满足条件的动作会增加额外的被满足的先决条件。当搜索结束，我们可以看到一个有效的计划，来满足杀死敌人这个目标：
DrawWeapon
LoadWeapon
Attack
在图示2里的计划例子，由具备表示先决条件和效果的Boolean常量值的动作组成，但必须指出的是，先决条件和效果也可以由变量表示。规划者在对目标退化的时候解决这些变量。变量给了规划者能力和灵活性，因为它现在可以满足更一般性的先决条件。举个例子，一个移动动作具备移动一个角色到一个可变距离的效果，会比一个只能移动到固定的，预先定义位置的移动动作更强。
动作可以用预先描述的世界状态描述来表示他们的先决条件和效果。比如，攻击动作的构造器定义了它的先决条件和效果如下：
CAIActionAttack::CAIActionAttack()
{
m_nNumPreconditions= 1;
m_Preconditions[0].eKey= kWeaponIsLoaded;
m_Preconditions[0].bValue= true;
m_nNumEffects= 1;
m_Effects[0].eKey= kTargetIsDead;
m_Effects[0].bValue= true;
}
如果动作即将参与规划者的搜索，它们只需要指定以这个象征方式的先决条件。有可能会有一些能被叫做上下文（context）先决条件的额外条件。一个上下文先决条件类似于需要是true，但是规划者从来不会满足。例如，攻击动作可能需要一个目标是在某个视野距离和范围之内。这是一个比可以用一个枚举值描述的更复杂的检查，并且规划者没有动作可以使这个值变成true，如果它已经不是true了。
当规划者正在搜索动作，它调用两个不同的函数。一个函数检查链接规划者先决条件，而另外一个检查自由形态的上下文先决条件。这个上下文先决条件确认函数可以包含任何武断的返回一个布尔值的代码片。因为一个动作的上下文先决条件，会在每次规划者尝试增加这个动作到一个计划时，被从新计算，最小化需要这个校验的过程是很重要的。可能的优化包括，缓从之前的校验下存结果，并且查找那些在规划者之外定期计算的值。
规划者优化
必须对优化规划者的搜索多一些考虑。随着动作的数量，以及在动作上的先决条件的增长，规划一个计划的复杂性会增加。我们可以用一些在优化寻路导航上的策略来进攻这个问题。这些策略包括优化搜索算法[Higgins02b]，缓存之前搜索的结果，以及把计划的规划任务分解到多个更新帧里面。上下文先决条件也可以用来裁减搜索，用来减少无用的路径。
对GOAP的需求
随着每个新游戏发布，业界总是设置更高的AI行为。由于对于角色行为复杂性的期望变大我们需要继续看更多的结构化、正式化的方案来建立可伸缩，可维护，和可重用的决策系统。面向目标动作计划是这些方案中的一个。通过放手允许游戏在运行时去规划计划，我们要把关键的决定权交给那些最有利去做这个决定的人；那些角色他们自己。
欢迎关注我的公众号：“韩大”（handa1740168）和我直接交流。
参考文献
[AIPS02] AIPS’02, Conferenceon AI Planning & Scheduling, informationabout AIPS
2002 available online at www.laas.fr/aips/, 2002.
[Fu03] Fu, Dan, Houlette, Ryan, “The Ultimate Guide to FSMs inGames,” AI Game
Programming Wisdom 2, CharlesRiver Media, 2003.
[Higgins02a] Higgins, Dan, “Generic A* Pathfinding,” AI Game Programming Wisdom,
Charles River Media, 2002.
[Higgins02b] Higgins, Dan, “How to Achieve Lightning-Fast A*,” AI Game
Programming Wisdom, CharlesRiver Media, 2002.
[IPC02] 2002 IPC, InternationalPlanning Competition, information aboutIPC 2002
available online at www.dur.ac.uk/d.p.long/competition.html, 2002.
[McDermott98] McDermott, Drew, Planning Domain Description Language,
information about PDDL2.1 available online at
www.dur.ac.uk/d.p.long/IPC/pddl.html, 1998.
[Monolith02] No One LivesForever 2: A Spy in H.A.R.M.’s Way, Monolith
Productions/Sierra Entertainment, Inc., 2002. Toolkit and SDKavailable at
nolf2.sierra.com/.
[Nilsson98] Nilsson, Nils J., Artificial Intelligence: A New Synthesis, Morgan Kaufmann,
1998.
[Russell95] Russell, Stuart, Norvig, Peter, Artificial Intelligence: A Modern Approach,
Prentice-Hall, Inc., 1995.