第十一章 二维游戏高级设计.ppt

1、游戏开发与设计,第十一章 二维游戏高级设计,重点和难点,游戏地图 路径查找 碰撞检测 人工智能,游戏地图,大部分的游戏都有地图，类似 SLG, RPG,RTS 之类的游戏， 地图的设计好坏与关卡的吸引程度关系很大。 游戏地图在显示上一般是由很多基本的图形拼合而成。地图在程序最简单的方式是以数组进行存放，最简单的可以以1代替障碍物，0代表可以通过的地面,游戏地图,Int maze= 1，1，0，0, 0，1，0，1, 1，0，0，0, 0，0，1，1 ;,游戏地图,上面的数据就表示了一个最简单的4X4的地图。这种简单的地图一般以一个个的小方格作为其中的元素，可以很简单的从地图数据中生成地图的实际

2、显示图样。,游戏地图,游戏地图,可以看到坦克的下面就是一幅地图，由平地以及障碍物构成。平面可以通行，用白色表示，黄黑相间的是障碍物，不能够通行。在这个地图中，只用了两种地形。 在具有多种地表情况的地图中，数据结构的表现就没有这么简单。因为同样是属于不可移动的位置，显示在游戏者眼前的却是不一样的图片。,游戏地图,例如一座山的边沿对于程序的属性是一致的，但显示在游戏者面前的是一个由不同的图片组成的连续的山沿。 在日常生活中，需要到达某个终点，我们通常需要查找地图，通过路标确认自己的所在位置，根据自己对于周围环境的判断选择达到终点的方式。,路径查找,而在游戏中，也需要判断一个NPC从一个起点到达一个

3、终点，路途中可能遇到不可预料的障碍， 这是一个最为常见的游戏人工智能问题。尤其在很多RTS游戏，从起点到终点的有效性决定了操作的难度以及游戏者真正意图能否忠实体现。这就涉及到游戏地图的路径搜索问题。,路径查找,基本算法 路径搜索算法中需要解决的最基本问题是避开障碍物。最容易实现的方法是下图描述的算法。,路径查找,从起点到终点拉一条直线A。沿着直线A朝终点行进，一遇到障碍物便按逆时针方向绕着障碍物行走，直至碰到直线A。重复步骤2，使一定能最终达到目的地。,路径查找,该算法计算出来的路径并不是最短的，有时候走出的路线还会让游戏者大失所望，但该算法的运行速度很快，能在较低档次的处理系统上满足游戏中实

4、时的要求，经典游戏“命令与征服”中的寻径算法是以此为基础的。以对上述算法作几点改进，使可移动物体的行走路线更为合理一些。,路径查找,上图中显然可移动物体应按沿顺时针方向绕障碍物走，而不该按逆时针方向去绕弯子。于是，当遇到障碍物时， 首先要判断环绕方向。 如果比起逆时针方向，顺时针方向行走能以更短的路径碰到直线A，那么选取逆时针方向绕着障碍物行走，反之亦然。,路径查找,尽量走直线路径，减少绕行路径。如图所示，先按上述算法计算出行走路线B，然后当可移动物体在路线B上绕着障碍物行进时，每走一步便从当前位置向终点拉一条直线C，如果沿着直线C前进能与目前还未经过的行走路线B的某段相遇（中间没有障碍物），

5、就终止绕行，直接按直线C行走至路线B，从而缩短了路途。,路径查找,当终点处于障碍物包围之中，可移动物体永远不可能达到终点，无论是按顺时针方 向还是按逆时针方向绕行都只能回到原地，无法进行了。对于这种情况的处理方式就是绕障碍物一周，选择离终点距离最近的地方停下来。 （星际争霸中处于岛屿上的兵即采用这种算法）,路径查找,下面描述一下判断运动方向的问题。 下图是一个NPC可能遇到的方向情况,路径查找,当环绕障碍物行走时，先要判断当前障碍物相对于可移动物体的方向，标记为整数i (0-7)。例如：障碍物在可移动物体的正右方，就记作方向5。,路径查找,接着可移动物体依次查看方向j=(i+n) mod 8

