第10章人工智能与游戏23

《第10章人工智能与游戏23》由会员分享，可在线阅读，更多相关《第10章人工智能与游戏23（23页珍藏版）》请在装配图网上搜索。

1、第第10章章 人工智能与游戏人工智能与游戏Page 210.1 人工智能与游戏的基础知识人工智能与游戏的基础知识10.2 追踪和躲避算法追踪和躲避算法10.3 寻径算法寻径算法目录目录Page 310.1 人工智能与游戏的基础人工智能与游戏的基础10.1.1 人工智能的概念 人工智能的研究是为了构建能像人类一样思考的计算机。更确切的定义是，AI是一种在计算机中模拟人类思维过程的技术。AI是一个非常广泛的研究领域，而和游戏相关的AI只是整个AI知识域中一个相对较小的子集。 人类思维并不是一个容易模拟的过程，这也就说明了为什么AI是如此之宽广的一个研究领域。虽然有很多不同的AI方法，但是它们都是在

2、计算机处理能力范围内模拟出人类的决策能力。大多数传统的AI系统使用各种基于信息的算法来进行决策，就像人类使用各种事先经验和心智规则来做出决定一样。 在过去，基于信息的算法具有完全确定性，于是每个决策都可以沿着一个可预言的逻辑流程倒推回去。现在，很多AI研究者意识到AI的确定性过程还不足以对人类思维精确建模，AI的研究热点从确定性AI模型转移到更加现实的、尝试考虑人类思维的微妙复杂性的AI模型，例如“最佳猜测”决策。就人类的思维而言，除了完整的逻辑决策过程外，这种类型的猜测还可能结合过去的经验、个人偏好以及当前的情绪状态来得出。Page 410.1 人工智能与游戏的基础人工智能与游戏的基础10.

3、1.2 游戏人工智能的类型（1）漫游AI 漫游AI确定一个游戏对象如何在一个虚拟的游戏世界中漫游，它是一种对游戏中NPC进行运动建模的AI系统。在这种AI系统中，NPC自己做出决定，确定它们如何在一个虚拟世界中漫游。典型的漫游AI例子有：在一些RPG游戏中，怪兽追着玩家角色运动；在飞行游戏中，漫游AI也用来实现按照预先定义的方式飞行的NPC战机，并适时躲避游戏玩家发射的子弹。基本上，对于计算机控制的游戏角色，不论它必须做出决定改变当前路径，还是要在游戏中实现需要的结果，或者只是简单地遵守某种特定的移动方式，都可以使用漫游AI。实现漫游AI通常都比较简单，一般根据一个游戏角色的位置，改变另一个游

4、戏角色的速度或位置。游戏角色的漫游移动也可以由随机的或预先定义的方式影响。Page 510.1 人工智能与游戏的基础人工智能与游戏的基础10.1.2 游戏人工智能的类型（2）行为AI 行为AI用于确定追踪在一个游戏玩家控制的角色后面的那些游戏对象的行为，这种追踪行为其实是一种AI系统，称为行为AI。行为AI常混合使用几种漫游AI算法来赋予游戏角色特定的AI行为。如果希望NPC有时候跟踪、有时候躲避、有时候遵从一种运动方式，甚至完全随机移动，那么可以考虑使用行为AI。而行为AI的另外一个作用就是可以改变游戏的难度。例如，可以设计一种行为AI模式，让NPC按照一定的时间比例采取跟踪、躲避和随机移动

5、三种移动模式组合而成的行为AI。如果希望在不同的关卡中设置游戏的不同难度，低难度关卡可以设置为20%的时间跟踪玩家角色，20%的时间躲避玩家角色，60%的时间随机移动；高难度关卡可以设置为，40%的时间跟踪玩家角色，20%的时间躲避玩家角色，40%的时间随机移动。（3）策略AI 在一个策略游戏中，策略AI从一组固定的实现定义的漫游规则中确定最佳的移动。Page 610.2 追踪和躲避算法追踪和躲避算法 追踪和躲避的问题在游戏开发中是随处可见的，无论开发的是什么类型的游戏，是第一人称射击游戏，或者是实时战略游戏，还是角色扮演游戏，游戏中的各种NPC角色都会追踪或躲避玩家角色。在第一人称射击游戏中

6、，敌对方的NPC需要追踪玩家角色并向玩家角色射击；当玩家角色向NPC射击的时候，它必须躲避玩家角色的射击。在实时战略游戏中，NPC所控制的部队时刻都在追踪玩家角色的部队和基地，并向玩家角色发起攻击；当玩家角色开始反击时，NPC又要开始躲避攻击，而游戏的进程也是在这种不断的追踪、躲避过程中推进的。总之，在任何一个种类的游戏中，都会看到NPC在进行追踪和躲避运动。Page 710.2 追踪和躲避算法追踪和躲避算法 追踪和躲避其实是一个两步的决策判断问题：首先根据一种行为模式决定NPC采取追踪行为还是采取躲避行为，其次是开始追踪或者逃跑。很多开发者认为追踪与躲避问题还包括另外的一层含义：即避开NPC

