>>>  創業先鋒 眾人拾柴火焰高  >>>

簡體     傳統

　　文 / Donald Kehoe

　　在《游戏行业的人工智能设计：AI的设计和实施》中，我们讨论了如何管理智能代理可能作出的基本决策——因为人工智能 (AI) 研究涉及到使用人工智能的实体。 在本文中，我为游戏男主角(或怪物或任何类型的游戏实体)作出的决策提供了一些背景。 智能代理需要确定游戏领域的兴趣点，然后明确如何达到目标。 最后，本文还将介绍如何优化这些方法并提供管理它们的方法，以说明多线程。

　　本文非常接近真正的人工智能 (AI)。 所有智能代理都需要具备感知环境的基本能力，并拥有在周围世界(无论是真实世界还是虚拟世界)中导航和移动的一些手段。 尽管方法有很大不同，但您的实体也需要具备这样的能力。 您也可以投机取巧，以确保一切快速顺畅地运行。

　　人工智能的感知方法

　　让代理作出武断决定适用于某些游戏，但如果您需要更多能力呢？ 如果您的代理将作出适当的决策，那么它需要了解周围发生的事情。 在人工智能的机器人应用中，做了大量关于计算机视觉方面的研究，为机器人提供了以真实、立体的三维 (3D) 视觉感知周围环境的能力，就像人类一样。这种成熟水平对于我们来说是完全多余的。

　　相较于真实世界的人工智能机器人，大多数游戏所用的虚拟世界拥有巨大优势。 我们世界中的一切都是已知量： 游戏中有一个列表，其中包含游戏里的一切。 您可以在这一列表中搜索任何标准，然后立即获取代理所用的信息，以制定更有意义的决策。

　　视觉

　　伪造实体视觉是为代理提供感知能力的最基本层次。 您可以通过在实体列表中搜索特定范围内的一切来做到这一点。 您既可以获取代理感兴趣的首要事件，也可以获取范围之内的事件列表，以便您的代理针对周围环境作出最佳决策。

　　这一设置适用于简单游戏，但当您的游戏风格较复杂时，如间谍游戏或第一人称的战术射击游戏 (FPS)，您的代理将需要在“看到”的内容上更具有选择性。 如果您不希望代理眼观四面，您可以针对超过实体视线范围之外的任意内容的潜力筛选出一个列表。 只需用一点数学知识就可以快速完成这一工作：

　　从代理的位置减去目标位置，计算考虑中的代理和实体之间的矢量。

　　计算矢量和代理所看方向之间的角度。(如果已经不是一个矢量，您也可以计算出数值)。

　　如果角度的绝对值大于代理的预设视角，您的代理看不到实体。

　　在较复杂的游戏中，您可能需要考虑某种遮蔽物隐藏的玩家或其他实体。 对于此类游戏，您可能需要执行光线追踪 (有时称为光线投射)，以了解是否有东西阻挡了潜在目标。 光线追踪是一种检查光线是否贯穿任何东西的数学方法，从一个点开始，以固定方向移动。 游戏引擎提供了光线追踪功能，但如果您想要了解其详情，请参见“三个臭皮匠抵一个诸葛亮”。

　　之前的方法告诉您是否有东西遮盖了目标中心，但可能不足以阻止您的代理。 有可能代理的中心被遮蔽，但代理的上部在遮蔽物上方伸出。 在目标上的特定关注点使用多个光线追踪不仅可以帮助确定 能否击中目标，还可以确定能够击中目标的哪个位置。

　　声音

　　乍看起来，它可能像是与视线无异的声音。 如果您可以看到实体，您肯定也能听到。 的确，如果您的代理发现了实体，代理可以主动检测实体所作的任何事情，直到从视线中完全消失。 但是，为代理添加额外的听觉水平可帮助视觉更有效地工作。 跟踪实体发出的作为感知水平的噪声对于任何隐蔽类游戏都至关重要。

　　和视觉一样，您需要获取一个附近实体的列表以便核对。 您可以再次通过简单的距离检查完成这项工作，但筛选这一列表的方式不同。

　　实体执行的每个操作需要有一些与其相关的声级。 您可以预设声级(以优化游戏平衡)，或者将操作所播放音效的实际能耗作为声级的基础。 如果产生的声音在阈值范围之内，您的代理将感知到该实体。

　　如果您想要考虑障碍，则可以再一次筛选这一列表：对环境执行光线追踪，了解是否有东西阻挡声音。 由于很少有材料是完全隔音的，因此您需要以更具创造性的方式从列表中删除实体。

