第10章人工智能与游戏ppt课件

1、第10章 人工智能与游戏.10.1 人工智能与游戏的根底知识10.2 追踪和躲避算法10.3 寻径算法目录.10.1 人工智能与游戏的根底10.1.1 人工智能的概念人工智能的研讨是为了构建能像人类一样思索的计算机。更确切的定义是，AI是一种在计算机中模拟人类思想过程的技术。AI是一个非常广泛的研讨领域，而和游戏相关的AI只是整个AI知识域中一个相对较小的子集。人类思想并不是一个容易模拟的过程，这也就阐明了为什么AI是如此之广大的一个研讨领域。虽然有很多不同的AI方法，但是它们都是在计算机处置才干范围内模拟出人类的决策才干。大多数传统的AI系统运用各种基于信息的算法来进展决策，就像人类运用各种

2、事先阅历和心智规那么来做出决议一样。在过去，基于信息的算法具有完全确定性，于是每个决策都可以沿着一个可预言的逻辑流程倒推回去。如今，很多AI研讨者认识到AI确实定性过程还缺乏以对人类思想准确建模，AI的研讨热点从确定性AI模型转移到更加现实的、尝试思索人类思想的微妙复杂性的AI模型，例如“最正确猜测决策。就人类的思想而言，除了完好的逻辑决策过程外，这种类型的猜测还能够结合过去的阅历、个人偏好以及当前的心情形状来得出。.10.1 人工智能与游戏的根底10.1.2 游戏人工智能的类型1遨游AI 遨游AI确定一个游戏对象如何在一个虚拟的游戏世界中遨游，它是一种对游戏中NPC进展运动建模的AI系统。在

3、这种AI系统中，NPC本人做出决议，确定它们如何在一个虚拟世界中遨游。典型的遨游AI例子有：在一些RPG游戏中，怪兽追着玩家角色运动；在飞行游戏中，遨游AI也用来实现按照预先定义的方式飞行的NPC战机，并适时躲避游戏玩家发射的子弹。根本上，对于计算机控制的游戏角色，不论它必需做出决议改动当出途径，还是要在游戏中实现需求的结果，或者只是简单地遵守某种特定的挪动方式，都可以运用遨游AI。实现遨游AI通常都比较简单，普通根据一个游戏角色的位置，改动另一个游戏角色的速度或位置。游戏角色的遨游挪动也可以由随机的或预先定义的方式影响。.10.1 人工智能与游戏的根底10.1.2 游戏人工智能的类型2行为A

4、I 行为AI用于确定追踪在一个游戏玩家控制的角色后面的那些游戏对象的行为，这种追踪行为其实是一种AI系统，称为行为AI。行为AI常混合运用几种遨游AI算法来赋予游戏角色特定的AI行为。假设希望NPC有时候跟踪、有时候躲避、有时候服从一种运动方式，甚至完全随机挪动，那么可以思索运用行为AI。而行为AI的另外一个作用就是可以改动游戏的难度。例如，可以设计一种行为AI方式，让NPC按照一定的时间比例采取跟踪、躲避和随机挪动三种挪动方式组合而成的行为AI。假设希望在不同的关卡中设置游戏的不同难度，低难度关卡可以设置为20%的时间跟踪玩家角色，20%的时间躲避玩家角色，60%的时间随机挪动；高难度关卡可

5、以设置为，40%的时间跟踪玩家角色，20%的时间躲避玩家角色，40%的时间随机挪动。3战略AI 在一个战略游戏中，战略AI从一组固定的实现定义的遨游规那么中确定最正确的挪动。.10.2 追踪和躲避算法 追踪和躲避的问题在游戏开发中是随处可见的，无论开发的是什么类型的游戏，是第一人称射击游戏，或者是实时战略游戏，还是角色扮演游戏，游戏中的各种NPC角色都会追踪或躲避玩家角色。在第一人称射击游戏中，敌对方的NPC需求追踪玩家角色并向玩家角色射击；当玩家角色向NPC射击的时候，它必需躲避玩家角色的射击。在实时战略游戏中，NPC所控制的部队时辰都在追踪玩家角色的部队和基地，并向玩家角色发起攻击；当玩家

6、角色开场还击时，NPC又要开场躲避攻击，而游戏的进程也是在这种不断的追踪、躲避过程中推进的。总之，在任何一个种类的游戏中，都会看到NPC在进展追踪和躲避运动。.10.2 追踪和躲避算法 追踪和躲避其实是一个两步的决策判别问题：首先根据一种行为方式决议NPC采取追踪行为还是采取躲避行为，其次是开场追踪或者逃跑。很多开发者以为追踪与躲避问题还包括另外的一层含义：即避开NPC运动途径上的妨碍物。 实现追踪和躲避算法的最简单、最直观的想法是根据玩家角色的位置信息，改动NPC的位置。在游戏循环的每帧中，减少NPC与玩家角色在游戏世界中坐标的间隔，可以使得NPC更接近玩家，实现追踪效果；在游戏循环的每帧中

