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

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,Textmasterformate durch Klicken bearbeiten,Zweite Ebene,Dritte Ebene,Vierte Ebene,Fnfte Ebene,Page,*,Klicken Sie,um das Titelformat zu bearbeiten,Textmasterformate durch Klicken bearbeiten,Zweite Ebene,Dritte Ebene,Vierte Ebene,Fnfte Ebene,Klicken Sie,um das Titelformat zu bearbeiten,Textmasterformate durch Klicken bearbeiten,Zweite Ebene,Dritte Ebene,Vierte Ebene,Fnfte Ebene,Klicken Sie,um das Titelformat zu bearbeiten,Textmasterformate durch Klicken bearbeiten,Zweite Ebene,Dritte Ebene,Vierte Ebene,Fnfte Ebene,Page,*,Klicken Sie,um das Titelformat zu bearbeiten,第,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-;,else if(xNPC yPlayer)yNPC-;,else if(yNPC xPlayer)xNPC+;,else if(xNPC yPlayer)yNPC+;,else if(yNPC xPlayer)xNPC-;,else if(xNPC yPlayer)yNPC-;,else if(yNPC xPlayerTile)xNPCTile-;,else if(xNPCTile yPlayerTile)yNPCTile-;,else if(yNPCTile destinationX)currentX-;,else if(currentX destinationY)currentY-;,else if(currentY destinationY)currentY+;,人工智能与游戏的基础知识,第15页,10.3,寻径算法,10.3.1,简单寻径算法,比很好做法是让游戏角色沿着比较自然视线路径行走，能够用,Bresenham,线段光栅化算法来实现这种效果。,Bresenham,算法是图形学中进行直线段光栅化算法，其目标是找出一条直线段在屏幕上所经过像素集合。而实际上，这个像素集合也能够看成从屏幕上一个点通向另外一个点路线，其效果如图,10.2,所表示。需要注意是，在基于贴砖游戏环境中使用这种算法，,Bresenham,算法所找到不是一个以像素为基础路径集合，而是一个以贴砖为基础像素集合。,人工智能与游戏的基础知识,第16页,10.3,寻径算法,简单寻径算法,Bresenham,算法,人工智能与游戏的基础知识,第17页,10.3,寻径算法,10.3.2 A*,算法,简单寻径算法在一些古老而简单游戏中能够很好地处理问题，可是伴随计算机处理能力提升，现在游戏在设计上比起街机时代游戏要复杂很多，这些简单算法变得不太适用。比如，当场景中充满河流、森林、围墙等各种障碍物时，角色需要找到一条绕开障碍物并抵达目标最正确路径就是一个相对复杂情况。,处理这些问题方法就是采取,A*,算法，一个高效启发式搜索算法。,A*,算法总能够在一个有障碍物复杂场景中找出一条从出发点到目标点最正确路径。这里“最正确”含义在不一样游戏中也不尽相同，有游戏认为“最正确”是指人物角色在抵达目标地点后其体力花费最少，有游戏则是指用最短时间抵达目标地点，而对于绝大多数游戏来说，“最正确”意思是指能够绕开障碍物而且走过距离最短。,人工智能与游戏的基础知识,第18页,10.3,寻径算法,10.3.2 A*,算法,A*,算法能够了解为，搜索一条由出发点到目标地点路径，使得这条路径“代价”是最小，而不一样游戏对此处“代价”将有不一样含义。,基于贴砖游戏场景作为基础，在一个有障碍物基于贴砖游戏地图中寻找一条经过两点而代价最小路径。在贴砖场景中，假定游戏角色在任意两个相邻非障碍物贴砖之间移动都会产生“代价”，而障碍物贴砖不可经过。如图所表示，,A,点能够经过不一样路径抵达,B,点和,C,点，不过代价不一样。,人工智能与游戏的基础知识,第19页,10.3,寻径算法,10.3.2 A*,算法,在,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.2 A*,算法详细步骤,（,1,）将起始点添加到,open,表中。,（,2,）重复以下步骤：,寻找open,表中,f,(,n,),值最低点作为当前点，并将它放入,closed,表中。,遍历当前节点相邻全部,8,个节点，假如不可经过或已经在,closed,表中，则略过。假如不在,open,表中，则将其添加进,open,表中，并把当前节点作为其父节点，统计这个节点,f,(,n,),、,g,(,n,),、,h,(,n,),值；假如已经在,open,表中，则检验,g,(,n,),值，看是否存在更加好路径，假如存在，则把这个节点父节点改为当前点，并重新计算这个节点,g,(,n,),和,f,(,n,),值，对,open,表按,f,(,n,),值排序。,当目标点被放入,closed,表中时，路径被找到另一个情况是，没有找到目标点，,open,表已空，也就是说，路径不存在。,（,3,）假如找到路径，则从目标点开始，按父节点返回起始点，这就是我们需要路径。,人工智能与游戏的基础知识,第21页,10.3,寻径算法,10.3.2 A*,算法,A*,算法在计算过程中每步都会对全部,open,表里节点按照,f,(,n,),值大小进行排序，选择,f,(,n,),值最小节点将其移动到,closed,表中，并考虑其全部相邻节点。详细步骤以下。,假如某个相邻节点不在,open,表中，则将其加入,open,表，并将当前节点作为这个相邻节点父节点，计算其,f,(,n,),、,g,(,n,),和,h,(,n,),值。,假如这个相邻节点已经在,open,表中，则比较其,g,(,n,),值与经过本节点抵达此相邻节点总代价值，假如经过本节点抵达这个相邻节点总代价值更小，则更新这个相邻节点,g,(,n,),值，将其父节点设为本节点，并依据新,g,(,n,),值重新计算,f,(,n,),值；不然，不改变这个相邻节点任何属性，同时将这些相邻节点加入,open,表中，并对这些相邻节点计算,f,(,n,),、,g,(,n,),、,h,(,n,),值。,人工智能与游戏的基础知识,第22页,10.3,寻径算法,10.3.2 A*,算法详细步骤,A*,算法不停重复上述过程，最终将找到一条从起始点到目标点代价最小路径，如图所表示。,人工智能与游戏的基础知识,第23页,