人工智能与游戏的基础知识

第10章人工智能与游戏人工智能与游戏的基础知识第1页10.1人工智能与游戏基础知识10.2追踪和躲避算法10.3寻径算法目录人工智能与游戏的基础知识第2页10.1人工智能与游戏基础10.1.1人工智能概念人工智能研究是为了构建能像人类一样思索计算机。更确切定义是，AI是一个在计算机中模拟人类思维过程技术。AI是一个非常广泛研究领域，而和游戏相关AI只是整个AI知识域中一个相对较小子集。人类思维并不是一个轻易模拟过程，这也就说明了为何AI是如此之宽广一个研究领域。即使有很多不一样AI方法，不过它们都是在计算机处理能力范围内模拟出人类决议能力。大多数传统AI系统使用各种基于信息算法来进行决议，就像人类使用各种事先经验和心智规则来做出决定一样。在过去，基于信息算法含有完全确定性，于是每个决议都能够沿着一个可预言逻辑流程倒推回去。现在，很多AI研究者意识到AI确实定性过程还不足以对人类思维准确建模，AI研究热点从确定性AI模型转移到愈加现实、尝试考虑人类思维微妙复杂性AI模型，比如“最正确猜测”决议。就人类思维而言，除了完整逻辑决议过程外，这种类型猜测还可能结合过去经验、个人偏好以及当前情绪状态来得出。人工智能与游戏的基础知识第3页10.1人工智能与游戏基础10.1.2游戏人工智能类型（1）漫游AI