7、运动路径上的障碍物。 实现追踪和躲避算法的最简单、最直观的想法是根据玩家角色的位置信息，改变NPC的位置。在游戏循环的每帧中，缩小NPC与玩家角色在游戏世界中坐标的距离，可以使得NPC更接近玩家，实现追踪效果；在游戏循环的每帧中，增大NPC与玩家角色在游戏世界中坐标的距离，可以实现躲避与逃跑。而所谓的增大NPC与玩家角色的距离，可以简单地理解为：通过算法分别增大NPC位置坐标与玩家角色位置坐标各个对应分量差值的绝对值。一般而言，二维游戏中坐标值由(X,Y)两个分量表示，三维游戏的坐标值由(X,Y,Z)三个分量表示。Page 810.2 追踪和躲避算法追踪和躲避算法10.2.1 基本的追踪和躲避

8、 追踪算法的本质，就是根据玩家角色的位置信息，改变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-; e

9、lse if (yNPC xPlayerTile) xNPCTile-; else if (xNPCTile yPlayerTile) yNPCTile-; else if (yNPCTile destinationX) currentX -; else if (currentX destinationY) currentY -; else if (currentY destinationY) currentY+; Page 1610.3 寻径算法寻径算法10.3.1 简单寻径算法 比较好的做法是让游戏角色沿着比较自然的视线路径行走，可以用Bresenham线段光栅化算法来实现这种效果。Bre

10、senham算法是图形学中进行直线段光栅化的算法，其目的是找出一条直线段在屏幕上所经过的像素集合。而事实上，这个像素的集合也可以看成从屏幕上一个点通向另外一个点的路线，其效果如图10.2所示。需要注意的是，在基于贴砖的游戏环境中使用这种算法，Bresenham算法所找到的不是一个以像素为基础的路径集合，而是一个以贴砖为基础的像素集合。Page 1710.3 寻径算法寻径算法 简单寻径算法Bresenham算法Page 1810.3 寻径算法寻径算法10.3.2 A*算法 简单寻径算法在一些古老而简单的游戏中能够很好地解决问题，可是随着计算机处理能力的提高，现在的游戏在设计上比起街机时代的游戏要

11、复杂很多，这些简单的算法变得不太适用。例如，当场景中充满河流、森林、围墙等各种障碍物时，角色需要找到一条绕开障碍物并到达目标的最佳的路径就是一种相对复杂的情况。 解决这些问题的方法就是采用A*算法，一种高效的启发式搜索算法。A*算法总能够在一个有障碍物的复杂场景中找出一条从出发点到目标点的最佳路径。这里“最佳”的含义在不同的游戏中也不尽相同，有的游戏认为“最佳”是指人物角色在到达目标地点后其体力耗费最少，有的游戏则是指用最短的时间到达目标地点，而对于绝大多数游戏来说，“最佳”的意思是指能够绕开障碍物而且走过的距离最短。Page 1910.3 寻径算法寻径算法10.3.2 A*算法 A*算法可以

12、理解为，搜索一条由出发点到目标地点的路径，使得这条路径的“代价”是最小的，而不同的游戏对此处的“代价”将有不同的含义。 基于贴砖的游戏场景作为基础，在一个有障碍物的基于贴砖的游戏地图中寻找一条经过两点而代价最小的路径。在贴砖场景中，假定游戏角色在任意两个相邻的非障碍物贴砖之间移动都会产生“代价”，而障碍物贴砖不可通过。如图所示，A点可以通过不同的路径到达B点和C点，但是代价不同。Page 2010.3 寻径算法寻径算法10.3.2 A*算法 在A*算法的处理过程中，每个贴砖都被称为一个节点，A*算法在计算过程中为每个非障碍物节点都计算一个通过这个节点到达目标地点的代价函数，记为f(n)。在计算

13、过程中，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)值没有全部计算的节点。Page 2110.

14、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表中时，路径

15、被找到。另一种情况是，没有找到目标点，open表已空，也就是说，路径不存在。（3）如果找到路径，则从目标点开始，按父节点返回起始点，这就是我们需要的路径。Page 2210.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)值。Page 2310.3 寻径算法寻径算法10.3.2 A*算法的具体步骤 A*算法不断重复上述过程，最终将找到一条从起始点到目标点的代价最小的路径，如图所示。