6、(n=1.7)，直至发现方向j处无障碍物为止。若障碍物位于正上方（7），可移动物体首先看左上方向（0=（7+1）mod8）能否通过，如果不通就接着试左边方向（1=（7+2）mod8），还不行再依次按图上所示箭头试探其余几个方向，直至找到出口，并往该方向行走一步。,路径查找,若障碍物位于左下方（2），则依次按下方（3）、右下方（4）、右方（5）、右上方（6）、上方（7）、左上方（0）、左方（1）等七个方向查看是否有通路。至于障碍物相对于可移动物体的其他位置的处理，照此类推。,路径查找,重复步骤1、2，便能完成顺时针环绕障碍物行走。该算法详细的伪语言描述见下，反复调用函数ClockwiseWalk

7、OneStep即可顺时针绕障碍一周。 (算法参考教材) 这种方法比较简单，不适合更高的要求,路径查找,A*算法 A*算法与状态空间搜索相关紧密，所以先介绍状态空间搜索。 状态空间搜索，就是将问题求解过程表现为从初始状态到目标状态寻找这个路径的过程。通俗点说，就是在解一个问题时，找到一条解题的过程可以从求解的开始到问题的结果。,路径查找,由于求解问题的过程中分枝有很多，主要是求解过程中求解条件的不确定性，不完备性造成的，使得求解的路径很多这就构成了一个图，我们说这个图就是状态空间。 问题的求解实际上是在这个图中找到一条路径可以从开始到结果。这个寻找的过程就是状态空间搜索。,路径查找,常用的状态空

8、间搜索有深度优先和广度优先。 广度优先是从初始状态一层一层向下找，直到找到目标为止。深度优先是按照一定的顺序前查找完一个分支，再查找另一个分支，以至找到目标为止。这两种算法在数据结构书中都有描述，可以参看这些书得到更详细的解释。,路径查找,前面说的广度和深度优先搜索有一个很大的缺陷就是他们都是在一个给定的状态空间中穷举。这在状态空间不大的情况下是很合适的算法，可是当状态空间十分大，且不预侧的情况下就不可取了。他的效率实在太低，甚至不可完成。在这里就要用到启发式搜索了。,路径查找,启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省

9、略大量无谓的搜索路径，提到了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。我们先看看估价是如何表示的。,路径查找,启发中的估价是用估价函数表示的，如： f(n)=g(n)+h(n) 其中f(n)是节点n的估价函数，g(n)是在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。,路径查找,在这里主要是h(n)体现了搜索的启发信息，因为g(n)是已知的。换种说法，g(n)代表了搜索的广度的优先趋势。但是当h(n) g(n)时，可以省略g(n)，而提高效率。,路径查找,启发式搜索其实有很多的算法 局部择优搜索法 最好优先搜索法 A

10、* 这些算法都使用了启发函数，但在具体的选取最佳搜索节点时的策略不同,路径查找,像局部择优搜索法，就是在搜索的过程中选取“最佳节点”后舍弃其他的兄弟节点，父亲节点，而一直得搜索下去。这种搜索的结果很明显，由于舍弃了其他的节点，可能也把最好的节点都舍弃了，因为求解的最佳节点只是在该阶段的最佳并不一定是全局的最佳。,路径查找,最好优先就聪明多了，他在搜索时，便没有舍弃节点（除非该节点是死节点），在每一步的估价中都把当前的节点和以前的节点的估价值比较得到一个“最佳的节点”。这样可以有效的防止“最佳节点”的丢失。,路径查找,A*算法也是一种最好优先的算法。只不过要加上一些约束条件罢了。由于在一些问题求