　　其他感官

　　为代理提供视觉和听觉所需的基本功能可以很轻松地应用到模拟其他感官上。 这里有一个其他潜在感觉的列表，如果设计需要，您可以添加到游戏中：

　　味觉。使命召唤 4*等最近推出的游戏中添加了让智能代理按照嗅觉跟踪玩家的概念。 为游戏添加气味相对简单： 为游戏中的每个实体提供一个不同的气味编号和强度。 气味强度决定着两个因素：气味的半径和留下的气味线索的大小。 活跃的玩家实体通常会出于一些原因记录其最后的几个位置(本文稍后将在线索中介绍更多信息)。 其中一个原因是帮助有气味的实体。 随着玩家实体更新线索，气味的强度随着线索的”淡化“而逐步减小。 当更新有气味的代理时，它需要像检查声音那样检查气味：检查半径和墙面。 有了气味，成功的因素便立足于气味的强度和代理的嗅觉，这些将对照实体和实体的线索进行检查。

　　雷达。有些游戏为玩家提供个人雷达，这使得感知变得更简单。 只需一个简单的半径检查即可。 随后人工智能便可以验证结果，了解其影响。 对于团队游戏，雷达本身可以变得更加有趣。 为了汇总基于团队的人工智能，每个团队需要制定一个包含雷达发现的实体的雷达列表。 然后团队的每个成员便可以只针对已知实体的列表执行半径检查，以确定团队是否应该做出响应。 团队可以使用雷达设备(如深入敌后： 雷神战争*游戏中)，按照添加“看到”的任何内容的每个团队编号添加至列表中。 这一行为可帮助实体作为一个部队工作，因为每个实体都会将其看到的内容告知其他实体。

　　触摸。这种感觉比较轻而易举，因为游戏引擎的碰撞系统会自动涵盖它。 您只需确保智能代理能够响应损坏和碰撞事件即可。

　　味觉。我不确定这种感觉如何运作。 它可能是气味的一种属性，但需要代理主动“品尝”其发现的东西。

　　能够感知周围世界当然很好，但代理应该感知到什么呢？ 您需要指定并能够确定通过代理的设置进行观察的事物。 当您认出看到的事物，您的代理可以根据管理实体的规则对其作出响应。

　　临时实体

　　临时实体有时也称为粒子、贴标或特效，是游戏世界中的视觉效果。 它们与实体类似，因为一个总体类结构定义所有潜在临时实体，但它们又不同于实体，因为它们不思考和响应游戏世界中的实体，也不与实体互动或相互响应或互动。 他们唯一的目的就是为了美观，在一段时间内为游戏世界提供额外细节，然后就会死去。 临时实体用于子弹轨迹、烟雾、火花、血喷甚至脚印等事物。

　　临时实体的性质意味着处理很少且无碰撞检测(超出非常简单的世界碰撞)。 问题在于，有些临时实体为玩家提供了有关已发生事件的视觉线索(弹孔和烧伤痕迹表示最近发生过战斗，雪地上的脚印可帮助找到潜在目标)，那么为何您的智能代理也不能使用它呢？

　　此问题有两种解决方法： 您既可以通过增强临时实体系统来支持光线追踪(会破坏一个临时实体系统的整点)，也可以在临时实体的一般临近区域投下一个空实体。 这一空白实体没有思考能力，也没有与其相关的图像，但您的代理能够检测到它，并且临时实体拥有为代理提供“英特尔”的相关信息。 因此，当一滩散血效果掉落在地上时，您可以在那里投下一个无形实体，让您的代理知道有不寻常的事情发生了。 对于脚印的问题，您已经有掩护它的线索了。

　　掩护

　　在很多射击游戏中，如果您的代理可以聪明地躲在掩护后面，而不是只是站在空地处等着被击中，那真是太好了。 这个问题比我之前介绍的其他问题更专业一些。 您的代理如何确定是否有可以躲藏的可用掩护？

Penny Arcade* 讽刺了敌人人工智能和掩护物的问题。

　　实际上，这一窘境是两个问题： 如何从实际几何结构方面确定掩护物，以及如何从实际实体方面确定掩护物(如上述的漫画所示)。 如要确定一个实体是否能够阻挡攻击，您可以简单地验证一下，比较一下选中的掩护物的边框尺寸。 然后，验证一下您的实体是否能够躲在它后面。 验证方法是，从射击者和掩护物的不同位置创建一束光。 利用这束光来确定(从射击者)穿过掩护物的点是否不会造成影响，然后将该区域标记为代理的下一个目标。

