Skip to content

Latest commit

 

History

History
151 lines (75 loc) · 25.9 KB

第七章游戏中的AI.md

File metadata and controls

151 lines (75 loc) · 25.9 KB

第七章 游戏中的AI

AI机器人在游戏中非常普遍,它们常以模仿人类的行为在游戏中活动。游戏中的怪物的自动行为比较普遍,这种简单的人工智能方式可以用几种不同的方式进行编写,主要的两种方式:一种为容易被人类思维接受的状态机,另一种是为机器人策略型思考方式编写的行为树。

状态机构架机器人行为

状态机虽然是个比较简单的概念,但在实际编程中花样也是繁多的,不过最终都是围绕着状态的概念来做的变化。状态机比较符合人类思考的方式,我们喜欢把事物的行为以状态形式进行拆分。以时间状态为基础的可以有,当前状态、前置状态、下一个状态、状态变化条件,其中每个状态都有自己定义,它们可以以行为方式拆分成,比如行走状态,休息状态,躺下状态,攻击状态,防守状态,三连击状态,俯冲状态,平移状态等。

人们习惯把人或动物的某些连贯的行为定义为状态,所以状态其实不只是一个动作,它可以是好几个动作,或者好几段位移,也就是好几段执行程序。这种好几个动作和好几段位移一起组成的组合,在程序中用状态来表示比较符合人类思考逻辑。每种状态下不只是一个动作或一种位移,而是由很多个动作多段位移组合而成。在游戏里,智能机器人由于都是人设计出来的,行为方式也需要符合人类的逻辑,因此用状态机的方式制作AI比较符合人类思维方式,也最容易被接受。

用状态机编写AI有诸多优点,诸如可维护性强,可扩展性强,逻辑耦合清晰,符合人类思维逻辑易上手。但缺点也很大,由于每个状态都必须由设计人亲自制定,因此在每个状态时编写时要考虑到所有情况,每种情况都要有相应的处理方式,这样就导致当需要设计的AI行为过于复杂的时候,编写的逻辑复杂度和工期长度也呈现指数级的增长,到最后有可能无法承受太复杂的AI行为逻辑,比如人类在战场中的随机应变能力,对于各种各样的爆炸,攻击,冲锋,防御的应变能力需要表现出各种不一样的行为方式时就会在状态机里出现很多 if 的情况,这时仍然用状态机来编写AI就会很容易陷入超出人类逻辑的复杂度。

用行为树构建AI

状态机也有很大的缺点,就是不能处理和模仿太复杂的智能行为,比如模拟一个人类奔赴一场大型战役中,对战场中的各种繁多的突发事件做出符合人类模式的处理,这种方式状态机就无能为力,由于突发情况太多,组合起来的突发情况更多,做出反应的方式也变化多端,用人类思维逻辑去编写每个状态,状态的数量就会如指数级攀升无法应付,不止人类大脑无法应付这么复杂的逻辑编写,这样复杂的逻辑也很难有效维护。

行为树很好的弥补了状态机的缺点,它简化了逻辑拼凑的方式,让脑容量有限的人类能更容易编写和控制机器人的智能行为。这也是AI架构的关键点,能够让人更加简单容易的制作复杂的人工智能的行为,可以说是‘化繁为简’。

‘化繁为简’是我们的大部分编程时的重点,尤其在AI设计上,人工智能的行为方式大都是由人类头脑指定的行为方式,是人类头脑所预期的行为。制作出人类所预期的AI行为逻辑,并且制作的方式和过程又在人类大脑的承受范围内的是我们所预期的。状态机的方式制作AI理论上可以实现任何AI,但复杂到一定程度人脑无法承受,其实就是低效的或者说低阶的AI。行为树的优势就在这里,能够通过一些简单的操作制作出达到人类所预期的足够复杂的机器人行为方式。

行为树的本质是树状节点,每个节点可以选择某种类型的功能节点,也可以选择某个叶子节点即没有子节点功能,功能节点以各种逻辑顺序来选择继续访问下面的子节点或者直接停止并返回结果给父节点,子节点的结果将给父节点作为参考以便继续运行相关逻辑,因此行为树本身就是一种树形的父子节点之间的逻辑结构,我们可以理解为节点逻辑,通过扩展节点的功能来实现复杂的行为逻辑。