11、解时，我们希望能够求解出状态空间搜索的最短路径，也就是用最快的方法求解问题，A*就是干这种事的！ 我们先下个定义，如果一个估价函数可以找出最短的路径，我们称之为具有可采纳性。,路径查找,A*算法是一个可采纳的最好优先算法。A*算法的估价函数可表示为： f(n)=g(n)+h(n) 这里，f(n)是估价函数，g(n)是起点到n的最短路径值，h(n)是n到目标的最短路径的启发值。由于这个f(n)其实是无法预先知道的，所以我们用前面的估价函数f(n)做近似。,路径查找,g(n) 代替g(n)，但 g(n)=g(n)才可（大多数情况下都是满足的，可以不用考虑）， h(n)代替h(n)，但h(n)=h(

12、n)才可（这一点特别的重要）。可以证明应用这样的估价函数是可以找到最短路径的， 也就是可采纳的。应用这种估价函数的最好优先算法就是A*算法。,路径查找,举一个例子，其实广度优先算法就是A*算法的特例。其中g(n)是节点所在的层数，h(n)=0,这种h(n)肯定小于h(n),所以由前述可知广度优先算法是一种可采纳的。实际也是。当然它是一种最臭的A*算法。,路径查找,A*算法是最好优先算法的一种，先看看最好优先算法的运算逻辑。如图有如下的状态空间：（起始位置是A，目标位置是P，字母后的数字表示节点的估价值）：,路径查找,路径查找,搜索过程中设置两个表：OPEN和CLOSED。OPEN表保存了所有已

13、生成而未考察的节点，CLOSED表中记录已访问过的节点。算法中有一步是根据估价函数重排OPEN表。这样循环中的每一步只考虑OPEN表中状态最好的节点。具体搜索过程如下：,路径查找,1.初始状态： OPEN=A5； CLOSED= 2.估算A5，取得所有子节点，并放入OPEN表中； OPEN=B4，C4，D6 ；CLOSED=A5 3.估算B4，取得所有子节点，并放入OPEN表中； OPEN=C4，E5，F5，D6 ； CLOSED=B4，A5,路径查找,4.估算C4，取得所有子节点，并放入OPEN表中； OPEN=H3，G4，E5，F5，D6 ； CLOSED=C4，B4，A5 5.估算H3，

14、取得所有子节点，并放入OPEN表中； OPEN=O2，P3，G4，E5，F5，D6 ； CLOSED=H3，C4，B4，A5,路径查找,6.估算O2，取得所有子节点，并放入OPEN表中； OPEN=P3，G4，E5，F5，D6 ；CLOSED=O2，H3，C4，B4，A5 7. 估算P3，已得到解,碰撞检测,刚才描述的算法只适用于单个可移动物体在静止的障碍物环境中生成行走路径。然而在实际的即时战略游戏中，经常是一群坦克在一个动态的地图上纵横驰骋，不同的坦克在行走过程中相遇互为障碍物，而且是可移动的障碍物。因此，必须对上面的算法作出修改使得物体在运动中避开可移动的障碍物。,碰撞检测,最直观的解决

15、方法是，一碰到可移动的障碍物，马上重新计算行走路径，该方法的缺点是重复计算路径、耗时太多。 其实，当某个物体碰撞到一个处于运动状态的可移动障碍物时，可以先等待一段时间，接着若发现可移动障碍物已挪开，就可以按原来的行走路径继续前进，从而节省了重复计算路径的时间,碰撞检测,反之，若发现可移动障碍物仍在原地，就比较两者的优先级（预先为每一个行走物体分配一个优先级），优先级较低则继续等待，优先级高者立刻重新计算行走路径避开可移动的障碍物。显然，运用该方法可以减少很多重复计算，加快了执行速度。,碰撞检测,上述算法中，可移动物体具有四种状态：Stillness, Run, FindNewPath, Mov

16、ing。,碰撞检测,在初始情况下，可移动物体处于Stillness状态。当接受指挥命令后，便进入了FindNewPath状态。一旦计算出行走路径，可移动物体就置为Run状态。在Run状态下，从行走路径列表中取出下一步的坐标，若该坐标所示位置无障碍物，状态变迁为Moving。,碰撞检测,进行前后两步间的坐标插值，结束后又回到Run状态；若发现原先计算出来的行走路径已经不适用了，便从Run状态转为FindNewPath状态,等找到新路径后，再恢复至Run状态。最后，当到达终点时，可移动物体的状态为Stillness。,碰撞检测,需要提出的是，除非特殊类型的游戏之外，目前的J2ME程序还不足以复杂到