在本示例中，代理确定了绿星是能够避开伤害的安全点。

　　AI 导航

　　目前为止，我已经聊了许多人工智能如何做决定及其如何知道将会发生什么(以便做出更好的决定)。 现在，我们来了解一下人工智能如何执行这些决定。 接下来是要确定如何从 A 点到 B 点。您可以使用多种方法，具体取决于游戏的性质和性能需求的级别。

　　碰撞和转弯

　　碰撞和转弯是产生实体运动最基本的方式之一。 下面介绍一下它的工作原理：

　　在目标方向移动。

　　如果撞到一面墙，转向让你距离目标最近的方向。 如果没有明显更好的选择，请随机选择一个。

　　这种方法对于简单的游戏非常有效。 数不胜数的游戏使用这种方法来控制怪兽如何追赶玩家。 碰撞和转弯导致实体在追赶玩家时卡在凹陷的墙或角落中，因此，对于有僵尸或没有这种地貌的游戏，这种方法非常理想。

　　但是，如果游戏要求代理更机敏，您可以对简单的碰撞和转弯进行更详细地介绍，为您的代理赋予一些记忆。 如果代理能够记住他们到过哪里，则可对如何转弯做出更有意义的决定。 转完所有弯后，代理将可原路返回，做不同的决定。 因此，您的代理能够系统搜索一个目标的路线。 下面介绍一下它的工作原理：

　　向目标移动。

　　遇到叉路时做选择。

　　发现死路时，原路返回到上一选择，再做其他选择。

　　探索全部可行路线后，放弃。

　　这种方法在处理方面不会耗费大量资源，这表示，您支持大量代理也不会降低游戏速度。 这种方法还非常适合处理多线程。 这种方法的缺点是会浪费大量空间，因为每位代理都可能会追踪包括全部可行路线在内的整个地图。

　　幸运的是，让代理在共享内存中记录路线，将可避免这一浪费。 但是，可能会产生线程冲突的问题;因此需要将实体路线保存在一个所有代理都能够在移动时向其发送请求，在发现新路线时向其发送更新的单独模块中。 然后，路线地图模块还需要能够解析发现的路线，以避免出现冲突。

　　路线查找

　　通过碰撞和转弯生成地图是适应不断变化的地图的好方法。 在策略游戏中，玩家不能坐等设备来查找他们的方位。 而且，这些路线图可能会变得非常庞大，这样，在其中搜寻正确的路线将会成为瓶颈。 查找救援路线。

　　路线查找问题在游戏开发中基本上已经解决。 像最初的星际争霸 (Starcraft)* (美国暴雪娱乐公司 (Blizzard Entertainment*))一样老的游戏都可以处理大量游戏实体，在大型的复杂地图中找到道路。

　　查找路线的核心算法是 'A*' (读为 [ə; stɑː])，可用于查找图表(在本案例中为地图)上任意两点间的最佳路线。 进行简单的在线查找即可发现包含 F、G 和 H 等描述性术语的 clean 算法。 请允许我更清楚地解释一下。

　　首先，必须建立两个列表：一个包含尚未核实的节点的列表(未核实)，一个包含已核实的节点的列表(已核实)。 每个列表包含一个位置节点、与目标之间的预估距离及其母节点(确保其位于列表中的节点)的参数。 列表最初为空。

　　接下来，将起点添加到未核实列表中，无母节点。 然后，输入算法：

　　从列表中选择外观最佳的节点。

　　如果该节点是目标，则操作即可完成。

　　如果该节点不是目标，则需要将其添加至已核实列表。

　　对于与该节点相邻的每个节点：

　　如果节点无法行走，则忽略它。

　　如果节点已在列表中(无论是已核实或未核实)，则忽略它。

　　接下来，将其添加到未核实列表中，将该节点设置为母节点，并预估其到目标的距离(粗略的距离检查即可)。