行为树(Behavior Tree)具有如下的特性,它有4大类型的节点:

1,Composite Node 复合节点

复合节点可详细的分为3种:

一种是Selector Node,即选择节点,它的节点规则是当执行本类型节点时,它将从头到尾迭代执行自己的子节点,如果遇到一个子节点执行后返回True则停止迭代,本节点向自己的上层父节点也返回True,否则所有子节点都返回False,那么本节点才向自己的父节点返回False。

另一种是Sequence Node,即顺序节点,它的节点规则是当执行本类型节点时,它将从头到尾依次迭代执行自己的子节点,如果其中一个子节点执行后返回False那么就立即停止迭代,同时本节点向自己的父节点也返回False,相反如果所有子节点都返回True,则本节点就向自己的父节点返回True。

还有一种是Parallel Node,即并发节点,它的节点规则是并发执行它的所有子节点。并发节点又分为三种策略,这与它们向父节点返回的值和并行节点所采取的具体策略有关即如下:

Parallel Selector Node,即并行选择节点,它的节点规则为执行完所有子节点,如果有一个子节点返回False则自己向父节点返回False,只有当所有子节点全返回True时自己才向父节点返回True。

Parallel Sequence Node,即并行顺序节点,它的节点规则为执行完所有子节点,如果有一个子节点返回True则自己向父节点返回True,否则只有当全部子节点返回False时自己才向父节点返回False。

Parallel Hybird Node,即并行混合节点,它的节点规则为执行完所有子节点,按指定数量的节点返回True或False后才决定返回结果。

并行节点提供了并发性,由于它可以在线程或协程级别提供并发操作,所以在性能上面有能够充分利用CPU提高性能。通常情况下,Parallel Node下会并行挂多个Action子树,或者挂多个条件节点以提供实时性。并行节点增加性能和方便性的同时,也增加了维护的复杂度。

除此以外为了进一步提高AI的复杂度和随机性,Selector 和 Sequence可以进一步提供非线性迭代的加权随机变种。比如,Weight Random Selector 即随机权重选择节点,每次执行不同的起点,提供了每次执行不同的First True Child Node的可能。而Weight Random Sequence 即随机权重顺序节点,则每次执行顺序不同,以提供了不同的随机迭代顺序,能使AI避免总出现可预期的结果让结果更加的随机化。

2,Decorator Node 修饰节点

Decorator Node,即修饰节点,修饰节点的功能为将它的子节点执行后返回的结果值做额外修饰处理后再返回给它的父节点。

这里举几个修饰节点的例子便于读书者们理解,下面这些修饰节点都可以自定义创造出来,节点功能可以为五花八门,它们共同点为修饰子节点的结果,或者通过子节点的结果来运行逻辑。

	反向修饰 Decorator Not,它的节点功能为将结果反置后返回上级处理,即当子节点为True时返回给自己父节点的则为False,反之子节点返回False时自己返回给父节点为True。

	直到失败修饰 Decorator FailureUntil,它的节点功能为子节点运行在指定的次数到达前一直向上级返回失败,指定次数后一直向上级返回成功。

	总是失败修饰 Decorator Fail,它的节点功能为无论子节点返回的结果是否为True都向上级返回False。

	计数修饰 Decorator Counter,它的节点功能为只运行子节点n次,运行计数超过n次后不再运行。

	时间修饰 Decorator Time,它的节点功能为在指定时间内运行子节点后都返回True,超出这个时间范围无论子节点返回什么结果都向上级返回False。		

	甚至Decorator Nothing 它的功能就是什么都不干,用来提前占个位置为后面的功能预留。

除了以上这些我们还可以创造出来更多种类型的节点,例如用来调试的日志(log)节点,告知开发者当前节点的位置及相关信息,或者循环修饰节点,循环执行子节点n次等等,我们可以根据项目的需求来增加必要的修饰节点逻辑。