17、需要采用碰撞检测的技术的地步。 在3D游戏设计中碰撞检测技术应用非常广泛，需要很多立体几何和解析几何知识。,人工智能,人工智能描述的是一台计算机上用于模拟逻辑思维和决策的技术。然而，在过去传统的人工智能中所使用的技术全都基于确定性算法，也就是使用基于属性的规则系统。,人工智能,这些系统基于“if.then.”结构。一个数据库，或是知识库是以信息的形式（这些信息在本性上彼此相关）创建的。随后，基于逻辑、语句、语法等等的规则被用于解决系统产生的问题。,人工智能,传统的人工智能系统存在的问题是它们几乎全部都是确定性的。尽管一些系统可以使用随即变量，在几乎相同的解答间进行选择，但是总的来说人工智能系统

18、不会以一个间接的方式提供没有被遗传过的东西。,人工智能,人工智能的“新”科学并不是以这种“干脆”的逻辑为基础的。细胞自动机、人造生命模糊逻辑、神经网、稀疏分布的存储器等的新发现都告诉我们思维并不是确定性的。有许多缺乏科学根据的随意性和个人偏好。,人工智能,例如，如果你们正在行走并选择一条特定的路，在这种情况下，你们肯定不会考虑正在行走的每一步。你们只知道有一个目的地，并且选择最佳的到达那里的方法。“最佳”就是一个难以琢磨的部分。,人工智能,你们的大脑怎样才能计算出“最佳”的路来呢？它是继续计算轨迹向量还是得到最短的路程呢？或是它是不是指给你们一个总的方向，然后当他感觉走错方向时再转向呢？基于这

19、些观察的问题和计算模型是人工智能新科学的基础。,人工智能,事实上，在游戏中的人工智能，并不一定是真正的人工智能 当然，它需要利用人工智能科学中的一些手段，比如模糊逻辑等等。,人工智能,但是游戏开发人员没有必要完全按照研究的模式，因为游戏设计人员能够“作弊”，因为开发人员了解目前游戏的状态，可以通过调整难度、调整精确度、调整敌人数量等方法，获得一种游戏的平衡，而看起来让玩家感觉到游戏的智能性。这是和人工智能研究不一样的地方。,人工智能,跟踪和躲避 在游戏术语中，AI大致上是用来描述一类问题很广的解决方法，这类问题即可以是角色扮演类游戏（RPG）中去模拟人作为某个角色的行为，也可以是即时战略游戏（

20、RTS）中的找路算法。,人工智能,在RTS类游戏中的主要的AI问题除了找路，团体AI和计算机对手的AI外，还有部队找路和部队的AI。计算机对手的AI本身也有好几部分：策略AI，战术AI，建筑布置，危险估计，地形分析等多方面。,人工智能,例如跟踪和躲避，可以经由下面的方式实现。 为了便于分析，我们可以使用一个游戏者和一个游戏对象或是游戏者对象的模型。问题是我们想使游戏者对手跟踪和追逐游戏者的角色。游戏者对手和游戏者的角色都有一个对坐标，指出它们各处于游戏中的什么位置。,人工智能,取得 （Px, Py） 玩家角色的位置 （Cx,Cy） 对手的位置 Begin / x tracking if (Px

21、Cx) then Cx+; else if (Px Cy) then Cy+; else if (Py Cy) Cy-; end,人工智能,由于我们获得游戏者角色和游戏者对手的位置，就可以使用这一信息为游戏者计算一个方向，就是它怎样移动才能接近游戏者的角色。因此，游戏者对手看起来就好象正在追逐游戏者的角色。上述算法使游戏者对手跟踪或攻击游戏者的角色。不管游戏者向哪个方向移动它。,人工智能,该算法直到游戏者对手处于游戏者角色的正上方时才停下来。它就像是一个跟踪导弹，直到击中你才会停下来。 在上面，可以做出进一步改进，我们可以增加如下的逻辑前提：当什么东西追赶你们时，它肯定是先看到你们。 （例如能