　　实体到达目标图块后，通过追踪不包含母节点的母节点(起始节点)即可构建路线。 这可为实体提供最佳路线，以便其进行查找。 由于该流程仅当代理收到命令或自行决定运动时才会发生，所以它能够从多线程处理获得巨大益处。 代理可以发送路线线程请求，当系统发现该路线时便会向代理提供，而不会影响人工智能的性能。 大多数情况下，系统可以快速获取结果;但是如果有大量路线请求负载，代理便只能空等，或向适合的方向行进(它可能可以使用碰撞和转弯的方法)。 在极大型的地图中，系统可以划分为多个区域，区域间的所有可行路线(或停留点)均可提前进行计算。 在这种情况下，查找路线的人仅需查找最佳路线即可，因而能够快速获得结果。 路线地图仅需关注地图上的变化即可，如当玩家建造了一面墙，仅需根据需要重新运行路线检查即可。 算法使用单独的线程运算，因此可轻松调整，而不会影响游戏中其他部分的性能。

　　在路线查找子系统中，多线程处理还可提高系统的性能。 它非常适合实时策略 (RTS) 游戏，或包含大量实体且每个实体都在寻找不同路线的系统。 可同时在不同线程内查找到多条路线。 当然，系统需要记录发现的路线。 同一条路线无需多次发现。

　　代码示例

　　以下展示了一个仅在 C 语言中部署的 A* 示例。简便起见，我在示例中并未考虑支持函数，因为它们需要针对不同的部署风格进行定制。 本示例基于一个简单的 tile 网格，其中每个 tile 都可以进一步处理，也可不处理。 这仅允许移动到相邻 tile，但是，如果进行微小的改动，便能够允许作对角移动，或者六角形游戏布局。

1. /*Get Path will return -1 on failure or a number on distance to path
   

2. if a path is found, the array pointed to by path will be set with the path in Points*/
   

3. int GetPath(int sx,int sy,int gx,int gy,int team,Point *path,int pathlen)
   

