游戏人工智能底层设计初窥（ZT）
帖子有些年头了，看过的请飘过《分裂细胞·明日潘多拉》AI开发体会
2004年3月，由上海育碧（Ubisoft Shanghai）担纲开发的游戏《分裂细胞·明日潘多拉》（Splinter Cell: Pandora Tomorrow）终于与玩家见面了。这款游戏是由顶尖军事小说作家汤姆·克兰西（Tom Clancy）作品改编的畅销游戏系列《分裂细胞》的第二作，它也被有些游戏杂志称为“第一款由国人开发并具有世界级水准的游戏”。
1.jpg
2003年5月，我加入了《分裂细胞·明日潘多拉》的团队，并有幸作为开发组的一员参与了游戏中人工智能和游戏流程的全程开发。现在回想起来，这款游戏的成功开发对于我此后的工作有着深远影响，因此希望通过本文与大家共享我的开发体会。
《明日潘多拉》的前身，也就是《分裂细胞》一代，创造了非常出色的市场销售成绩。《明日潘多拉》作为第二代，必须达到并超越第一代的水准，这给我们带来了一定的压力，同时也带来了无穷动力。当然，压力还来自于紧张的开发进度要求，因为上海育碧是法国 Ubisoft 在中国的全资子公司，而且Ubisoft又是上市公司，所以上海育碧的游戏开发计划跟法国上市企业公布季报、年报的周期是密切相关的。一般说来，公司公布年报的周期也就是公司财政年度的开始和截止时间，即上一年的三月到下一年的三月，所以大多数游戏的开发（特别是大制作的游戏）也是从三月份开始的。《明日潘多拉》就是一个典型的从上一年三月开始到次年三月上市的游戏。为了在短短一年内开发出高品质的《分裂细胞》二代，团队里的大多数成员都必须具备丰富经验，尤其是软件工程师。
与一代相同，我们沿用了美国Epic公司的Unreal游戏引擎。Unreal引擎是个很成熟的FPS游戏引擎（其新近加入了一些适应MMORPG要求的功能），它不仅为软件工程师提供成熟的3D图形渲染流水线，游戏手柄输入支持以及初级物理功能，也为关卡设计师（Level Designer）、美工（Artist）和动画师（Animator）等提供了操作方便的关卡编辑器、材质编辑器、模型浏览器和动画浏览器。Unreal更是一个完善的游戏开发环境，是游戏开发流程中具有关键地位的工具——而且是完备好用的工具。即便是游戏玩家，在熟悉UnrealEd关卡编辑器的功能之后，也能够在较短的时间里制作出支持多人联机对战的简单FPS游戏mod（前提是游戏里面的各种贴图、模型和动画都已经做好了）。Unreal引擎的功能之全面，工具之成熟易用，由此已经可窥一斑。但为了制作一款像《明日潘多拉》这样的大型游戏，类似只用编辑器做几个地图的小伎俩是无济于事的，而对游戏引擎作一定的修改与改进则是十分必要的。《分裂细胞》一代的开发团队为了适应游戏要求，已经对游戏引擎作了一些修改，而现在负责二代开发的我们则要往这个引擎中加入更强大的功能——在《明日潘多拉》中将要用到的特殊功能。
在游戏所有的功能模块中，人工智能将是决定游戏“好玩”与否的重要因素。若论及游戏的人工智能，则不能不说到碰撞检测、寻路算法和动画播放这三大瓶颈问题。进一步说，若一款游戏中的这三个方面有明显缺陷，则肯定无法高质量实现“逼真”的人工智能。
2.jpg
基于八叉树空间划分的碰撞检测系统
在游戏开发的前期，我评估了我们所使用的引擎的碰撞检测系统（Collision Detection System）。当时我们的碰撞检测还是以散列表（也叫哈希表）为基础的Collision Hash，此系统的基本思路是把整个游戏空间一次性划分成多个固定尺寸的立方体。游戏中的对象，无论是人物角色，还是物体模型，甚至是虽无形但具备碰撞检测能力的对象（例如玩家进入就会触发事件的区域）都会被存储在一张全局散列表（Global Hash Table）之中。散列函数（Hash Function）的选择在这里是极其重要的。每个立方体占据的游戏空间对应于散列表中的一项，每一个表项里存放的是这个立方体里所有物体的链表指针。如果有某个物体跨越立方体的边界，那么多个立方体的表项的链表里面都将包含这个物体的指针。
如果一个物体发生了移动，我们就要做几件事情：
第一步：游戏引擎根据该物体的当前位置和目标位置以及该物体扫过的空间体积（扫掠体Swept）的横截面积，来判断在本次运动中它会与哪几个空间立方体发生碰撞。
第二步：在散列表中查到这几个空间立方体所对应的物体链表，检测该物体是否会与这些链表内的任何物体发生碰撞。这一步可以采用简化模型进行，比如用一个只有几百个面的外包多面体来代替一个成千上万面的精细物体。这样做的结果是大大提高了速度，但是美中不足也略微降低了精度，不过最终这种平衡的结果是整体速度的大幅提高。当然，这些简化模型是事先由美工做好的，在地图数据存储的时候就与物体相关联，因此也可以说这是用人力成本换取游戏的执行效率。
第三步：对发生碰撞的物体，逐个多边形地进行碰撞检测，以便获得碰撞具体发生的位置和碰撞发生所涉及多边形的法线朝向。这一步的计算就比较基础了，一般是直线跟三角形的相交位置计算，或者是三角形与三角形的相交位置计算。
第四步：根据所获得的碰撞位置和法线朝向，我们确定了参与碰撞运动的物体的新位置，如果条件巧合，也有可能发生物体在碰撞发生位置停住的情况。
第五步：我们根据物体的新位置更新它在散列表中的信息，因为它现在可能已经从一个空间立方体进入到了另一个空间立方体。我们要把它从原来立方体所对应的散列表项所指向的物体指针链表中删除，并将其加入到新的立方体对应的散列表项所指向的物体指针链表中。
即便完成了这五步，也只是完成了碰撞检测中的最基本运算。由于发生碰撞而导致游戏运行状态发生改变——上述的描述并未涉及这方面，而这方面是视游戏的具体内容而定的，因此不在本文的讨论范围之内。以上描述的散列表和固定网格的空间划分是有效的，也是成熟的算法，但是Xbox和PS2的有限机能和内存限制使我们必须寻找更好的算法。因此在散列表的基础上再作优化意义已经不大，不过有没有更好的算法呢？
http://bbs.shuzifun.com/attachments/forumid_36/20081106_657ea98c0c82b4d43167Qq9Gk7ixu9TD.jpg
3.jpg
于是我们很快想到了八叉树（Octree）算法。与基于散列表的算法不同，八叉树算法对空间的分割是分层次（Hierarchical）的：整个空间是第一层；然后xyz三根轴将整个空间分成八个卦限（Octant），也就是八个部分，这是第二层；而后第二层的每一卦又被分成八份，成为第三层……这个划分一直进行下去，直到所分的每份空间足够小或者每份空间仅包含一个物体为止。
在这个例子里面整个空间是树根，每一个叶节点所对应的空间都只包含一个物体。在进行碰撞检测时，检查是从第一层开始，逐层向下进行的（宽度优先）。在接触到叶节点之前，检查始终都是对中间的节点进行的，中间节点的碰撞检测效率很高，因为它们都是很规则的正方体或长方体。
6.jpg
为了对比散列表法和八叉树法，现在我们假设一个散列表的固定网格空间划分，把空间划分为一个个如上面八叉树第三层的大小的立方体。现在我们假设物体在移动中与Object2对象发生碰撞。
找到Object2的时间，等于：
散列表散列函数运算时间 + 在物体链表中查找这个物体的时间。
八叉树从树根到叶节点的搜索时间。
7.jpg
因此当每个散列表表项所指物体链表中只有一个物体时，散列表法的算法复杂度为常数；而当散列表表项所指物体链表中的物体数增加时，散列表法的算法复杂度向O(N)过渡。对比八叉树法的时间复杂度O(logN)，我们可以看到，在某些情况下散列表的效率优于八叉树，但是某些情况下则又不如八叉树。这带来了两个问题：一个是物体的大小和位置在用散列表法的时候是有讲究的，另一个是散列表法在某些情况下的不佳表现可能会带来游戏帧数的不稳定。而这两个问题八叉树法都自动避免了。
8.jpg
让我们再来看看上图中的Object4，由于它占满了八叉树第三层的八个卦限，于是我们直接把它放在第二层的节点上。如果对散列表和八叉树做跟上面的例子相同的假设，散列表法要把这八个卦限对应的八个立方体全都搜索一遍，因为这八个立方体对应的散列表项的物体链表里面都有Object4。而用八叉树方法只有第二层的Octant8被搜索了，这就大大提高了效率。所以在大量物体跨越散列表的空间划分边界的时候，八叉树法效率更高。在八叉树的数据结构中Object4的指针只被存储了一次，而在散列表方法重要被存储八次，由此看来两种方法的内存占用量有着天壤之别。
我们已经做了很多实验来比较散列表和八叉树的综合性能，并且发现它们在《明日潘多拉》的游戏关卡中：两者的速度处在同一个数量级上，不过散列表稍快一点。然而，在内存的占用上八叉树具有明显优势，比散列表小一个数量级！这很好地印证了我们上面的分析。作为一款为游戏机开发的游戏软件，内存永远都是一个瓶颈，而八叉树在节约内存开销方面的优势终于促使我们下定决心使用它，这个决定在后来被证明是明智的。
9.jpg
基于路点的寻路系统
在《明日潘多拉》里面我们使用的是基于路点（Path Nodes）的寻路系统。这个系统的思想简单明了，即把很多个路点放置在NPC可能会经过的地方，然后把相邻的路点都连接起来。这样这些路点就形成了一张网络（无向图），覆盖整个游戏关卡。一旦NPC的高层AI决定了目的地，就要首先找到离目的地最近的路点的位置，然后用A*算法计算出要到达目标路点的必经路径，接下来沿着这一条路径逐帧向目标前进。这个思想虽然简洁优美，但在实际的游戏关卡里却有很多特殊情况，所以必须做很多其它工作才能保证A*算法正常工作。由于路点的连接是在游戏程序运行之前就已经预先计算好的，并没有考虑到在游戏过程中由于其它NPC的阻挡或某些物体的移动而使得某一条路线被阻断的情况。于是你可能会看到某个NPC站在其它NPC的巡逻路线上，而后者却在不停地试图挤过（或穿过）前者的情况。为了解决此类问题，我们在NPC的移动代码里实现了对路线上的障碍物进行实时检测和躲避的算法。
4.jpg
路点法虽然概念很简单，但让NPC灵巧地绕过障碍物却是很复杂的过程。也许出乎你的意料，躲避障碍物的算法有时会比一个标准寻路算法还要复杂。比如当几个NPC在同一个狭窄的走廊里相遇，一般情况是由于碰撞检测的存在使他们都认为别人挡住了去路，所以他们就都停在那里等别人走开，在玩家眼里NPC好像都变成了傻瓜一般。同类问题会在各类场景中出现，不论是丁字路口或十字路口。解决类似问题的方法是困难而复杂的。在另外一些情况下，由于关卡中的特殊结构，仅仅依赖路点是无法保证NPC寻路总能得出正确的结果。例如一个NPC要乘电梯到另一层楼面，然后再跑到某个目的地。
11.jpg
由于两层楼面的路点并不是相互连接的，这就要求在代码里对电梯作特殊处理，使NPC觉得两层楼面的路点是连接在一起的，从而完成寻路过程。因此尽管同样是基于路点的寻路系统，当开发不同的游戏时，问题的复杂度仍可能相去甚远。一个场景中如果有很多门、楼梯、电梯、地道的游戏寻路代码，会远比另一个主要是室外开放场景的游戏复杂。若是不能认识到这种复杂度，就可能无法制定有效的开发计划和分配适合游戏实际需要的足够的开发资源。从《分裂细胞》三代，即《混沌理论》（Chaos Theory）开始，我们使用一种更好的寻路方式——导航网络（Navigational Mesh）。
导航网络与路点系统相比，主要有三大优势：能覆盖关卡全部面积、NPC的路线更加平滑、控制NPC在特定区域的行为更容易。
骨架动画系统
5.jpg
我们在《明日潘多拉》里使用的动画系统是基于骨架的。NPC和游戏主角的所有动作，包括走、跑、跳、爬等，都是通过对人物骨架上每一根骨头的位置和朝向（Position & Orientation）的精确控制而实现的。这些骨头的位置和朝向可以用三维动画软件例如3Dmax、Maya或Motion Builder事先算好，再导入UnrealEd编辑器里。
在游戏中，人工智能的高层逻辑模块先决定要播放什么动画，然后在底层的播放模块里逐帧读取基于关键帧的动画数据，并在相邻的关键帧之间进行插值，求出当前帧的骨架上各块骨头的位置和朝向，最后在骨架上蒙皮（Skinning）并贴上纹理（Texturing），于是人物在当前帧的新姿势就出现了。在使用这种动画系统的时候，骨架的通用性是很重要的。比如所有的NPC都使用同样的骨架结构，骨头数量也要相同。如果有两个NPC的骨架结构不同，或者骨头数量不同，就要为这两个NPC做两套动画数据，这样动画师的工作量就翻番了。
但是仅有单个的各种动作的动画显然是不够的，因为不管什么时候，游戏动画都要求平滑流畅，若只是将这些相互独立的动画连起来播放是不能达到这个要求的。当上一个被播放动画的最后一帧与当前正在播放的动画的第一帧的角色姿态明显不同时，就会导致在这两个动画之间切换过程中人物姿态发生明显的抖动。比较常见的例子是玩家控制的角色起动（从走到跑），制动（从跑到走）或在行进中进行转身等各种单纯动作，在玩家看到的人物姿势里都要体现出来。为了在《明日潘多拉》里满足这个需求，我们给每个人物动画使用了许多个动画通道（Channel），每个通道都有一个Alpha值与之对应。在每一个通道中进行一个动画的播放，则最后人物动作的结果就是所有通道动画的叠加。一个动画通道的Alpha值如果为1，那么该通道的动画就会全部体现在最后的动作中；如果Alpha值为0，该通道的动画就不出现在最后的动作中；如果值在0到1之间，该通道的动画则会部分地体现在最后的动作中。在任一瞬间，每个动画通道至多有一个动画在播放。动画通道的编号从0到255，0号通道与1号通道叠加的结果再与2号通道叠加，产生前三个通道叠加的结果；这个结果再与4号通道叠加，产生前四个通道叠加的结果……
在游戏的某一时刻，如果在各个通道里面播放的动画不同，人物的姿态就是由数个正在不同通道分别播放的动画组合而成，这个组合过程叫做动画的混合（Animation Blending）。有些通道只播放基本动作；有些通道的Alpha值不断增大或减小，从而产生一个动作到另一个动作的自然过渡；还有的通道只负责播放人物端着武器的姿势等等，不一而足。由于NPC的智能程度主要通过动画表现出来的，而游戏主角的各种很酷的姿势和动作也是通过动画表现出来的，因此动画播放是至关重要的。于是在游戏里，动画数据本身的质量和动画播放的质量在极大程度上影响着玩家对三维游戏的整体感觉。
动画与其它游戏引擎部分的接口也是相当重要的。比如在走路的动画中，当脚一落地便要适时地播放脚步声，当拔枪的手运动到身体前方就要及时把手枪放到玩家或者NPC的手里等等。为了实现这种与引擎其它部分的接口，我们在动画数据中加入notify。每一个notify实际上都是一个脚本语言回调函数的函数名，有的函数负责播放声音，还有的函数负责把手枪等物体放到玩家或NPC手里等。这样我们就实现了游戏引擎中其它模块与动画播放的同步。
游戏AI是一个复杂的系统，随着新游戏的推出，游戏AI的复杂度更是水涨船高。对于将来的游戏，实现绚烂的3D画面不再是太大的难题，优秀游戏的核心竞争力将主要体现在AI上。本文粗略的描述了一下《分裂细胞·明日潘多拉》中几个最重要的底层AI模块，以及它们的实现方法。在今后的文章中我们会继续向大家介绍《明日潘多拉》中高层AI的设计思路和实现算法，请大家继续关注。 高手！膜拜膜拜
我看ps3里的欧美游戏很多很多都是射击枪杀暴力游戏 宝贵的经验之谈啊 回复 呆呆星人 的帖子
{:3_140:} 高手！膜拜膜拜
斑竹大人辛苦了
页:
[1]