7、，增大NPC与玩家角色在游戏世界中坐标的间隔，可以实现躲避与逃跑。而所谓的增大NPC与玩家角色的间隔，可以简单地了解为：经过算法分别增大NPC位置坐标与玩家角色位置坐标各个对应分量差值的绝对值。普通而言，二维游戏中坐标值由(X,Y)两个分量表示，三维游戏的坐标值由(X,Y,Z)三个分量表示。.10.2 追踪和躲避算法10.2.1 根本的追踪和躲避 追踪算法的本质，就是根据玩家角色的位置信息，改动NPC的位置，减小NPC与玩家角色在游戏世界中坐标的间隔。【例10.1】 根本追踪算法。/xNPC与yNPC分别代表NPC的两个坐标分量/xPlayer与yPlayer分别代表玩家角色的两个坐标分量if

8、 (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 -; els

9、e if (currentX destinationY) currentY -; else if (currentY destinationY) currentY+; .10.3 寻径算法10.3.1 简单寻径算法 比较好的做法是让游戏角色沿着比较自然的视野途径行走，可以用Bresenham线段光栅化算法来实现这种效果。Bresenham算法是图形学中进展直线段光栅化的算法，其目的是找出一条直线段在屏幕上所经过的像素集合。而现实上，这个像素的集合也可以看成从屏幕上一个点通向另外一个点的道路，其效果如图10.2所示。需求留意的是，在基于贴砖的游戏环境中运用这种算法，Bresenham算法所找到的

10、不是一个以像素为根底的途径集合，而是一个以贴砖为根底的像素集合。.10.3 寻径算法 简单寻径算法Bresenham算法.10.3 寻径算法10.3.2 A*算法 简单寻径算法在一些古老而简单的游戏中可以很好地处理问题，可是随着计算机处置才干的提高，如今的游戏在设计上比起街机时代的游戏要复杂很多，这些简单的算法变得不太适用。例如，当场景中充溢河流、森林、围墙等各种妨碍物时，角色需求找到一条绕开妨碍物并到达目的的最正确的途径就是一种相对复杂的情况。 处理这些问题的方法就是采用A*算法，一种高效的启发式搜索算法。A*算法总可以在一个有妨碍物的复杂场景中找出一条从出发点到目的点的最正确途径。这里“最

11、正确的含义在不同的游戏中也不尽一样，有的游戏以为“最正确是指人物角色在到达目的地点后其膂力耗费最少，有的游戏那么是指用最短的时间到达目的地点，而对于绝大多数游戏来说，“最正确的意思是指可以绕开妨碍物而且走过的间隔最短。.10.3 寻径算法10.3.2 A*算法 A*算法可以了解为，搜索一条由出发点到目的地点的途径，使得这条途径的“代价是最小的，而不同的游戏对此处的“代价将有不同的含义。 基于贴砖的游戏场景作为根底，在一个有妨碍物的基于贴砖的游戏地图中寻觅一条经过两点而代价最小的途径。在贴砖场景中，假定游戏角色在恣意两个相邻的非妨碍物贴砖之间挪动都会产生“代价，而妨碍物贴砖不可经过。如下图，A点

12、可以经过不同的途径到达B点和C点，但是代价不同。.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*算法在计

13、算过程中运用到两个链表，一个叫做open表，另一个叫做closed表。closed表中的节点是其一切相邻节点的f(n)值全部计算过的节点，open表中的节点是计算过f(n)值，但是其一切相邻节点的f(n)值没有全部计算的节点。.10.3 寻径算法10.3.2 A*算法的详细步骤1将起始点添加到open表中。2反复以下步骤： 寻觅open表中f(n)值最低的点作为当前点，并将它放入closed表中。 遍历当前节点相邻的一切8个节点，假设不可经过或曾经在closed表中，那么略过。假设不在open表中，那么将其添加进open表中，并把当前节点作为其父节点，记录这个节点的f(n)、g(n)、h(n)

14、值；假设曾经在open表中，那么检查g(n)值，看能否存在更好的途径，假设存在，那么把这个节点的父节点改为当前点，并重新计算这个节点的g(n)和f(n)值，对open表按f(n)值排序。 当目的点被放入closed表中时，途径被找到。另一种情况是，没有找到目的点，open表已空，也就是说，途径不存在。3假设找到途径，那么从目的点开场，按父节点前往起始点，这就是我们需求的途径。.10.3 寻径算法10.3.2 A*算法 A*算法在计算过程中的每步都会对一切open表里的节点按照f(n)值的大小进展排序，选择f(n)值最小的节点将其挪动到closed表中，并思索其一切相邻节点。详细步骤如下。 假设某个相邻节点不在open表中，那么将其参与open表，并将当前节点作为这个相邻节点的父节点，计算其f(n)、g(n)和h(n)值。 假设这个相邻节点曾经在open表中，那么比较其g(n