4. {
   

5. int u,i,p;
   

6. memset(&Checked,0,sizeof(Checked));
   

7. memset(&Unchecked,0,sizeof(Unchecked));
   

8. Unchecked[0].s.x = sx;
   

9. Unchecked[0].s.y = sy;
   

10. Unchecked[0].d = abs(sx - gx) + abs(sy - gy);
    

11. Unchecked[0].p.x = -1;
    

12. Unchecked[0].p.y = -1;
    

13. Unchecked[0].used = 1;
    

14. Unchecked[0].steps = 0;

　　上述代码段可处理已验证和未验证列表的初始化，并将起始节点放入未验证列表。 借助此代码集，算法的其他部分可在循环中运行。

1. do
   

2. {
   

3. u = GetBestUnchecked();
   

4. /*add */
   

5. AddtoList(Checked,Unchecked[u]);
   

6. if((Unchecked[u].s.x == gx)&&(Unchecked[u].s.y == gy))
   

7. {
   

8. break;
   

9. }

　　上述代码段展示了未验证列表中距离目标最近的节点。GetBestUnchecked()可用于验证每个节点与目标之间的预估距离。 如果该 tile 是目标，则循环停止，流程完成。

　　下文展示了距离的算法：获取 X 和 Y 方向上与目标之间的预估距离，并将其相加。 一开始，您可能会想使用勾股定理 (a^2 + b^2 = c^2 )，但是完全没必要。 您只需要相对距离，而非确切距离。 处理器处理加减运算的速度比处理乘运算的速度快许多倍，而处理处理乘运算的速度比处理除运算的速度快许多倍。 由于该代码段在一帧中将会处理许多次，所以优化是关键。

1. /*tile to the left*/
   

2. if((Unchecked[u].s.x - 1) >= 0)/*first, make sure we're on the map*/
   

3. {
   

4. if((IsInList(Unchecked,Unchecked[u].s.x - 1,Unchecked[u].s.y,NULL) == 0)&&(IsInList(Checked,Unchecked[u].s.x - 1,Unchecked[u].s.y,NULL) == 0))
   

5. /*make sure we don't repeat a search*/
   

6. {
   

7. if(TileValid(Unchecked[u].s.x - 1,Unchecked[u].s.y,team))
   

8. NewtoList(Unchecked,Unchecked[u].s.x - 1,Unchecked[u].s.y, Unchecked[u].s.x, Unchecked[u].s.y, abs((Unchecked[u].s.x - 1) - gx) + abs(Unchecked[u].s.y - gy), Unchecked[u].steps + 1);
   

9. }
   

10. }

　　在上述代码段中，该函数在当前节点的左侧处理 tile。 如果它未添加到已验证或未验证列表中，系统将会尝试将其添加至列表。 TileValid() 是另一个需要定制以满足游戏需求的函数。 如果它通过 TileValid() 验证，将会调用 NewToList()，这将会向未验证列表中添加一个新 tile。 以下三个代码段执行相同的流程，但是指称不同的方向：右、上和下。

1. /*tile to the right*/
   

2. if((Unchecked[u].s.x + 1) < WIDTH)/*first, make sure we're on the map*/
   

3. {
   

4. if((IsInList(Unchecked,Unchecked[u].s.x + 1,Unchecked[u].s.y,NULL) == 0)&&(IsInList(Checked,Unchecked[u].s.x + 1,Unchecked[u].s.y,NULL) == 0))
   

5. /*make sure we don't repeat a search*/
   

6. {
   

7. if(TileValid(Unchecked[u].s.x + 1,Unchecked[u].s.y,team))
   

8. NewtoList(Unchecked,Unchecked[u].s.x + 1,Unchecked[u].s.y, Unchecked[u].s.x, Unchecked[u].s.y, abs((Unchecked[u].s.x + 1) - gx) + abs(Unchecked[u].s.y - gy), Unchecked[u].steps + 1);
   

9. }
   

10. }
    

11. /*tile below*/
    

12. if((Unchecked[u].s.y + 1) < HEIGHT)/*first, make sure we're on the map*/
    

13. {
    

14. if((IsInList(Unchecked,Unchecked[u].s.x ,Unchecked[u].s.y + 1,NULL) == 0)&&(IsInList(Checked,Unchecked[u].s.x,Unchecked[u].s.y + 1,NULL) == 0))
    

15. /*make sure we don't repeat a search*/
    

16. {
    

17. if(TileValid(Unchecked[u].s.x,Unchecked[u].s.y + 1,team))
    

18. NewtoList(Unchecked,Unchecked[u].s.x,Unchecked[u].s.y + 1, Unchecked[u].s.x, Unchecked[u].s.y, abs(Unchecked[u].s.x - gx) + abs((Unchecked[u].s.y + 1) - gy), Unchecked[u].steps + 1);
    

19. }
    

20. }
    

21. /*tile above*/
    

22. if((Unchecked[u].s.y - 1) >= 0)/*first, make sure we're on the map*/
    

23. {
    

24. if((IsInList(Unchecked,Unchecked[u].s.x ,Unchecked[u].s.y - 1,NULL) == 0)&&(IsInList(Checked,Unchecked[u].s.x,Unchecked[u].s.y - 1,NULL) == 0))
    

25. /*make sure we don't repeat a search*/
    

26. {
    

27. if(TileValid(Unchecked[u].s.x,Unchecked[u].s.y - 1,team))
    

28. NewtoList(Unchecked,Unchecked[u].s.x,Unchecked[u].s.y - 1, Unchecked[u].s.x, Unchecked[u].s.y, abs(Unchecked[u].s.x - gx) + abs((Unchecked[u].s.y - 1) - gy), Unchecked[u].steps + 1);
    

29. }
    

30. }
    

31. memset(&Unchecked[u],0,sizeof(PNode));

　　该迭代中需要做的最后一件事情是将未验证列表从当前代码中删除。 不再需要该 tile。

1. }
   

2. while(1);

　　最后一段代码可通过从目标原路返回来构建路线。 一定能够找到返回起始位置的路线，因为路线中的每个代码都会记录将其放入列表中的代码。 然后，返回最终路线(通过参数)。 以下函数可返回新路线的长度。

1. IsInList(Checked,Unchecked[u].s.x,Unchecked[u].s.y,&u);
   

2. p = Checked[u].steps;
   

3. if(path != NULL)
   

4. {
   

5. for(i = (p - 1);i >= 0;i--)
   

6. {
   

7. path[i].x = Checked[u].s.x;
   

8. path[i].y = Checked[u].s.y;
   

9. IsInList(Checked,Checked[u].p.x,Checked[u].p.y,&u);
   

10. }
    

11. }
    

12. return p;
    

13. }

　　总结

　　智能代理需要观察其周围的世界。 可以使用简单的范围检查和光纤追踪使根据视觉和听觉所做的观察快速成形，帮助代理在游戏过程中以更贴近人类思维的方式做决定。 确定目标后，代理需要寻找路线，去往他们想去的地方。 碰撞和转弯等快速方式适用于短期任务和简单地图，而更复杂的游戏需要分析地图来查找最佳路线。 您可以对这些方法进行优化，以充分利用多线程部署，确保游戏流畅运行，即使需要处理大量实体和复杂地图也是如此。

英特尔开发人员专区 授权

GameRes游资网 2015-08-23 08:54:39