3,Condition Node 条件节点

Condition Node相对比较简单,条件满足则返回Ture,否则返回False。

各式各样的条件节点,都继承基础条件节点并且返回Ture或False。比较常用的条件节点例如,大于,小于,等于,与,或,判断True或False。由这些条件节点可以与变量组合成,判断血量的条件,距离判断的条件,状态判断的条件,时间间隔判断条件等,可以用于行为树AI中。

4,Action Node 行为节点

Action Node,通常都是最后的叶子节点,它完成具体的一次(或一小步)行为并视需求返回值。行为节点可以是执行一次得到的结果,也可以视为分步执行很多次的行为。例如向前行走这个行为可以一直被执行直到走出某个范围。

我们可以通过扩展行为节点让AI行为变得更为丰富多彩,行为节点也是自主定义角色行为的关键,它通常涉及角色行为的具体行为。常用的行为节点的例如,行走到目标地点的行为节点,追击目标的行为节点,使用物品的行为节点,撤退的行为节点,攻击目标的行为节点,防御动作的行为节点,释放某技能的行为节点等等。这些行为节点都可以根据我们项目的需要从基础的行为节点扩展而来的,行为节点是最丰富的节点库,大部分时间我们程序员也一直在修改和扩容行为节点以向AI行为提供更多丰富的可编辑行为内容。

在行为树中任何节点被执行后,必须向其上层的父节点报告执行结果:成功True或失败False或Running正在运行(还在执行并未执行完毕,例如行走到某目的地,角色行走正在途中),这简单的成功或失败或运行中的汇报原则被很巧妙地用于控制整棵树的决策方向。

整棵行为树中,只有条件节点和行为节点才能成为叶子节点,也只有叶子节点才是需要特别定制的节点,而复合节点和修饰节点均用于控制行为树中的决策走向,所以有些资料中也统称条件节点和行为节点为Behavior Node 即表现节点,而复合节点和修饰节点为Decider Node 即决策节点。

行为树能够支撑起对复杂逻辑的AI的原因就是由于我们可以使用这些简单的节点去搭建一个庞大的AI行为树(也可以说是一个AI模型)。我们程序员很容易的扩展节点来丰富AI节点库,无论是复合节点、修饰节点、条件节点、还是行为节点在扩展时都是相对容易的且有良好的耦合性的,这使得我们在壮大AI行为时节点的功能性扩展变得很容易,而拼装这些节点形成一个完整的AI行为就如同是一个搭积木的过程,人脑能搭建多复杂的积木就能搭建起多复杂的行为树AI。

决策树也是与行为树相似的AI解决方案。决策树和行为树一样都是树形结构叶都是由节点构成。在决策树中决策的构成是由树形结构的头部开始,从上往下一路判断下去决策该往哪走,最后一定会执行到叶子节点,进而确定当次行为的动作。在决策树中只有叶子节点才决定了如何行动,而且在决定后的行动中无法中途退出,必须等到当次行为执行完毕或者被打断后才能开始下一次决策。从理念上讲,决策树就是为了制定决策,而行为树是为了控制行为,它们是两个不同的理念。行为树更加注重变化,而决策树则更加注重选择。因此行为树可以定制比决策树更加复杂的AI逻辑,而实现的难易程度上比较行为树并没有增加多少。

行为树比状态机更容易编写复杂的AI逻辑很大程度上是得益于单个节点的易扩展性,状态机的每个状态的扩展难度相对比较难。从人们拼装节点组合的角度看,AI树的可搭建更加丰富多彩的AI行为,而且它的搭建行为需要的能力也都是在人脑的可及范围内,而状态机对于稍微复杂点的AI行为搭建则非常费力,不仅需要更多的硬编码支撑而且状态间的连线也容易让人陷入困惑。