22、够主动攻击玩家的NPC）,人工智能,换句话说，它肯定在一定范围之内。考虑这种情况时，我们可以使用一个能见半径可以进行测试，看看游戏者对手是否处于游戏者角色的一定距离之内（其视觉范围还是感觉范围）。如果条件为真，我们则打开这个算法。否则可使游戏者对手做其他的事情，而不是追逐游戏者的角色，因为它根本就是无法看见游戏者的角色。,人工智能,追逐的反义词为逃避。逃避的做法与追逐相同，只不过一切都被颠倒过来进行。如果游戏者对手在游戏者角色的右边，游戏者对手则继续向右移动，而不是向左移动。 逃避的算法和追逐的算法类似,人工智能,模式 在一个游戏中使用模式是我们想做的事情。虽然一个游戏不应该总是基于模式的，但

23、是游戏应该有执行模式的能力，如选择一个方向，选择规则，选择一种行为。下面我们就来谈谈如何使用模式在屏幕上移动一个游戏者对手。我们甚至可从一组模式中选择拥有一个随机数的模式。,人工智能,所举的例子是大家熟悉的“小蜜蜂”，将游戏者角色置于屏幕的底部，将电脑控制的对手放在屏幕顶部并按照一定队形排列。我们也许想让游戏者对手执行一定的飞行模式 翻筋斗、旋转、分解和S形旋转等等 然后恢复原来的队形。要实现这些我们可以为游戏建立一个模式表，程序可从这个表中任意选择，然后程序将表用完。,人工智能,下面是我们使用到的表 （数组）： int patternsNUM_PATTERNSMAX_ PATTERNS_EL

24、EMENTS = 1，1，2，2，0，3，4，4，-1， 2，2，1，1，4，4，4，1，-1， 0，0，0，4，4，4，1，1，-1， 2，2，2，2，1，3，3，4，-1;,人工智能,正如你所看到，共有四个模式。每个模式最多包含5条指令。这些指令被转换成方向，然后被转换成实际的速率向量控制外来的机器人。,人工智能,在为“小蜜蜂”提供的模式装置中，程序读入表，然后基于当前表中的元素，向适当的方向移动机器人。模式装置可以理解6个值或指令。值1 4 分别为方向，北（N），南（S），东（E），西（W）。0的意思是不动，-1的意思是模式结束。,人工智能,模式的使用不仅可以只连接移动。模式可用于选择动

25、作、随机数等等。例如，可以使用一个模式作为随机数生成器的根源，以便于时间向前流动的时候，生成的随机数基于一个不同根值的模式。这会获得改变数的概率分布的效果，近而改变使用随机数的任何系统的行为。对于我们所制作的游戏大脑而言，我们使用模式仅作为移动顺序。然而，你们可使用它们提供任何你们希望的东西。,人工智能,有限状态机 通过有限状态机（Finite-State Machine）可以使系统从一种行为迁移至另一种行为，并且能够了解它正在执行的行为。,人工智能,有限状态机一般用于执行复杂逻辑的硬件设计中，有限状态机的概念在软件工程中也很有用。一个电脑游戏可有许多种操作模式 例如：初始化模式、正常模式及终止模式 有限状态机除了可以跟踪游戏的全部状态外，还可以跟踪这些模式。有限状态机还可以控制游戏中玩家的对手和游戏对象。,人工智能,例如，我们可以做一部跟踪玩家角色状态的有限状态机。角色可能有如下状态： 状态0：活着 状态1：奄奄一息 状态2：死亡,人工智能,基于这些状态，游戏中的控制逻辑可执行不同的事情，如果玩家角色处于状态0，逻辑将允许角色移动、开火等等。然而，如果角色处于1，游戏逻辑将显示死亡顺序，角色就不能再移动或开火了。最后，当状态切换到状态2时，游戏逻辑将仔细检查它使用什么样的顺序才能使玩家角色活过来。,人工智能,当然，还存在将玩家