漫游AI确定一个游戏对象怎样在一个虚拟游戏世界中漫游，它是一个对游戏中NPC进行运动建模AI系统。在这种AI系统中，NPC自己做出决定，确定它们怎样在一个虚拟世界中漫游。经典漫游AI例子有：在一些RPG游戏中，怪兽追着玩家角色运动；在飞行游戏中，漫游AI也用来实现按照预先定义方式飞行NPC战机，并适时躲避游戏玩家发射子弹。基本上，对于计算机控制游戏角色，不论它必须做出决定改变当前路径，还是要在游戏中实现需要结果，或者只是简单地恪守某种特定移动方式，都能够使用漫游AI。实现漫游AI通常都比较简单，普通依据一个游戏角色位置，改变另一个游戏角色速度或位置。游戏角色漫游移动也能够由随机或预先定义方式影响。人工智能与游戏的基础知识第4页10.1人工智能与游戏基础10.1.2游戏人工智能类型（2）行为AI行为AI用于确定追踪在一个游戏玩家控制角色后面那些游戏对象行为，这种追踪行为其实是一个AI系统，称为行为AI。行为AI常混合使用几个漫游AI算法来赋予游戏角色特定AI行为。假如希望NPC有时候跟踪、有时候躲避、有时候遵从一个运动方式，甚至完全随机移动，那么能够考虑使用行为AI。而行为AI另外一个作用就是能够改变游戏难度。比如，能够设计一个行为AI模式，让NPC按照一定时间百分比采取跟踪、躲避和随机移动三种移动模式组合而成行为AI。假如希望在不一样关卡中设置游戏不一样难度，低难度关卡能够设置为20%时间跟踪玩家角色，20%时间躲避玩家角色，60%时间随机移动；高难度关卡能够设置为，40%时间跟踪玩家角色，20%时间躲避玩家角色，40%时间随机移动。（3）策略AI在一个策略游戏中，策略AI从一组固定实现定义漫游规则中确定最正确移动。人工智能与游戏的基础知识第5页10.2追踪和躲避算法追踪和躲避问题在游戏开发中是随地可见，不论开发是什么类型游戏，是第一人称射击游戏，或者是实时战略游戏，还是角色饰演游戏，游戏中各种NPC角色都会追踪或躲避玩家角色。在第一人称射击游戏中，敌对方NPC需要追踪玩家角色并向玩家角色射击；当玩家角色向NPC射击时候，它必须躲避玩家角色射击。在实时战略游戏中，NPC所控制部队时刻都在追踪玩家角色部队和基地，并向玩家角色发起攻击；当玩家角色开始还击时，NPC又要开始躲避攻击，而游戏进程也是在这种不停追踪、躲避过程中推进。总之，在任何一个种类游戏中，都会看到NPC在进行追踪和躲避运动。人工智能与游戏的基础知识第6页10.2追踪和躲避算法追踪和躲避其实是一个两步决议判断问题：首先依据一个行为模式决定NPC采取追踪行为还是采取躲避行为，其次是开始追踪或者逃跑。很多开发者认为追踪与躲避问题还包含另外一层含义：即避开NPC运动路径上障碍物。实现追踪和躲避算法最简单、最直观想法是依据玩家角色位置信息，改变NPC位置。在游戏循环每帧中，缩小NPC与玩家角色在游戏世界中坐标距离，能够使得NPC更靠近玩家，实现追踪效果；在游戏循环每帧中，增大NPC与玩家角色在游戏世界中坐标距离，能够实现躲避与逃跑。而所谓增大NPC与玩家角色距离，能够简单地了解为：经过算法分别增大NPC位置坐标与玩家角色位置坐标各个对应分量差值绝对值。普通而言，二维游戏中坐标值由(X,Y)两个分量表示，三维游戏坐标值由(X,Y,Z)三个分量表示。人工智能与游戏的基础知识第7页10.2追踪和躲避算法10.2.1基本追踪和躲避追踪算法本质，就是依据玩家角色位置信息，改变NPC位置，减小NPC与玩家角色在游戏世界中坐标距离。【例10.1】基本追踪算法。//xNPC与yNPC分别代表NPC两个坐标分量//xPlayer与yPlayer分别代表玩家角色两个坐标分量if(xNPC>xPlayer){xNPC--;}elseif(xNPC<xPlayer){xNPC++;}if(yNPC>yPlayer){yNPC--;}elseif(yNPC<yPlayer){yNPC++;}人工智能与游戏的基础知识第8页10.2追踪和躲避算法10.2.1基本追踪和躲避躲避在逻辑上与追踪刚好相反，它目标是让NPC摆脱玩家角色追踪与打击。所以，躲避算法能够经过与追踪相同方式实现，不过，它们坐标操作方向相反。【例10.2】基本躲避算法。if(xNPC>xPlayer){xNPC++;}elseif(xNPC<xPlayer){xNPC--;}if(yNPC>yPlayer){yNPC++;}elseif(yNPC<yPlayer){yNPC--;}人工智能与游戏的基础知识第9页10.2追踪和躲避算法10.2.2随机性追踪和躲避算法基本追踪和躲避算法确实能够使NPC完成追踪或者躲避任务，不过它过于简单处理方式使得NPC运动过程不太自然，甚至会在一定程度上影响游戏可操作性和可玩性。比如，在追踪过程中，NPC会飞快地向玩家靠近，在这种情况下，玩家还没来得及反应就已经被NPC击中。而同时在NPC躲避过程中，也会飞快地逃离玩家，不论怎样玩家也不可能追得上NPC。这些情况都会打击游戏玩家信心与兴趣，从而不利于提升游戏可玩性与趣味性。在绝大多数情况下，在进行游戏设计时都希望能够得到一个折中情况，这么玩家才有可能在游戏中战胜NPC，并取得游戏趣味性。人工智能与游戏的基础知识第10页10.2追踪和躲避算法10.2.2随机性追踪和躲避算法为了实现上述所说折中情况，让NPC运动方式更为平滑，一个比很好方法就是在追踪和躲避过程中加入一些随机性。【例10.3】随机追踪算法。if((Math.abs(rand.nextlnt())%2)==0){if(xNPC>xPlayer){xNPC--;}elseif(xNPC<xPlayer){xNPC++;}}if((Math.abs(rand.nextlnt())%2)==0){if(yNPC>yPlayer){yNPC--;}elseif(yNPC<yPlayer){yNPC++;}}人工智能与游戏的基础知识第11页10.2追踪和躲避算法10.2.3基于贴砖追踪和躲避算法在传统2D和2.5D游戏中，游戏场景通常采取贴砖结构。基于贴砖场景会被分割成许多不连续砖块，砖块能够是正方形、菱形和六边形。游戏角色位置只能处于某个贴砖中心，而且游戏角色在场景中移动是以贴砖为单位，游戏角色每次移动都会从一个贴砖中心移动到另外一个相邻贴砖中心。而在以像素为坐标连续环境中，游戏角色在场景中移动是以像素为单位，游戏角色移动方向限制较小。人工智能与游戏的基础知识第12页10.2追踪和躲避算法10.2.3基于贴砖追踪和躲避算法不论在以像素为单位连续环境中还是以贴砖为单位环境中，上述基本追踪和躲避算法思想都是适用，只是算法在表示和实现上稍有不一样。在连续环境中，X和Y坐标代表以屏幕某个像素点为原点像素坐标（通常是屏幕左上角或者左下角）；而在贴砖环境中，X和Y坐标代表贴砖行编号和列编号。【例10.4】贴砖环境中追踪算法。//xNPCTile与yNPCTile分别代表NPC两个坐标分量//xPlayerTile与yPlayerTile分别代表玩家角色两个坐标分量if(xNPCTile>xPlayerTile){xNPCTile--;}elseif(xNPCTile<xPlayerTile){xNPCTile++;}if(yNPCTile>yPlayerTile){yNPCTile--;}elseif(yNPCTile<yPlayerTile){yNPCTile++;}人工智能与游戏的基础知识第13页10.3寻径算法10.3.1简单寻径算法从最基本层次来讲，路径寻找只是让某个游戏角色从其最初位置移动到所需抵达目标地过程而已。从某种意义上说，简单寻径算法和基本追踪算法原理是完全一样，其目标都是让游戏角色在某种运动方式指导下慢慢靠近目标位置。所不一样是，在追踪算法中，目标位置是游戏中另一个游戏角色所在位置；而在寻径算法中，目标位置可能是某个游戏角色所在位置也可能是游戏地图上某个区域。人工智能与游戏的基础知识第14页10.3寻径算法10.3.1简单寻径算法