不过再厉害的人脑在搭建行为树AI时也有极限的搭建复杂度,无论你对搭建行为树这项技能有多么熟练多么精通都有到一个极限的状态。当搭建的复杂度超出人类大脑的时候我们就会陷入混乱,或者说无法完成更加复杂的AI行为。例如如果想完全模拟人类的思维判断逻辑,对不同的人,对不同的事,对不同的景色,对不同的物体,不同的路面,以及以上混合组合的不同组合作出应对策略,就完全超出了人类大脑搭建的极限。像这种特别复杂,完全不能由人类大脑通过搭建的方式形成的AI,我们就需要引入‘机器学习’技术,它不再由人来制定行为方式而是通过对案例的学习,从而获得更多更复杂的环境应对方式。

非典型性AI

1,庄家式AI

顾名思义,是庄家统治游戏的一种玩法,玩法中AI就是全局的统治者,它决定了整个游戏的高潮和低谷,AI如何操作成为了至关重要的关键点,玩家是否喜欢这款游戏很大程度上取决于AI的策略。

这种类型游戏大部分以彩票或赌局的形式存在,比如老虎机,百家乐,21点,以及部分以彩票为形式的游戏。

AI策略的目的是要让玩家玩的好又不能赢太多而且最终是要输给AI的。玩家喜欢继续玩但从总体上来看却又是输的,让庄家就是游戏运行商有的赚,但又不能太狠,让游戏细水长流。

这种AI常以输赢的概率为基本控制手段,如果现阶段以玩家欢乐为主,那么胜的概率变得大一点,玩家会认为幸运女神眷顾他了,一段时间后为了让玩家遇到点困难,让玩家有挑战性,这时AI慢慢降低了赢的概率,玩家缓慢觉得赢的次数开始减少,有些玩家会以为幸运女神走了,需要靠自己的‘本事’玩下去了,他们不断得发现和寻找输赢的规律,以及出牌和翻牌的概率,直到输得所剩无几,然后AI开始了缓慢提高胜率的操作,让玩家又看到了希望,找到了自信,认为自己终于不费苦心找到了规律和破解的秘密,于是又开始了新一轮有输有赢但输多赢少的旅程。如此这般不断得循环往复,AI以一种庄家的形式控制着整个游戏过程。

从技术上来看,这种控制概率的过程,就是加法和减法的过程。其核心是给出一个概率后,如何让它真的起到概率的作用,而且这种概率能让人很舒适的接受,比如当有30%概率赢时能否做到真正的随机值在30%的概率上徘徊,比如10局中有2-4局能中玩家可以得到想要的那个点位或者想要的牌什么的,而不是10局中0-5局能赢,这样输赢实际结果波动到了不好的体验。

2,可演算式AI

可演算式的AI在策略类游戏中非常常见,在页游里的大部分的自动对战,以及现在卡牌手游中的大部分自动战斗都是可演算式的AI,是可以根据两边的阵容数据和一个随机种子来演算出整场战斗的每个细节的。例如,两个军队的各5个英雄,互相间攻击并释放技能,服务器需要在一瞬间把所有需要在客户端演示的内容都计算出来,并以数据的形式发送给客户端,客户端根据演算的数据进行展示人物的动作,位移,技能释放等,客户端并不需要计算任何内容,所有内容都在服务器里已经计算好了,以数据形式代表了整个过程。

可演算式AI的特点是逻辑一定是确定性的,不能是模糊的,或者会随机改变的,或者随时间变化而变化的结果,同样的数据第一次计算和多次计算的结果必须是相同的,才能最终体现出可演算的这个特征。其次,可演算式AI大都是根据时间轴来演化游戏的进程,在那里‘时间轴’的概念在可演算式AI中是比较常见的。

什么是时间轴演算路径?我们用卡牌对战算法来举几个例子。

首先最简单的时间轴演算路径,例如,先由敏捷度最高的英雄进攻,等待英雄进攻完毕后再由其次高敏捷度的英雄进攻,依次进行下去直到所有的英雄进攻完毕再重新一轮进攻。这种相对比较简单,可以把进攻看成一轮一轮的回合,每个回合都相当于是一次for循环,每次for循环前先对敏捷度进行排序,再在for循环中依次计算进攻了谁受到了多少伤害,以及是否死亡。最后把进攻的数据和伤害的数据用队列的形式存储在数据中发送给客户端,客户端受到数据后再进行演示。也可以不发送具体数据,而是只是发送随机数的种子,通过种子来产生与服务器一样的随机数,最后再通过使用同一套算法来达到校验的目的,即如果前端的计算结果和后端的计算结果一致则认为客户端的演算正确,这样就减少了很多数据传输的压力。

