— AI分享站

第一部分见这里

模式3:根据条件跳转到多个状态,包括自跳转

这是在状态机里最常见的模式,由于是基于条件的跳转,所以可以非常方便的用选择节点和前提的组合来描述,特别值得注意的是,对于自跳转而言,其实就是维持了当前的状态,所以,在构建行为树的时候,我们不需要特别考虑自跳转的转换。如下图所描述了,我们先用序列节点来保证跳转的上下文(可以参考模式2中的相关内容),这里用到的另一个技巧是,我们会在状态a结束的时候,在黑板中记录其结束的原因,以供后续的选择节点来选择。另外,我们在第二层选择节点第一次用到了非优先级的选择节点,和带优先级的选择节点不同,它每次都会从上一次所能运行的节点来运行,而不是每次都从头开始选择。

Fsm2BtPattern3

当然,和模式2类似的是,我们也可以不用序列节点,而是单纯的用选择节点,这样的话,作为默认状态的状态a就需要处在选择节点的最后一个,因为仅当所有跳转条件都不满足的时候,我们才会维持在当前的状态。如上图的下面那颗行为树那样。请仔细查看,我在前三个节点对于前提的定义,除了本身的跳转条件外,还加上了一个额外的条件,InAXState,它保证了仅在上一次运行的是A状态或自身的时候,我们才会运行当前的节点,这样就保证了和原本状态机描述是一致的。

模式4:循环跳转

在状态机中存在这样一种模式,在状态a中,根据某条件1,会跳转到状态b中,而在状态b的时候,又会根据某条件2,跳转到状态a,产生了这样一个跳转的“环”。显而易见的是,行为树是一种树形结构,而带环的状态机是一种图的结构,所以对于这种情况,我想了下,觉得需要引入一种新的选择节点,我称之为动态优先级选择节点(Dynamic Priority Selector),这种选择节点的工作原理是,永远把当前运行的节点作为最低优先级的节点来处理。如下图

Fsm2BtPattern4

当我们在节点a的时候,我们会先判断b的前提,当b的前提满足的时候,我们会运行节点b,下一帧再进来的时候,由于现在运行的是节点b,那它就是最低优先级的,所以,我们会先判断节点a的前提,满足的话,就运行节点a,不满足则继续运行节点b,依次类推。下面是我写的相关代码,可以给大家参考。

 1: void DynamicPrioritySelector::Test(const Blackboard& in) const
 2: {
 3:     bool hasRunningChild = IsValid(m_iCurrentRunningChildIndex);
 4:     int nextRunningChild = -1;
 5:     for(int i = 0; i < m_ChildNodes.Count(); ++i)
 6:     {
 7:         if(hasRunningChild &&
 8:            m_iCurrentRunningChildIndex == i)
 9:         {
 10:             continue;
 11:         }
 12:         else
 13:         {
 14:             if(m_ChildNodes[i]->Test(in))
 15:             {
 16:                 nextRunningChild = i;
 17:                 break;
 18:             }
 19:         }
 20:     }
 21:     if(IsValid(nextRunningChild))
 22:     {
 23:         m_iCurrentRunningChildIndex = nextRunningChild;
 24:     }
 25:     else
 26:     {
 27:         //最后测试当前运行的子节点
 28:         if(hasRunningChild)
 29:         {
 30:             if(!m_ChildNodes[m_iCurrentRunningChildIndex]->Test(in))
 31:             {
 32:                 m_iCurrentRunningChildIndex = -1;
 33:             }
 34:         }
 35:     }
 36:     return IsValid(m_iCurrentRunningChildIndex);
 37: }

总结

从上面4种模式的转化方式中,我们好像会有种感觉,用行为树的表达好像并没有状态机的表述清晰,显的比较复杂,罗嗦。这主要是因为我们用行为树对状态机做了直接的转化,并想要尽力的去维持状态机的语义的缘故。其实,在AI设计过程中,一般来说,我们并不是先有状态机,再去转化成行为树的,当我们选择用行为树的时候,我们就要充分的理解控制节点,前提,节点等概念,并试着用行为树的逻辑方式去思考和设计。

不过,有时,我们也许想用行为树改造一个已有的状态机系统,那这时就可以用我上面提到的这些模式来尝试着去转换,当然在实际转换的过程中,我的建议是,先理清并列出每一个状态跳转的条件,查看哪些是带上下文的跳转,哪些是不带上下文的跳转,哪些是单纯的序列跳转(比如,从状态A,到状态B,到状态C,类似这样的单线跳转,常见于流程控制中),哪些跳转是可以合并的等等,然后再用行为树的控制节点,把这些状态都串联起来,当发现有些跳转用已有的控制节点不能很好的描述的时候,可以像我上面那样,添加新的控制节点。

这四种模式,是我现在能想到的,可能不全,如果大家有问题,可以在后面留言,有指教的也欢迎一起讨论。