【例10.5】简单寻径算法。//currentX与currentY分别代表NPC当前坐标X和Y分量//destinationX与destinationY分别代表目标位置坐标X和Y分量if(currentX>destinationX){currentX--;}elseif(currentX<destinationX){currentX++;}if(currentY>destinationY){currentY--;}elseif(currentY<destinationY){currentY++;}人工智能与游戏的基础知识第15页10.3寻径算法10.3.1简单寻径算法比很好做法是让游戏角色沿着比较自然视线路径行走，能够用Bresenham线段光栅化算法来实现这种效果。Bresenham算法是图形学中进行直线段光栅化算法，其目标是找出一条直线段在屏幕上所经过像素集合。而实际上，这个像素集合也能够看成从屏幕上一个点通向另外一个点路线，其效果如图10.2所表示。需要注意是，在基于贴砖游戏环境中使用这种算法，Bresenham算法所找到不是一个以像素为基础路径集合，而是一个以贴砖为基础像素集合。人工智能与游戏的基础知识第16页10.3寻径算法简单寻径算法Bresenham算法人工智能与游戏的基础知识第17页10.3寻径算法10.3.2A*算法简单寻径算法在一些古老而简单游戏中能够很好地处理问题，可是伴随计算机处理能力提升，现在游戏在设计上比起街机时代游戏要复杂很多，这些简单算法变得不太适用。比如，当场景中充满河流、森林、围墙等各种障碍物时，角色需要找到一条绕开障碍物并抵达目标最正确路径就是一个相对复杂情况。处理这些问题方法就是采取A*算法，一个高效启发式搜索算法。A*算法总能够在一个有障碍物复杂场景中找出一条从出发点到目标点最正确路径。这里“最正确”含义在不一样游戏中也不尽相同，有游戏认为“最正确”是指人物角色在抵达目标地点后其体力花费最少，有游戏则是指用最短时间抵达目标地点，而对于绝大多数游戏来说，“最正确”意思是指能够绕开障碍物而且走过距离最短。人工智能与游戏的基础知识第18页10.3寻径算法10.3.2A*算法

A*算法能够了解为，搜索一条由出发点到目标地点路径，使得这条路径“代价”是最小，而不一样游戏对此处“代价”将有不一样含义。基于贴砖游戏场景作为基础，在一个有障碍物基于贴砖游戏地图中寻找一条经过两点而代价最小路径。在贴砖场景中，假定游戏角色在任意两个相邻非障碍物贴砖之间移动都会产生“代价”，而障碍物贴砖不可经过。如图所表示，A点能够经过不一样路径抵达B点和C点，不过代价不一样。人工智能与游戏的基础知识第19页10.3寻径算法10.3.2A*算法

在A*算法处理过程中，每个贴砖都被称为一个节点，A*算法在计算过程中为每个非障碍物节点都计算一个经过这个节点抵达目标地点代价函数，记为f(n)。在计算过程中，f(n)为一个估算值，伴随计算进行每个节点f(n)值都有可能改变。A*算法定义：f(n)=g(n)+h(n)。g(n)表示从起始点移动到当前节点花费代价，依据之前条件，垂直和水平方向代价为10，对角线方向为14。h(n)表示当前点到目标点预计代价，普通设定这个预计代价值为：当前点到目标点水平和垂直方格总数，然后乘以10。A*算法在计算过程中使用到两个链表，一个叫做open表，另一个叫做closed表。closed表中节点是其全部相邻节点f(n)值全部计算过节点，open表中节点是计算过f(n)值，不过其全部相邻节点f(n)值没有全部计算节点。人工智能与游戏的基础知识第20页10.3寻径算法10.3.2A*算法详细步骤（1）将起始点添加到open表中。（2）重复以下步骤：①寻找open表中f(n)值最低点作为当前点，并将它放入closed表中。②遍历当前节点相邻全部8个节点，假如不可经过或已经在closed表中，则略过。假如不在open表中，则将其添加进open表中，并把当前节点作为其父节点，统计这个节点f(n)、g(n)、h(n)值；假如已经在open表中，则检验g(n)值，看是否存在更加好路径，假如存在，则把这个节点父节点