游戏人工智能编程精粹(青少年人工智能编程水平测试)

 

前言

在很久很久之前的一个射击小项目上的怪物AI中使用了操控力的方式来实现怪物的各种行走行为等，主要知识点都是在书籍《游戏人工智能编程精粹》里面得来的，最近又准备了一个类似的射击项目，那么就打算总结一些这些东西，再次梳理一下下。

怪物AI移动

怪物移动是使用力F去驱动的。由力F产生加速度a（牛顿第二定律），从而产生速度v。然后，根据路程s与速度v之间的关系，就可以知道怪物移动的距离了。

牛顿第二定律给出以下关系：F＝ma （F是物体所受合外力,m是物体质量,a是物体此刻的加速度）

简单用伪代码表示就是

update(dt:number){ 计算出怪物所受的合力F 加速度a = 力F/怪物质量 //不关心质量直接设定1怪物当前速度v += 加速度a*每帧间隔dt 位置偏移值 = 怪物当前速度v*dt 怪物具体位置+=位置偏移值 }

那么我们的怪物移动AI的重点的就是落在计算怪物当前状态所受的合力F是多少的问题。

互联网小常识：网络管理系统一般由管理进程（Manager）、被管对象（MO）、代理进程（Agent）、管理信息库（MIB）和网络管理协议（SNMP和CMIP）五部分组成。

合力计算

下面给出几种比较常见的怪物行为，并对各种行为的计算力一个简单总结。

怪物寻找某个目标点-seek怪物远离某个目标点-flee (跟seek相反的行为)怪物到达某个目标点-arrive(与seek有一定区别，下文再作解释)怪物在场景中徘徊，类似无规则巡逻-wander怪物与追逐某个目标-pursuit怪物躲避某个目标-evade (和pursuit相反的行为)怪物躲避障碍物-obstacleAvoidance （以简单的圆形为例）怪物根据给定路径点跟随,巡逻-followPath多个怪物按照队列追逐-offsetPursuit (可以实现战斗队列等)集群行为的分散，靠拢，队列对齐等，用于简单模拟鱼群，蚁群移动的多个怪物根据流场寻路找到目标点

我们先一个个总结，然后根据特定条件计算多个行为之间产生的合力。

seek：seek行为提供一个力驱动怪物到达目标位置，咋计算这个力呢，看图就懂

图示红色箭头向量是我们期望怪物直接按照这个方向移动到目标点。但是我们当前速度方向是黑色箭头方向。那么我们应该提供的力，通俗点说应该是像虚线箭头所示，把它的当前速度方向矫正到期望的速度方向。

看到箭头指向就知道其实我们需要的力就是期望的速度-当前速度（向量减法，不多述说）

示例代码如下

//targetPos 需要寻找的位置cc.Vec2.subtract(tempVec2, targetPos,this._vehicle.position); cc.Vec2.normalize(tempVec2, tempVec2); cc.Vec2.multiplyScalar(tempVec2, tempVec2,this._vehicle.maxSpeed); cc.Vec2.subtract(tempVec2, tempVec2,this._vehicle.velocity);returntempVec2;//tempVec2就是返回的力

效果如下

flee：flee行为刚好与seek行为相反，它提供一个力使得怪物远离对应目标点，根据上面seek行为的图可以知道其实期望的速度方向就是跟seek的相反了，那简单，远离的力方向就是当前速度-期望速度方向了

示例代码如下

//targetPos 需要远离的位置cc.Vec2.subtract(tempVec2,this._vehicle.position, targetPos);if(tempVec2.magSqr() >90000) {//可设定特定距离才远离，返回的力为0cc.Vec2.set(tempVec2,0,0);returntempVec2; } cc.Vec2.normalize(tempVec2, tempVec2); cc.Vec2.multiplyScalar(tempVec2, tempVec2,this._vehicle.maxSpeed); cc.Vec2.subtract(tempVec2, tempVec2,this._vehicle.velocity);returntempVec2;

效果如下

arrive:arrive行为是产生一个力使得怪物到达目的地，注意，这里是到达，意味着它跟seek的区别是，arrive会使得怪物越靠近目标就会缓慢下来。那么我们就是在seek的基础上计算当前怪物与目标点距离反比关系来决定计算怪物当前的期望速度

示例代码如下

//targetPos 目标点cc.Vec2.subtract(tempVec2, targetPos,this._vehicle.position); let dis = tempVec2.mag();// dis为距离目标点距离大小if(dis >0.01) {//当距离>0的时候才计算对应力// deceleration为一个衰减系数 1 2 3 数值越低衰减越快let speed = dis / (deceleration *0.3);// 限制速度不会超过怪物最大速度值speed = Math.min(speed,this._vehicle.maxSpeed); cc.Vec2.multiplyScalar(tempVec2, tempVec2, speed); tempVec2.divSelf(dis);//tempVec2为计算得到的期望速度值cc.Vec2.subtract(tempVec2, tempVec2,this._vehicle.velocity);returntempVec2; } cc.Vec2.set(tempVec2,0,0);returntempVec2;

效果如下

wander：wander行为可以产生一个力使得怪物在场景上随机走动。这个想起来就简单吧，直接用随机数返回一个任意方向任意大小的力就好了。但是可能会造成怪物像无头苍蝇乱串抖动，不能达到一个很好的转弯。

这里给出游戏人工编程精粹中提到的一个方法：

在怪物的前端凸出一个圆圈，目标被限制在这个圆圈上，然后我们移向目标，每帧给目标添加一个随机的位移值，随着时间的推移，沿着圆周移来移去，来创造以一个没有抖动的往复运动。我就不画图了，直接白嫖书本上的图

游戏人工智能编程精粹

示例代码

let jitterTimeScale =this._wanderJitter *this._vehicle.timeElapse(); cc.Vec2.set(tempVec2_2,this.randomClamped() * jitterTimeScale,this.randomClamped() * jitterTimeScale);// tempvec2_2 随机偏移值 叠加到徘徊的wanderTarget上cc.Vec2.add(this._wanderTarget,this._wanderTarget, tempVec2_2);//归一化徘徊目标向量this._wanderTarget.normalizeSelf();//计算获得半泾cc.Vec2.multiplyScalar(this._wanderTarget,this._wanderTarget,this._wanderRadius);//在怪物局部坐标上将目标从0,0->偏移到 0,this._wanderDistancecc.Vec2.set(tempVec2_2,0,this._wanderDistance);//这里就是把对应目标圆圈做一定偏移cc.Vec2.add(tempVec2,this._wanderTarget, tempVec2_2);this._vehicle.node.getLocalMatrix(tempMat4);//将局部坐标向量转换为与怪物通一坐标系下的坐标，就是对应的目标坐标，相减得到对应徘徊力cc.Vec2.transformMat4(tempVec2, tempVec2, tempMat4); cc.Vec2.subtract(tempVec2, tempVec2,this._vehicle.position);returntempVec2;

还是看看具体效果吧，应该还行，暂时没有想出比较好的，性能又可以的

pursuit：pursuit行为提供一个力使得怪物具有一定的脑子，不至于在后面一直跟着，让怪物能够大概预测接下来某个时刻到达的位置，然后去寻找那个位置。简单来说pursuit就是seek行为基础上预测未来某个时刻的目标点。

这个分两种情况讨论。

第一种就是目标朝向跟怪物朝向是面对面的，那么怪物可以直接采用seek寻找即可

那么这个朝向是多少呢，我们可以给定一个范围即可。采用怪物与目标之间的速度点积求出对应角度的cos值，再acos一下就知道角度了。

第二种情况就是目标朝向跟怪物朝向的角度不是面对面的。那么我们就要预测一下怪物需要seek的目标点了。我们可以根据当前目标的位置，速度来简单确定一下这个目标点。采取正比于怪物与目标之间的距离，反比于怪物与目标之间的速度。

下面直接给出示例代码

//追逐privatepursuit(agent: Vehicle): cc.Vec2 {if(!agent) { tempVec2.set(cc.Vec2.ZERO);returntempVec2; } cc.Vec2.subtract(tempVec2, agent.position,this._vehicle.position); let relativeHeading =this._vehicle.heading.dot(agent.heading);//计算点积，假设是面对面（这里是计算反方向之间的夹角 0.95大概是18度左右）if(tempVec2.dot(this._vehicle.heading) >0&& relativeHeading < -0.95) {returnthis.seek(agent.position); }// 预测未来某个时间位置let lookaheadTime = tempVec2.mag() / (this._vehicle.maxSpeed + agent.velocity.mag()); cc.Vec2.multiplyScalar(tempVec2_2, agent.velocity, lookaheadTime); cc.Vec2.add(tempVec2_2, tempVec2_2, agent.position);returnthis.seek(tempVec2_2); }

效果大概如下吧

红色圆点为预测到的seek的位置

evade: evade行为其实就是跟pursuit行为相反了。它提供了一个逃避的力。但是躲避就没必要检查有没有面对面了，直接进行计算即可

下面直接给出示例以及效果。

//躲避privateevade(agent: Vehicle): cc.Vec2 { cc.Vec2.subtract(tempVec2, agent.position,this._vehicle.position); let lensqr = tempVec2.magSqr();if(lensqr >40000) {//可设定特定距离之后不躲避cc.Vec2.set(tempVec2,0,0);returntempVec2; }else{ let lookAheadTime = tempVec2.mag() / (this._vehicle.maxSpeed + agent.velocity.mag()); cc.Vec2.multiplyScalar(tempVec2, agent.velocity, lookAheadTime); cc.Vec2.add(tempVec2_2, tempVec2, agent.position);returnthis.flee(tempVec2_2); } }

设定某个目标处于wander以及evade行为

然后操控一个怪物去追

obstacleAvoidance：躲避障碍其实涉及的力计算应该比较复杂，这个用圆来计算仅做一个例子解析一下类似的力

这里记录一下对应的方法，还是贴出那个书的图来解释一下

大概思路就是，怪物前面弄出一个矩形检测框，把圆形障碍转换到怪物的局部坐标系下。那么障碍位于怪物后面（x<0）超出框宽度的（大于检测框宽度一半+障碍物半径一半）就不管了。然后计算检测框与对应障碍圆之间的交点（这里采用局部坐标x方向判定的。但是在cocos里面我采用的是y轴方向，因为方便计算，原理一样）

//圆方程 (x-a)^2+(y-b)^2=r^2 a,b圆心坐标 r半径

// 直线方程 y = mx+n.由于交点在x轴上。直接代入y=0 可以计算出x的值

互联网小常识：子网划分方法（根据IP地址划分子网）：依然要根据子网个数和主机个数确定子网号和主机号位数，然后计算子网掩码，然后列出子网地址段。

求得交点之后怎么计算操控力呢

主要是两部分，一个是躲避障碍的侧向力，一个是制动力，防止撞上去了。

直接给出示例代码

//躲避障碍物privateobstacleAvoidance(obstacles: Obstacle[]): cc.Vec2 {//检测框的长度正比于智能体速度，速度越快，检测框越长this._boxLength =40+ (this._vehicle.velocity.mag() /this._vehicle.maxSpeed) *40; let distToClose = Number.MAX_SAFE_INTEGER; let closeIndex = -1; cc.Vec2.set(tempVec2_3,0,0);this._vehicle.node.getLocalMatrix(tempMat4);//获得怪物的逆矩阵用于转换cc.Mat4.invert(tempMat4, tempMat4);//遍历所有的障碍物for(let i =0, len = obstacles.length; i < len; i++) { let obstacle = obstacles[i]; cc.Vec2.set(tempVec2_2, obstacle.node.x, obstacle.node.y); cc.Vec2.transformMat4(tempVec2_2, tempVec2_2, tempMat4);// 在检测盒范围内的障碍才需要进行检测if(tempVec2_2.y >=0&& tempVec2_2.y <=this._boxLength + obstacle.radius) {//圆方程 (x-a)^2+(y-b)^2=r^2 a,b圆心坐标 r半径//y = b+-sqrt(r^2-a^2)let expandeRadius = obstacle.radius +this._vehicle.radius;if(Math.abs(tempVec2_2.x) < expandeRadius) { let sqrtpart = Math.sqrt(expandeRadius * expandeRadius - tempVec2_2.x * tempVec2_2.x); let ip = tempVec2_2.y - sqrtpart;if(ip <=0) { ip = tempVec2_2.y + sqrtpart; }//找到最近的一个障碍的交点if(ip < distToClose) { distToClose = ip; closeIndex = i; cc.Vec2.set(tempVec2_3, tempVec2_2.x, tempVec2_2.y); } } } }if(closeIndex >=0) { let closeobstacle = obstacles[closeIndex];// 怪物离障碍越近，操控力越强let multiplier =1.0+ (this._boxLength - tempVec2_3.y) /this._boxLength;//侧向力tempVec2_2.x = (closeobstacle.radius - tempVec2_3.x) * multiplier;//制动力tempVec2_2.y = (closeobstacle.radius - tempVec2_3.y) *0.2;this._vehicle.node.getLocalMatrix(tempMat4);//局部坐标转换到与怪物同一坐标系下cc.Vec2.transformMat4(tempVec2, tempVec2_2, tempMat4);returntempVec2; }else{ tempVec2_2.set(cc.Vec2.ZERO);returntempVec2_2; } }

效果大概如下。给怪物添加arrive以及躲避障碍的行为。

可以看到怪物会有一定抖动。这个是我已经平滑过的，采取前10次速度方向来平均值来确定最终的朝向。如果不平滑会抖得更厉害。主要原因是因为arrive与躲避障碍同时印象多导致的。所以一般我都不用这种行为力或者少用，主要看效果吧。会用后续流场的概念来做。

followPath：跟随路径，这个就比较简单了就是给出指定的路径，让怪物不断寻找下一个目标点。当然这个还是有一定小问题，那就是判定是否到达那个点的问题，这个比较的距离其实跟帧率相关了。

不贴代码，直接给出效果

offsetPursuit：偏移追逐，其实这个就是多个怪按照一定队列去追逐某个目标，或者算是一种战斗队列一样跟随。这种行为力用得比较多。就是在追逐的目标点添加一个偏移值。

仅仅贴出一下效果吧。

集群：集群行为主要是包含了分离，队列，靠拢，3个行为特点。顾名思义了。

分离：获得一个力跟它周围的邻居怪物分离。那么就是要计算当前怪物跟邻居那些怪物的位置差单位向量的和，来获得最终需要移动的方向力。看图应该能理解

中间是当前怪物，周围是邻居怪物。那么求得当前怪物与周围邻居的分离力就是这些位置差的单位方向向量之和除以对应邻居个数。

示例代码

privateseparation(agents: Array): cc.Vec2{ cc.Vec2.set(tempVec2,0,0);for(leti =0, len = agents.length; i < len; i++) {// 遍历邻居if(agents[i].ID !=this._vehicle.ID && agents[i].isTag && agents[i] !=this._targetAgent1) { cc.Vec2.subtract(tempVec2_2,this._vehicle.position, agents[i].position);letlen = tempVec2_2.mag(); cc.Vec2.normalize(tempVec2_2, tempVec2_2); tempVec2_2.divSelf(len); cc.Vec2.add(tempVec2, tempVec2_2, tempVec2); } }returntempVec2; }

剩余的对齐，靠拢。其实跟分离的思想一样，不一一样说了。聚拢就是分离是相反的。对齐那个就是获得邻居对应速度朝向的总和方向。详细代码可以查看demo吧

下面给出对应效果。因为单个看没啥意思的。通常要用其中2,3种行为来看

示例：其中一个大红怪物在徘徊，另外一群小怪物一边徘徊一边躲避的同时与周围的邻居发生对应的分离，对齐，靠拢的现象

flow field：流场，有时候当场景上有一些障碍物，怪物需要躲避障碍去击杀玩家的时候，就需要用到寻路算法了。但是在怪物很多的情况下，每个怪物都采用A星寻路，消耗太大了。那么流场算法就帮到我们了。这个是个什么玩意呢。

这个也是在大多数RTS类游戏经常用到的。我们讲得通俗一点。

当我们用A星寻路的时候，从每个怪物开始点开始往目标点寻路，然后生成一条最短路径。其主要Dijkstra寻路的优化。而Dijkstra算法不细说了，它主要可以为我们生成一个从最开始点到各个可以通行的点的最短路径，得到一颗最小生成树。

那么反过来。我们可以从目标点开始采用Dijkstra算法把场景分块，遍历得到从目标点开始到场景各个块的最短路径。场上所有到这个目标点的怪物都按照这个最短路径来寻路到目标点了。这个也是A星跟Dijkstra寻路的最大区别。

那么我们就可以根据块与块之间的父子关系或者路径关系来获得当前块的一个实际的移动方向了。这个也就是所谓的向量场的概念了。

下面给出对应效果。在获得每个块的移动方向之后，怪物们就可以跟随这个向量场方向采用seek或者arrive行为到达那个位置了。，详细代码可以查看demo

如上图，红色的为障碍物，数值显示的是从目标点开始到其他各个点的花费。其实相邻或者斜角的都是1.而斜角方向不是1.414，主要是当算法遍历获得开放列表里面最短距离那个节点的时候，第一个就是最近那个节点，不用排序直接获取，效率快一些。而且这个对于生成向量场不影响。

但是你会发现目前这个状态，向量场方向只有横竖斜45度的方向。很明显的就是我明明稍微斜一点点就能更快到达目的地了。但这非要绕一绕

如图，我怪物绿点明明可以直接走过去的，但我现在根据向量场必须按照深红色的方向走。显然这是有点不太好的。

那么怎么优化呢，这里是采取了HowToRTS网站教程中的方法：视线。也就是在没有障碍的情况下（怪物其实能直接看到目标点了），我其实可以直接走过去的。那么通过这个概念我们就可以用来修改一下我们向量场的指向方向了。

那么我们怎么确定我当前的块是否是有视野直接看到目标点的呢？

我们也是反推一下：首先目标点本身肯定是有视野的，标记为true。我们从目标点本身出发，在直线方向上（横竖）邻居方块那也必定有视野，没毛病，标记为true。那对角线的方块怎么处理呢。其实也简单，只需要当前对角线方块相邻的那两个直线方块都有视野（也就是没有障碍），那它也必定有视野。好好体会，细品。

那么我们就可以把这个逻辑在用Dijkstra遍历过程中就可以计算出来了。

计算后的效果如下

可以看到灰色部分就是我们视野区域，也可以看到视野区域内的向量是直接指向目标点的。

以上便是对对应行为力的一个个简单描述了。那么我们怎么把他们整合在一起使用呢。

其实就是把对应每个行为求得的力叠加即可得到最终的合力了。

怎么叠加呢？

1.加权截断总和，最简单的方法就是给每一种行为操控力乘上一个权重值，然后把他们加一起，然后把结果截断到智能体可允许的最大操控力内。

简单，但每种激活的行为都要算一遍，而且调节加权值很难应该不同的情况。

2.带优先级的加权截断累计，文章示例都是采用这种方式的，在速度以及精确度上有一个折中。把对应激活的行为按照优先级排序，按照顺序计算每个行为力*它的权重。叠加之后如果超过智能体最大操控力，那么就直接截断了。后面的行为就不处理了。譬如躲避障碍跟到达目的地两个行为激活了，那么我们首先必要的就是要先躲开障碍物的同时到达目的地。所以躲避障碍物优先级最高，而且权重值也较高。

3.带优先级的抖动，这个就是给每个激活的行为添加一个随机权重，每帧根据优先级计算，对比每个行为的权重值，不为0也符合那么就采用这个行为提供的力，不考虑其他了。譬如到达以及躲避障碍，躲避障碍优先级还是最高。先随机一个值与躲避障碍的预设随机值比较，符合那就直接采用躲避障碍提供的力，到达那个就不管了。相比之下，这种计算力的方法效率比较高，但精度会有损失，可能没有得到自己想要的行为。

完毕！

demo链接：

https://gitee.com/wujianfen/steering

git@gitee.com:wujianfen/steering.git

互联网小常识：在一些中高端交换机中，通常把交换表保存在CAM(content-addressable memory)中，可以通过交换机的show cam命令查看，大中型为show cam dynamic ，小型为show mac-address-table。

免责声明：本站所有信息均搜集自互联网，并不代表本站观点，本站不对其真实合法性负责。如有信息侵犯了您的权益，请告知，本站将立刻处理。联系QQ：1640731186