————————————————————————
作者:Finney
Blog:AI分享站(http://www.aisharing.com/)
Email:finneytang@gmail.com
本文欢迎转载和引用,请保留本说明并注明出处
————————————————————————

Read More

选这次主题,要感谢一位网友的来信,他询问了一些如何将有限状态机转成行为树的问题,当时,我回信给了一些建议,但后来我仔细想了一下,觉得可能说得还不够全面,所以我就想通过这篇文章,来整理出一些比较典型的转化“模板”,给有这方面疑惑的朋友一些帮助,如果有朋友有一些自己的见解的,可以在后面留言,我们一起讨论。

有限状态机维护了一张图,图的节点是一个个的状态,节点和节点的连线是状态间根据一定的规则做的状态转换,每一个状态内的逻辑都可以简要描述为:

如果满足条件1,则跳转到状态1
如果满足条件2,则跳转到状态2
...
否则,不做跳转,维持当前状态

稍作整理的话,我们可以对状态机的几种跳转的情况一一描述出来,然后看看如果将这些情况用行为树来表示的话,可以怎么做。这就是我前面说的“转化模板”,当然我不能保证我下面列出的是状态机的所有可能情况,如果大家在实践中发现还有其他的情况,欢迎留言,我随时更新。

在这之前,我们可以先回忆一些关于行为树的一些概念(可以参考12

  • 控制节点:选择节点,序列节点,并行节点,等等
  • 行为节点:两种运行状态,“运行中”和“完成”
  • 前提条件

模式1:当处在任何状态中,一旦某条件满足,即跳转到某个特定的状态。

比如,在状态机中的一些错误处理,经常会用到上面的这种模式,当状态在运行过程中,发生了某些异常,那一般,我们会把状态机跳转到某个异常状态。这种情况,我们可以用到带优先级的选择节点(Priority Selector)方式,如下图,可以看到,我们把状态c作为行为树里的行为节点,跳转条件(Condition1)作为这个节点的前提(Precondition)。

Fsm2BtPattern1

再用上面举到的错误处理的例子,在状态机中,我们一般会这样写:

 1: STATE A::Update()
 2: {
 3:     ...
 4:     if(error)
 5:     {
 6:         return TO_ERROR_STATE();
 7:     }
 8:     ...
 9:     return UNCHANGED_STATE();
 10: }

转换到行为树中,我们会通过外部的黑板来做通信(可以参考这里),在行为节点a中,我们会这样写

 1: EXECUTE_STATE A::Execute(BlackBoard& out)
 2: {
 3:     ...
 4:     if(error)
 5:     {
 6:         out.error = error;
 7:         return EXECUTE_STATE_FINISH;
 8:     }
 9:     ...
 10:     return EXECUTE_STATE_RUNNING;
 11: }

然后对于节点c的前提里,我们来读取黑板里的error值

 1: bool Condition1::IsTrue(const BlackBoard& in) const
 2: {
 3:     return in.error == true;
 4: }

模式2:对于同一个跳转条件,处在不同的状态会有不同的跳转

比如,我们有两个状态,a和b,他们都对同一个跳转条件作出响应,但和模式1不同的是,a对跳转到状态c,而b会跳转到状态d,换句话说,这是一种带有上下文的状态跳转方式。对于这种情况,可以用到序列节点的相关特性,如下图

Fsm2BtPattern2

序列节点中,当前一个节点运行完成后,会执行下一个节点,利用此特性,在上图中可以看到,我们在a中,当满足条件Condition1的时候,则返回“完成”,那行为树就会自动跳转到c节点中,参考代码如下:

 1: EXECUTE_STATE A::Execute(BlackBoard& out)
 2: {
 3:     ...
 4:     if(condition1 == true)
 5:     {
 6:         return EXECUTE_STATE_FINISH;
 7:     }
 8:     ...
 9:     return EXECUTE_STATE_RUNNING;
 10: }

对于这种模式的另一种转化,可以不用序列节点,还是用到选择和前提的组合,但我们在前提中加上一个当前状态的附加条件,如下图

Fsm2BtPattern2 (1)

在第二层的前提中,我们可以这样写

 1: bool InACState::IsTrue(const BlackBoard& in)
 2: {
 3:     return in.current_running_node = A::GetID() ||
 4:            in.current_running_node = C::GetID();
 5: }
 6:
 7: bool InBDState::IsTrue(const BlackBoard& in)
 8: {
 9:     return in.current_running_node = B::GetID() ||
 10:            in.current_running_node = D::GetID();
 11: }

这样对于c的前提就是Condition1和InACState的“与”(回想一下前提的相关内容)。由于我们保留了上下文的信息,所以通过对于前提的组合,我们就转化了这种模式的状态机。

(待续…)

————————————————————————
作者:Finney
Blog:AI分享站(http://www.aisharing.com/)
Email:finneytang@gmail.com
本文欢迎转载和引用,请保留本说明并注明出处
————————————————————————

Read More

LOD(Level Of Detail)是3D渲染中用到的概念,按照wikipedia上的翻译,可以译为“细节层次”,它是一种根据与观察点的距离,来减低物体或者模型的复杂度来提升渲染效率的优化技术,因为显而易见的是,当一个物体离我们很远的时候,我们不需要用很复杂的多边形来绘制,只要用一个粗略模型或者低精度的贴图即可,所以在3D渲染中,这是一个很常见的优化技术。

对于AI来说,当一个AI对象离我们很远的时候,其实,它做出什么样的决策,做出什么样的行为,我们并不能“感觉的”到,虽然它的行为可能会对游戏世界有影响,但玩家一般只会专注于离自己比较近的AI行为,所以我们在AI的优化中,也可以采用这种“LOD”的技术,来提升AI部分的运行效率。

我在玩真三国无双的时候,对此非常有感触,虽然我并不知道他是否在AI层做了LOD,但类似于这种大场景,超多NPC的游戏,AI层的LOD的优化技术就非常适合。同样的NPC,当他离玩家不同的距离的时候,我们就可以赋予它不同的AI行为,如下表所示:

  1. 近:攻击,防御,追踪,掩护,包围,等待,...
  2. 中:追踪,包围,等待,...
  3. 远:等待,...
一般来说,AI候选的行为越多,它决策所花费的时间也越多,根据这样的假设,我们就可以通过限制AI行为的方式,来起到提升效率的作用。上面说的是一种LOD的方式,还有一种实现方式是减少AI的决策频率,这也是我以前讨论过的AI中的懒惰问题,比如如下表:
 
  1. 近:攻击,防御,追踪,掩护,包围,等待,...(0.1秒决策一次)
  2. 中:攻击,防御,追踪,掩护,包围,等待,...(1秒决策一次)
  3. 远:攻击,防御,追踪,掩护,包围,等待,...(5秒决策一次)

我们可以根据需要来混合使用上面两种方式。说到这里,我想大家脑海中会有一个自己的代码实现框架,我也想了一种,可以用到我经常说的行为树的方式来实现,行为树最好的就是可以任意的添加行为分支,所以可以说,对于第一种的LOD实现是天生支持的,我们只要建立三个行为分支表示近,中,远,并且在这三个分支下,挂上不同的候选行为,这样,我们就建立了一棵带LOD优化功能的行为树,如下图:

 
Lod1
 
对于第二种LOD实现,我们可以创建一种新的控制节点(回忆一下控制节点的概念),可以称之为LazyNode,这是一个一元的节点,它的功能就是维护一个时钟,当时间一到就执行它的子节点。同样的,我们用LazyNode,也建立近,中,远三个行为分支,然后在下面挂上相关的行为子节点,如下图:
 
Lod1 (1)
可以看到,如果我们用行为树,就不需要用什么附加的模块来做LOD优化,而是用行为树强大的扩展能力把这些直接整合进了AI结构中,这种不破坏结构,从架构层面的优化方式,是我相当推崇的。
LOD是一种懒人化的优化方式,无论是概念还是实现都非常简单,当然,所有这些都是以不破坏游戏性为前提的,有时,我们有可能需要远处的AI做一些复杂的决策,比如,在即时战略游戏中,虽然我们AI离我们很远,但它确实需要做一些完整决策,在这种情况下,LOD可能并不是很适用,所以,AI中的一些问题没有一成不变的解决方案,实际情况,实际分析是相当之重要的 :) ,大家对AI优化有什么心得呢,欢迎大家留言讨论。
 
 
————————————————————————
作者:Finney
Blog:AI分享站(http://www.aisharing.com/)
Email:finneytang@gmail.com
本文欢迎转载和引用,请保留本说明并注明出处
————————————————————————
Read More

游戏AI在做决策的时候,最重要的参考依据就是当前游戏世界信息,这其实和人做判断的时候是一样的,我们在做出一个决定的时候,脑中会闪过很多我们已经收集的信息,包括所见,所听,直觉(基于以往的经验)等等。所以,我们如何去抽象游戏世界信息,并收集起来以供AI使用,也是非常值得我们去思考和探讨的问题。

当然,不同的AI决策,对于游戏世界的信息需求是完全不同的,不同的游戏,对于游戏世界的抽象方式也不完全相同,因此,关于游戏信息收集的实现是一种“游戏特定”(Game specific)的问题。说句题外话,正是由于AI中充满了很多“游戏特定”的问题,所以AI不像渲染,声音,网络等其他游戏模块,它很难做成一个“引擎”,不过也正是因为每个游戏的AI需求都不同,因此AI编程也充满了魅力和创造力 :)

虽然存在这样或者那样的不同,但就像我一开始分析的,无论是否存在一个单独的模块来收集并存储游戏世界信息,这确实是AI程序中必不可少的单元。这次我想和大家探讨一个我一直在考虑的想法,虽然在我做过的项目中还没有完全用到(零星的用到一点,没有抽象成单独的模块),不过作为一个思维笔记记下来,还是很有必要的。

假设我们写一个篮球游戏中控球队员的AI,如果我们不考虑复杂的战术配合,一般来说,控球队员要么带球突破,要么直接投篮,要么传球给会造成威胁的空位球员,考虑到篮球场上瞬息万变情况来,如果单纯的if-else,会很难罗列出全部的条件,所以我们可能会采用模糊AI的决策逻辑,比如分数系统,不过,由于今天我们讨论的是收集和存储游戏世界信息的问题,所以对于AI决策相关的东西,我们暂且不讨论。我们仅仅来看,在这个问题中,AI决策时候可能需要知道哪些游戏世界信息:

  1. 场上己方球员的分布
  2. 场上对方球员的分布
  3. 球场上哪里比较有威胁(靠近篮筐的地方)
  4. 球场上哪里比较不安全(比如有强力防守队员,或者防守队员人数很多)
  5. 场地的构成(三分线位置,三秒区)
  6. 球员的相关信息(比如球员能力,位置,当前行为等等)
  7. ……

如果把上面的信息分个类别的话,可以分成以下4种

  • 静态实体信息(比如5)
  • 静态抽象信息(比如3)
  • 动态实体信息(比如1,6)
  • 动态抽象信息(比如4)

静态和动态的概念比较好理解,“静态”就是值不随着游戏的进行而变化的信息,“动态”就是随着游戏的进行会一直改变的信息,像场地信息就是静态的,不会改变的,像场上对方球员分布就是属于动态信息,因为他们的位置是一直变动的。而我这边提到的“实体”信息,指的是“真是存在”的信息,“抽象”是指“自定义”的参考信息。像场地信息,就是实体信息,因为类似三分线位置都是实际存在的信息,但像球场上哪里有威胁,那就是我们根据需要,自己定义的信息了,可以不断的调整和修正。

我借鉴了3D渲染中“帧缓冲区”(Frame Buffer)的概念,想用一种类似的方式来存储游戏世界信息,因为我们看到上面我们需要收集的信息中,不管是静态还是动态,实体还是抽象,很多都是和游戏地图相关的(除了6),所以我们就可以用一种“图”的方式来存储信息,称之为“游戏信息图”(Game World Info Map)。

首先我们按需求将游戏地图栅格化,比10×10,当然,粒度的大小取决于对于精度和效率的平衡。每一个格子就相当于“帧缓冲区”中的像素,然后我们可以创建多个这样的“图”,和创建多个“帧缓冲区”一样。每个图都代表上述信息中的一项内容,图中的每个格子都根据信息的内容填入0.0 ~1.0的值。

例如,我们要建立一个“场地威胁图”,我们定义0表示完全没有危险,1表示薄雾浓云愁永昼威胁值最高,那我们就可以这张图的相应的格子中填入相应的值,而且因为这是静态信息,所以只需要在游戏开始时填入就可以了,当我们填完每一个格子的时候,我们就得到了这样一张“场地威胁图”。对于动态信息的情况,我们需要在每一帧(或者每几帧)对“图”中的信息做一次更新,比如“场地危险图”,就是这样的动态“信息图”,需要根据防守队员的情况来实时更新。这样当我们填完所有的“图”信息后,AI决策时就可以知道任意时刻,在地图上的任意点上的相关信息了。

小地图的情况(如上例)可以直接做栅格化,但对于地图比较大的情况,如果直接栅格化的话,更新起来性能太低,这种情况可以考虑采用层次化的图模型,先将地图分成大块的格子,在大的格子里再细分成小格子,当查看距离近的信息的,采用精细的格子信息,查看远处的时候,采用粗略的信息,这样就可以在效率上取得一些平衡。

用“图”来表示世界信息的另一个好处是,可以方便的将信息绘制出来(在地图上,或者在外部的调试工具中),而不用面对一大堆的数据,如果再将不同的值配以不同的颜色来显示的话,那将大大的降低AI调试的难度。

可以看到,其实“图”的概念,就是对于游戏世界信息中和地图有关的信息的抽象,像我前段时间提到的“势力图”(Influence Map),就是“信息图”的一种应用。“信息图”的想法并不是我的独创,其实可能大家或多或少以前在编写游戏AI的时候也用到过,但我觉得整理一下的话,可以作为一种比较通用的结构来提炼出来,在AI中加以运用。希望对大家有所帮助。

————————————————————————
作者:Finney
Blog:AI分享站(http://www.aisharing.com/)
Email:finneytang@gmail.com
本文欢迎转载和引用,请保留本说明并注明出处
————————————————————————

Read More

前段时间,谈到了一种层次化的AI架构,通过“请求”来隔离出“决策层”和“行为层”,这种架构的核心是通过“请求”来起到承上启下的作用,并由此得出当前AI所应当有的行为,所以可以称之为“请求导向(Request-Oriented)”的结构。这种结构比较适用于需要频繁做AI决策的游戏场合,比如体育类游戏等,一旦变换了请求之后,行为层就可以迅速的找到相应的行为来完成请求的内容。

这次我们换一种思路,来讨论一种“目标导向(Goal-Oriented)”的AI结构,这种结构对于一些持续性相对较长的AI策略来说,是非常适用的。还是先举个例子吧,我平时很喜欢玩星际(没玩过的同学,可以看我下面的描述),那假设我用单个农民(SCV)造一个人族的重工厂(Factory),造重工厂的前提是需要200水晶(Mineral)资源,100气体(Gas)资源,而且必须要先造好兵营(Barrack),兵营是150水晶资源,还有在采集气体资源前,需要造一个气矿(Refinery),气矿也需要100水晶资源,具体流程图如下:

GoalOrientedExample

在这个流程里,我们为这个农民设定的“目标”就是“造一个重工厂”,由于在游戏中,要完成这个目标前,需要有其他一系列的预备行为,如果我们为这个农民写AI的话,它就需要根据上面的流程一步步的来完成我们要求它的“造一个重工厂”的目标。由于所有的AI行为决策都是由指定的目标引起的,所以我们把它称之为“目标导向(Goal-Oriented)”的AI架构。

由上面的例子我们可以看到,一个目标之后,必然会有一系列的行为与之对应,而这些行为就是为了最终完成这个目标,那这些行为是如何串联的呢?或者说,我们如何来做这样的行为计划呢?在“目标导向(Goal-Oriented)”的AI架构中,一般都会存在一个称之为“计划器(Planner)”的模块,由这个模块负责生成这样的行为序列,计划器有两种工作方式,一种是静态的,一种是动态的。

静态的计划器是在游戏设计时,对于所有已定义的可用目标,预先设计好计划流程,就像我们上面这个例子,我们就对“造一个重工厂”这个目标预先设计了一套计划流程,当游戏中的农民收到这个目标后,就会按照我们定义的这个流程来做。

动态的计划器是在游戏运行时,实时的根据目标来计划行为,因为我们看到,计划中每一个单步的行为都存在“前提(Precondition)”和“效果(Effect)”两个部分,“前提”就是做这个行为需要满足的条件,“效果”就是这个行为对于游戏世界的影响。还是用上面这个例子,像“造兵营”这个行为,它的前提就是“需要有150水晶资源”,它的效果就是“当前存在一个兵营”,再如“造重工厂”,它的前提就是“需要200水晶资源”,“需要100气体资源”,“当前存在一个兵营”,它的效果就是“当前存在一个重工厂”,可以看到,前一个行为的效果会成为了下一个行为的前提,所以有了这样的定义,我们就可以通过一些算法,来把可用的行为串联起来,形成一个计划,这样最后一个行为的效果,就是我们所定义的目标。

除了核心的计划器模块,我们还需要目标选择(Goal Selector)模块,来选择我们当前要完成的目标(相当于更高层的决策层),还有一个就是计划实施(Plan Stepper)模块(相当于行为层),用来按部就班的完成计划中各个行为,这两个模块比较好理解,就不多说了,有了上面几个部分的定义,我就可以画出这样的“目标导向(Goal-Oriented)”的AI架构图:

GoalOrientedArchitecture

由上图可以看到这种架构也是相当清晰的,核心的计划器部分在具体实现的时候,还有各种各样值得讨论的地方,本文作为抛砖引玉的作用就不多提了,以后可以继续讨论。现在的游戏AI中,这种Goal-Planner架构的也占了相当大的比例,在动态的计划器的驱动下,可以呈现出多样和逼真的AI行为,希望这篇文章对大家了解这种架构起到一些帮助。

————————————————————————
作者:Finney
Blog:AI分享站(http://www.aisharing.com/)
Email:finneytang@gmail.com
本文欢迎转载和引用,请保留本说明并注明出处
————————————————————————

Read More

游戏AI和游戏设计紧密相关,我也经常说,一个好的游戏AI,不在于算法的艰深和行为的完全拟真,而在于和整体游戏性的契合,在平时工作中,也是和游戏设计师打交道的最多,有这样一句话,一个好的AI程序员相当于半个游戏设计师 :) ,所以这次就来谈谈关于AI难度的设计问题。

谈到游戏设计,有些人觉得可能是灵光乍现的东西,只可意会不可言传,我以前也是这么认为的,但去年以AI程序员身份参加了一个为期两周的设计培训课程,感到收获颇丰,原来游戏设计通过总结前人对于游戏设计的实践,是可以形成一系列科学有效的方法的,好的游戏都有一些共性在里面,所以像《愤怒的小鸟》,《植物大战僵尸》这种游戏的成功,也绝不是偶然的。虽然在分工上,设计大部分都是游戏设计师的职责,但作为AI程序员,有时需要给出一些技术上的建议,并能提供一些技术上的支持。这次提到的关于AI难度的设计,也是我最近遇到的一个问题,我想如果运用一些科学的方法,就可以在设计时明确AI的方向和做法,这样对开发是有相当的益处的。

先假设一个场景,如下图所示(P代表玩家,E代表敌人,黑色的块代表障碍,黄色的圈代表目标),这是一个潜行类的游戏,游戏目的是控制游戏内的主人公拿到敌人基地内的情报图,而敌人会在基地内不停的巡逻,如果被发现就会Game Over。假设我们要做成关卡类的游戏,每一关都会比前一关难一点,关卡中的AI行为也要有难易之分。那作为AI程序员,自然就要去思考如何来AI的难度变化,来符合游戏设计人员的需要。

DifficultyOfAIs

当我们设计敌人的AI的时候,会先考察有多少因素会影响到敌人的AI难度,这些因素也是我们可以提供给关卡设计师的,值得说明的是,我们只考量AI层面的难度,不考察由关卡本身带来的难度,因为显而易见的一些因素,诸如敌人数量,敌人出生位置,障碍的位置等等,也是可以增加或者减少关卡难度的,虽然说我们在这里不考虑这些因素,但这些因素也是可以用我接下去的设计方法来设计的。

好,继续我们的AI难度设计,我们仔细分析问题之后,会列出如下可能影响到AI难度的因素

  • 巡逻方式:静止的,可预判的,不可预判的
  • 巡逻范围(用巡逻路线长度衡量):0,4米,8米,12米,无穷
  • 视野角度:0度,30度,60度,90度,120度,360度
  • 视野范围:0米,1米,3米,5米,7米,无穷
  • 移动速度:0米/秒,2米/秒,4米/秒,6米/秒,10米/秒
  • 声音感知范围:0米,1米,3米,5米,无穷

上面的这些因素后面的取值,都是由简单至难依次递增的,特别值得注意的一点是,每一个因素的第一个值都是最简单的情况,可以称之为“空值”,最后一个值是最不可能的情况,一般称之为“无穷值”,在空值和无穷值之间的值,是根据需求,按经验定义的,一般情况下(除巡逻方式外),我们不会取空值和无穷值。就拿“视野角度”这个因素来说,它的空值就是0度,表示这个敌人没有视野,它的无穷值是360度,表示这个敌人能看到周围所有的东西,在这之间的值都是比较合理的视野角度,可以任意取用。

有了这些因素,我们就可以用一张二维的表格来定义各种难度下的AI设置了,如下面这个表格

  巡逻方式 巡逻范围 视野角度 视野范围 移动速度 声音感知范围
AI1(新手) 静止 4米 30度 1米 2米/秒 1米
AI2(简单) 可预判 8米 60度 3米 2米/秒 1米
AI3(中等) 可预判 8米 90度 5米 4米/秒 3米
AI4(困难) 可预判 8米 120度 7米 6米/秒 3米
AI5(超神) 不可预判 12米 120度 7米 6米/秒 5米

这里我们通过设置不同的因素值,定义出了5种难度的AI设置,当把这些AI放入关卡中后,就会对关卡的难度产生影响,也帮助了关卡设计师来更好的设计和调整关卡的难度。

当然,作为AI程序员,可能我们并不需要参与到最后的关卡难度设计,但这样的设计方式,我觉得,是值得我们学习的,也可以帮助我们在实现AI的过程中,辅助游戏设计师,定义出可控的参数来,做到参数化的AI控制。我在现在的项目中,经常听到玩家的一些抱怨,什么AI太难啦,AI太简单啦什么的,而且有时游戏测试人员也需要一种“傻AI”模式来帮助他们测试,所以,如果我们能在实现AI初期,就把一些能够控制AI难度的因素定义出来,那也可以更好的来使我们的AI行为更可控,何乐而不为呢?

————————————————————————
作者:Finney
Blog:AI分享站(http://www.aisharing.com/)
Email:finneytang@gmail.com
本文欢迎转载和引用,请保留本说明并注明出处
————————————————————————

Read More

最近和一个同事讨论状态机的问题,记录一下。

我们知道状态机是AI(当然,不光是AI了)中常用的一种架构,有很多中实现方式,总体来说对于表达简单逻辑,还是很有帮助的,而且实现简单,甚至用一个switch-case就可以了,但在实践中状态机有一个致命的缺点,当状态一旦多了之后,它的跳转就会变的不可维护,假设有n个状态的话,那我们就需要维护最多n*n的跳转链接(因为状态机允许自己跳转自己),而且对于当前处在的状态而言,我不能知道我的跳转历史,也就是说,我很难知道为什么我会在这个状态里。这也就是为什么行为树现在成为相对主流的AI架构的原因。下图就演示了多状态间的跳转链接,对于AI程序员来说是非常头疼的。

shit-fsm

所以一般而言,除非是只有两三个状态的简单状态机,如果想要用状态机作为AI整体架构的话,现在都会选择层次化状态机结构(HFSM),并在一定程度上规范状态机的跳转行为。据我所知,微软的著名游戏光环2(Halo2)里就用到了层次化状态机的结构。HFSM就是为了减少跳转链接而做出的努力,举个决策小狗行为的例子,我们对小狗定义了有很多行为,比如跑,吃饭,睡觉,咆哮,撒娇,摇尾巴等等,如果每个行为都是一个状态,用常规状态机的话,我们就需要在这些状态间定义跳转,比如在“跑”的状态下,如果累了,那就跳转到“睡觉”状态,再如,在“撒娇”的状态下,如果感到有威胁,那就跳转到“咆哮”的状态等等,我们会考量每一个状态间的关系,定义所有的跳转链接,建立这样一个状态机。如果用层次化的状态机的话,我们就先会把这些行为“分类”,把几个小状态归并到一个状态里,然后再定义高层状态和高层状态中内部小状态的跳转链接,可能这样说有点晕,还是看图吧

hfsm

从上图可以看到,其实层次化状态机从某种程度上,就是限制了状态机的跳转,而且状态内的状态是不需要关心外部状态的跳转的,这样也做到了无关状态间的隔离,比如对于小狗来说,我们可以把小狗的状态先定义为疲劳,开心,愤怒,然后这些状态里再定义小状态,比如在开心的状态中,有撒桥,摇尾巴等小状态,这样我们在外部只需要关心三个状态的跳转(疲劳,开心,愤怒),在每个状态的内部只需要关心自己的小状态的跳转就可以了。这样就大大的降低了状态机的复杂度,另外,如果觉得两层的状态机还是状态太多的话,可以定义更多的状态层次以降低跳转链接数。

说回到和同事讨论的事情,当然同事的需求并不是用在AI中,是为了处理UI和网络异步请求的问题,我们知道,在网络游戏的UI中,经常需要给网络发送异步请求,然后得一些数据,正因为这些请求是异步的,所以需要在发送后等待网络返回结果,当这些请求很多的时候,很容易在UI端产生混乱(所以,一般来说,在项目中UI的bug是最多的 :) ),所以他提出了一种结构来改善这样的问题,总结下来,其实就类似于这种AI中常用的这种层次化状态机的概念,不过针对他的需求,还增加了一个并行的概念,也就是在一个状态内部,可能有多个同时运行的状态机(因为有同时多个的网络异步请求),所以当收到一个跳转请求或者消息的时候,还需要决定是哪个状态机需要跳转。另外为了防止跳转混乱,我们还谈到给状态机加更多跳转限制,增加语义支持等等问题。

最后,对于状态机,列出一些小的tips作为总结,希望对大家有所帮助

  • 要为状态定义入口动作/出口动作
  • 要详细设计每一个状态,列出层次化状态结构
  • 针对具体问题,严格限制状态跳转的请求
  • 同一层次的状态数量不宜超过5个
  • 记录每一次的跳转历史,方便调试
  • 可能的话,最好使用编辑器来编辑状态机

————————————————————————
作者:Finney
Blog:AI分享站(http://www.aisharing.com/)
Email:finneytang@gmail.com
本文欢迎转载和引用,请保留本说明并注明出处
————————————————————————

Read More

前段日子,和以前大学的同窗们聚会,很多人都是好久未见,有些人也是难得从国外回来一次,大家相聊甚欢,说说近况如何云云。

正巧,有个人现在在美国某著名大学读PHD,而且主要研究的是人工智能相关,那我作为一个AI程序员,对她研究的东西自然也就要打听一番。聊了一点之后,发现学术的东西还真是学术,和我现在在做的非常的不同,不仅偏向于理论,而且门类非常的窄。虽然,这也是在我的预料之中的,虽然,我在游戏行业里对AI技术摸爬滚打了几年,但还是不得不感叹:此AI非彼AI。

游戏中用到的AI技术,不管从架构还是实现上,较之于学术上的AI研究来说,都是相当简单的东西了。当然,不是说游戏AI不追求前沿,这也是有原因的,首先游戏AI技术的发展,和其他游戏技术一样,也是依赖于硬件的发展,在红白机时代,受硬件所限很难处理复杂的AI逻辑,所以看以前的游戏,AI大多是简单的if-else逻辑,或者简单的脚本化的逻辑为主。随着游戏硬件的处理速度越来越快,AI才可以越来越多的用到一些稍稍复杂或者高级的技术。

其次就是游戏对于处理速度的要求是相当之追求的,如果一个60帧的游戏,那一帧的处理时间就是16毫秒左右,在这之中分给AI的时间一般也就是6~8毫秒(视具体要求和如何划分AI而定)。所以游戏的AI很难选用一些,虽然很强劲,但很费时的算法,而我们知道,学术上的一些人工智能的研究,它的一些算法是很费时间的,这也就导致了很多学术上的研究并不能直接给游戏AI所用。

还有,就是可控性和灵活性。人工智能的极致就是极度的拟真,让人感觉不出这个是由程序算出来的结果,对于学术研究来说,这个是他们所最求的目标,但游戏的AI不同,拟真只是一个方面,游戏的AI是为游戏服务的,拥有一个拟真的AI的游戏,并不一定是一个好玩的游戏。所以有时,游戏的AI会作假,会不断的根据设计的要求调整,所以,游戏AI技术一般是注重于模块化的,灵活的架构,而不是拟真的算法。就拿神经网络来说,20世纪40年代就提出了神经网络的基本概念和雏形,做为一种学习型的算法和结构,可以说非常吸引人。但直到现在,我还是很少看到游戏中用神经网络作为主要的AI架构的,归根结底,就是它并不符合我提到的可控性和灵活性的要求。作为一个游戏的AI架构来说,太难以掌控和调式了。在游戏中,我所看到的一些运用到神经网络的地方,还是在一些语音识别的处理上。当然,可能以后会有更多的发展和运用,但就我现在的感觉来说,游戏AI还是需要具备可控性和灵活性的特点。

当然,不少游戏AI技术,也是取自于从学术研究。比如现在很多游戏用到的HTN(Hierarchical task network),中文翻译应该叫“层次化的任务网络”,就是一种实时的做计划(Plan)的系统,类似的学术研究其实从20世纪70年代就开始了,现在经过各种发展,慢慢的也应用到了游戏中了,而且不管从性能,还是最后的效果来看,还是很不错的。随便说一句,类Planner的AI系统,这也是我将来会重点学习和研究的地方。

游戏AI和游戏中的3D技术很不一样,3D技术经常是能把一些最新的研究带入进来,呈现出极其真实的画面,但游戏AI,就像我前面所说的那样,一方面要考虑的计算量的问题,更重要的是,它是为游戏服务的,所以好的游戏AI可能被学院派所不屑(因为并没有艰深的理论和算法),但它确实常常能表现出极佳的游戏性,这不是正是我们做游戏的人来说,最追求的吗? :)

所以,此AI非彼AI,不过多接触和了解一些前沿的AI研究,对于拓宽思路还是很有益的,最后,推荐一本书,《人工智能的未来》,记得当初读的时候,是通宵读完的,而且兴奋的满脑子都是里面的字句。真是非常有意思的书,我想,大家看完也会有种豁然和不一样的感觉。

————————————————————————
作者:Finney
Blog:AI分享站(http://www.aisharing.com/)
Email:finneytang@gmail.com
本文欢迎转载和引用,请保留本说明并注明出处
————————————————————————

Read More

前置阅读推荐:1 2 3

一直在说AI可以分为决策层(Strategy Layer)和行为层(Behavior Layer),和行为层打交道最多的,就是动画了,说到动画,游戏引擎一般都会提供完整的底层的动画系统,包括如何转换数据,如何做动画Blend等等,但这些一般不属于AI程序员的工作范畴,所以不在这次的讨论范围内,我们这次说到的“动画的选择和控制”是相对比较高层的东西,在我的定义里是属于AI行为层的内容。

现在的游戏中,动画越来越多,也越来越复杂,据说FIFA里就用到了4000到5000个动画,所以如何来驱动和组织这些动画,就成了AI行为层需要考虑的问题。就拿足球游戏为例,比如决策层发出“射门”的请求,那行为层就要从几千个动画中决定播放哪个动画来完成这个请求。直观感觉上,这就是一个if-else的问题,但我们要做的,是要有一个好的AI架构来做这样的一个对于动画的选择和控制。

从上面的描述中,我们可以看到,其实行为层的决策问题,和决策层的决策问题是一样的(这也是为什么他们都属于AI的原因),只是输入和输出的不同。对于决策层而言,输入是游戏世界信息(Game World Info),输出是请求(Request),而对于行为层而言,输入是请求和游戏世界信息,输出是动画和动画的播放控制信息(Animation Info)。如下图所示:

StrategyLayerAndBehaviorLayer

对于单个动画来说,我们可以定义两个附加的信息来选择和控制动画

  • 动画的选择条件信息(Animation Condition)
  • 动画的运行时状态(Animation Running Info))

动画的选择条件信息定义了播放此动画的条件,举个例在来说,在足球游戏中,我们有一个倒挂金钩的动画,要播放这个动画,就需要定义一系列的条件,比如球要在一定的高度,人要背对球门等等,这些条件都是预先定义好的,是选择动画的一个依据。

动画的运行时状态定义了动画在播放时的所有相关信息,诸如当前放到哪一帧等等,我们都知道,动画数据中存的都是用关键帧(key-frame)信息,有时,AI程序员需要在动画的关键帧中添加一些自定义辅助信息,比如,假设我们想在某一帧之后就可以接下一个动画,那就可以在这一帧上打个标记来标识,再比如,我们想在身体某部位触到地面的时候发个声音,那也可以在动画中身体碰到地面的那一帧上打标记。再用前面那个倒挂金钩的例子,我们可能会在触球的那一帧上有个标记,在更新动画运行时状态的时候,我们就可以知道在这一帧,要把球踢出去了。所以,这些信息,都是需要被监控的,它会影响到游戏方方面面,不仅仅是给行为层来使用。

下面是示意图,可以看到动画运行时状态是可以在多动画间共享的,因为一般来说,同一时刻只会有一个动画在播放,如果会有多个动画的Blend,比如上下身分开的动画系统,可以仅关心需要关心的那个主要动画的运行状态。所以动画运行时状态也可以称为“当前动画运行时状态”。

AnimationAtomStructure

有了动画,有了动画选择的条件后,我们会发现,这和行为树(Behavior Tree)的结构很像,如果我们把动画看成行为树的节点(Node),把动画选择条件看成节点的前提(Precondition),那我们就可以用行为树来搭建这样一个“动画选择树”。用行为树还有一个好处是,由于控制节点的存在,所以对于一个请求,我们可以用序列节点,作出序列动画的能力,举个例子来说,我们有一个摔倒(Falling Down)的动画,然后后续想接不同的起身(Getup)动画来丰富行为,那用行为树的话,就可以很轻松的做到这点,看下图,我们用了一个序列节点和一个选择节点的组合。

SeqAnimation

对于动画运行信息呢,就比较自由,可以放在行为树中,也可以单独的做一个模块来更新。如果选择放在行为树中的话,可以在根节点使用并行控制节点(而不是一般的选择控制节点),然后左子树是更新动画运行信息,右子树是动画选择树,这样在更新的时候,就会又执行左子树(更新运行时状态),又执行右子树(根据新的请求选择动画),将动画运行时信息放在前面更新的原因是,我们在选择动画时,可能需要参考当前的动画运行状态,就像我们前面所说的那个接下一个动画的问题那样。所以一般推荐先更新动画信息,再选择新的动画。

如果想用行为树来做动画的选择和控制,最需要考虑的就是“叶节点的粒度问题”,如果叶节点是单个动画的话,对于动画量不大的游戏,还可以接受,但像我前面说的类似FIFA的这种有几千个动画的游戏,会导致行为树过于庞大,不好维护,所以,有时我们需要控制叶节点的粒度,比如,将叶节点针对一组动画(相关性很大的一些动画)等。

好,这次就聊这么多,如果大家有什么想法,可以直接留言在下面,我都会回复的 :)

————————————————————————
作者:Finney
Blog:AI分享站(http://www.aisharing.com/)
Email:finneytang@gmail.com
本文欢迎转载和引用,请保留本说明并注明出处
————————————————————————

Read More

我们在学习程序的时候,都会提到一些逻辑计算方面的事情,像与(and),或(or),非(not)等,在编程语言层面也提供了相关的符号来表述逻辑的计算。我们都知道,对于AI来说,逻辑是非常重要的,一些简单的AI系统,就是由if-else搭起来的一个庞大的逻辑网,里面包含了各种预设好的可能性,最后得到一个决策结果,这样的系统还有一个名字,叫基于规则的AI系统(Rule based AI System),当然随着游戏逻辑越来越复杂,这样简单的靠分支的系统已经不能满足要求了,所以出现了各种AI架构,像有限状态机(FSM),行为树(Behavior Tree),计划器(Planner)等等。但不管架构如何变化,我们在AI中还是充斥着各种逻辑的计算。

那为什么我们要用类来表示逻辑计算呢?这就要牵扯到我们一直在聊的行为树的问题了,我们知道行为树在每个节点上都需要一个称之“前提”(Precondition)的部分,用来帮助我们来决定此节点是否能被执行,所以这个“前提”就会包含一个逻辑表达式,要么返回False,要么返回True,对于不同的节点来说,它的“前提”基本上都不会相同,那自然的,我们就会从程序设计的角度来思考,如何去实现它。当然,方法有很多,不过如果从以下两个方面来考量的话,可以考虑用类的方式来做。

  1. 模块化(目的复用逻辑项)
  2. 为行为树的编辑器做准备(目的可视化的逻辑表达)

说到类的实现方式之前,我们可以先来看一下,一般代码中的逻辑表示,以c/c++为例:

 1: bool a = IsAOk();
 2: bool b = IsBOk();
 3: bool c = IsCOk();
 4: if(a && (b || c))
 5:     //do sth
 6: else
 7:     //do other things

这样的方式很直接,很简单,作为“前提”的实现也是很好的,比如我们可以提供这样一个类,然后让用户继承这个类,自己在isTrue的方法里写需要的逻辑计算。

 1: class Precondition
 2: {
 3: public:
 4:     virutal bool isTrue() const = 0;
 5: };

但考虑到我上面的两点需求,这样的实现就显得不够模块化,因为我们并不能复用上面的任何一个逻辑项,而且更重要的是,我们也没有办法在编辑器中“看到”它的逻辑表达。基于这样的原因,我们再来看看用如何用类来表示逻辑计算,还是用上面这个纯虚类,我们定义几个称之为类逻辑操作符的新类

  • PreconditionAND
  • PreconditionOR
  • PreconditionNOT
  • PreconditionXOR

这些类继承自上面的Precondition,并重写了isTrue方法,我们用PreconditionAND举例:

 1: class PreconditionAND : public Precondition
 2: {
 3: public:
 4:     PreconditionAND(Precondition* lhs, Precondition* rhs)
 5:         : m_Lhs(lhs),m_Rhs(rhs)
 6:     {}
 7:     virtual bool isTrue() const
 8:     {
 9:         return m_Lhs->isTrue() && m_Rhs->isTrue();
 10:     }
 11: protected:
 12:     Precondition* m_Lhs;
 13:     Precondition* m_Rhs;
 14: };

可以看到,这个类很简单,它接受两个Precondition的实例,然后在isTrue里再调用这两个实例的isTrue方法,并返回它们的And结果。对于其余的逻辑符号类,我们也用同样的方式来定义,值得注意的是,对于PreconditionNOT来说,它只接受一个Precondition的实例,因为Not是一元的操作符。

有了逻辑操作符,我们就可以复用Precondition的逻辑项了,比如

 1: Precondition* precon = new PreconditionNOT(
 2:                             new PreconditionAND(
 3:                                 new PreconditionA(), new PreconditionB()
 4:                             )
 5:                         );
 6: //ret means !(A && B)
 7: bool ret = precon->isTrue();

我们用类逻辑操作符链接了逻辑项,使之达到了复用和模块化的效果。对于这种方式,我们需要不断的整理和提炼,并预先定义一些我经常用到的一些单个的逻辑项,就像上面所示的A,B一样,然后通过类逻辑操作符,组合成我们需要的逻辑计算结果。对于这些单个的逻辑项,因为需要被复用的关系,所以要尽量保持内部的逻辑是简单的。

就我们想要的行为树编辑器来说,我们可以将这些预先定义好的单个逻辑项导出到编辑器,然后在编辑器里,我们通过类逻辑操作符,来组成出我们需要“前提”,这样,我们就可以在编辑器里直观的“看到”逻辑的表达式,也方便我们检查逻辑的正确性。

当然,这种方式比起第一种直接在代码中书写逻辑的方式,相对复杂,在开发过程中,team对于这种理念的坚持程度也有待验证(因为需要不断的优化逻辑表达式),但对于一种用类实现逻辑的方式,我觉得还是有必要在这里介绍一下。我在实践中,两种方式都用到过,各有利弊,对于极度追求模块化的设计理念,并且想做行为树的可视化编辑器的朋友来说,用类的方式还是非常值得一试的。

好,今天就聊到这里,希望对大家有所帮助。

————————————————————————
作者:Finney
Blog:AI分享站(http://www.aisharing.com/)
Email:finneytang@gmail.com
本文欢迎转载和引用,请保留本说明并注明出处
————————————————————————

Read More