稍微复杂点的时间轴逻辑,例如游戏里的卡牌角色不再由敏捷度来决定进攻的先后次序了,而是由每个英雄的进攻间隔冷却时间来决定进攻次序,对战开始时开始计算每个英雄的进攻冷却时间是否结束,谁的冷却时间先结束谁就最先得到进攻权,进攻完毕后再等待下一个英雄的冷却时间,以此类推。从技术上讲,冷却时间不需要等待,把所有英雄加入一个队列,排序一下就可以得到谁的剩余冷却时间最短,就立马可以开始计算进攻细节,完毕后根据冷却时间插入到队列中去,任然还是一个有序的剩余冷却时间队列,一直这样计算下去直到演算结束一方胜利或失败。这种演算方式就有了更多了时间轴的概念。

我们再来看看更复杂的时间轴,前面所说的进攻逻辑都是在其他英雄都停止的状态下进行的,现在进攻时不再需要其他英雄等待了,一旦冷却时间结束就可以立刻进攻。也就是说,每个英雄都可以在其他英雄还在进攻时进行进攻操作,只要他的冷却时间到位,并且他的进攻是需要花费固定时间的,等到进攻完毕后再判断对方和自己是否死亡。这种方式,不只是多了一个进攻消耗时间这么简单了,还有死亡时间的判断。在还没有死亡判定前,此英雄虽然是即将死了但任然可以被进攻。从技术上来看,计算的量从单一的剩余时间量排序,增加了进攻消耗时间排序插入,以及死亡判定排序,我们既要在冷却时间结束时计算进攻,还要在选择进攻对象时计算该英雄是否已经判定死亡,最后在进攻完毕后计算当前的时间并插入到排序队列中。这样我们就需要将每个关键时间点都计算出来,并依次演算,由于前面的关键时间点有可能影响后面的角色AI的动作,导致我们不能演算太多的时间段,只能一步步来做AI演算。

再复杂点,英雄在进攻一半时可以被别的英雄打死,也可以被其他英雄的技能打断,也包括了随时被回复血量蓝量,增加状态等等,让战斗更加逼真、更具有实时性。加强了实时性的要求,更加考验可演算式AI的复杂度,由于太多的需要计算的时间内容,所以我们必须有一个能有效管理时间轴的方法。从技术上来看,我们必须定义‘时间节点’这个概念了。

‘时间节点’就是一个事件在整个过程的时间轴上的发生时的位置。

有了时间节点这个概念,我们可以用时间节点为计算标准,把所有人物的下一个事件的时间节点计算出来,比如,移动到达敌方位置,释放技能,回到原地,冷却时间结束,每个人只计算最近的一个时间节点,并把计算出来的结果放进队列中,然后就可以找出时间节点里离我们最近的一次事件的发生节点,也就是时间差最少的节点,执行它。

由于每个时间点都有可能引起其他时间点的变化,例如这个做东把对方打死了,对方的时间节点就消失了,又例如打断了别人技能释放,对方就回到了冷却队列,时间节点就需要重新计算了,又例如加速了友军的攻击速度,因此所有友军正在攻击或打算攻击的时间节点都要重新计算了等等等等,这些关键点的时间节点被前面的时间节点打断则需要重新计算。因此每次在执行完一个时间节点后,都要对有可能产生变化的人物的时间节点进行重新计算,并重新加入队列。这样经过重新计算后,我们可以再次找出离我们最近的一个时间节点了。如此往复的重复这个计算过程,直到没有任何时间节点可计算和执行,最终决出这张战斗的胜利或失败。

时间轴贯穿了整个AI过程,人物之间的打斗,移动,释放法术,冷却时间等待,AI每次只计算一个时间节点,因为只有最近的那个时间节点是一定不会被其他节点影响的,这样既照顾到了可演算的根本原则,也照顾到了游戏的实时性,让战斗更加精彩。最后我们可以把每个计算的结果都记录下来,这样可以随时在客户端进行演示,整个过程的事件发生的时间都将准确无误呈现出来。如果觉得这样传输数据太浪费网络资源,则可以使用我前面提到的,传输随机种子,然后通过两边一致的算法进行各自演算。

3,博弈式AI

游戏项目中大部分AI的目的都是以娱乐玩家为主,并没有要真正打败玩家,最多也是要与玩家达到一种平衡。而博弈式AI则不同,它的目标就是为了打败玩家,它是为了赢得比赛而生的。

博弈AI最大的特点是搜索。通过搜索将所有下一步可能发生的,以及下几步可能发生的事情都记录在内存中,以此来确定电脑该怎么进行下一步动作,进而获得最大的效益。

有人不理解为什么是搜索,在AI选择下一步的动作前,下一步要发生的情况有很多,我们需要选择最佳的那个。于是把所有下一步的情况都列出来,再把下一步的后几步的情况也列在下一步的下面,计算的步数太多CPU计算量太大的因此裁剪了后面的步数,假设我们只计算和预测五步的结果,我们需要找到第五步的最好结果,再反推到第一步来确定第一步到第五步是怎么走的。

既然我们要从第一步走到第五步,假设第一步有10多种情况,第一步到第五步都有10多种情况,每一步之间都有一个结果就相当于一点到另一个点的路径一样,从第一步到第五步就可以视为路径的一种,那么从第一个点到第五个点的最短路径,就是第一步到第五步的最佳结果。把视角一转换后发现事情变得的简单了,用最短路径算法就可以解决搜索问题。

不过事情远没有这么简单,这里只是举了个简单的例子,情况会复杂到每一步有几百种情况,普通的搜索方式计算机可能完全无法承受。为了能让计算机更快更有效的计算出结果,通常在搜索中我们都需要引入枝剪和优化,设定一些固定技巧,以及拒绝计算一些明显比较差的选择,以此来改进搜索算法的效率。

除了搜索我们还需要对每一步的结果进行估值。估值表示了当前局势的好坏程度,通常用一个0到100的浮点数来表示估值,估值的准确性是衡量AI的一个关键点,只有正确的计算出局势的估值,AI才能知道当前选择的行动方向它的效益是多少,是否达到了最大效益的目的。

我们拿五子棋来说,棋盘上的每一个点都是对手下一步的可能性,通常不会在空白处下一个完全不着边的棋,所以搜索范围缩减到了当前棋盘上有棋子的范围周围的空位。AI对所有这些空位录入到程序中并搜索下一步最佳摆放位置,当AI把棋子放入该位置上后,对方做出的反应后AI由此引发了后几步的对弈可能。我们假设AI只搜索和计算后5步的预测,也就是说,计算出来的当前落子的估值,就是所有棋盘中可落子的后5步内最优估值。

最后通过数据录入和训练增强AI的博弈能力。人类的手法很高明,欺骗性很强,很容易就能找到AI的盲点,所以录入人类的想法也是博弈AI的关键点。

96年97年的人机国际象棋大战就是录入了大量的棋局来告诉AI人类的一些固定走法,让AI在对弈中识别人类的套路。通过数据录入以达到对固定手法的判断,这样做的局限性比较大,无法应付快速更新换代的技巧和想法。为了做出更强大的博弈式AI,我们不得开始让AI拥有自学的能力,通过模仿人脑的神经系统网络,再用数据训练,让机器学习更加有效。它们原理就是数据训练+估值判定,给AI不断地喂数据的同时,告诉AI这个数据是对的还是错的,或者说估值能达到多少,通过不断的数据训练(俗称喂数据)的方式,让AI的神经网络系统像人脑那样形成链路,这样就拥有了丰富的‘经验’,进而在对弈中不断学习,每次对弈对AI来说既时竞赛同时也是学习。