设计面向游戏的人工智能(第 4 部分)

作者:Donald Kehoe

发挥人工智能的最大价值:线程化


之前的所有本系列文章一直都在为本文奠定基础。我们希望,您现在能够清楚地了解到游戏人工智能 (AI) 是什么,并知道如何将其用于您的游戏中。如今,极具挑战性的任务是,最大程度地提升您系统的性能。

无论您的系统有多好,但若它拖慢游戏速度,则一切毫无意义。高效的编程和优化窍门所起作用比较有限;若您的目标超出了单内核的限制,那么您只能进行并行处理(见图 1)。



图 1:在 Blizzard Entertainment 的《星际争霸 2》* 中,大量单元在同一时间运行自己的人工智能。多线程是最佳的处理方法。

若进行处理时所用的系统具有一颗以上处理器或一颗多核处理器,您可将工作分配给多颗处理器。有两种分配方式:任务并行化和数据并行化。


任务并行化


将您的应用进行多线程化处理的最轻松方法是,将它分解为多个特定的任务(见图 2)。我们通常只使用几种方法对组成游戏引擎的不同任务进行封装,以便其它系统可与它们进行通信。



图 2:功能并行化让每个子系统利用各自的线程和内核。遗憾的是,具有多个内核而非任务的系统并未得到充分利用。

一个最好的例子是,该游戏引擎的音频系统。音频不需要与其它系统进行交互。它只是按照命令进行工作,即按需播音和混音。通信功能是用于播放和停止声音的调用,可使音频自动、完美地适用于功能并行化。使用线程分析工具为该工作提供帮助,并通过您想在其自己的线程中运行的代码段之前和之后进行的调用,音频系统可被分解成自己的线程。

让我们来了解下,您的人工智能系统如何运用该功能并行化。根据您的游戏需要,您可能会有很多不同的任务,您可为它们提供自身线程。我们来了解下其中三种任务:路径查找、战略人工智能和实体系统本身。

路径查找

您可以以这样的方式实施您的路径查找系统,即每个搜索路径的实体可随时按需调用自己的路径。尽管本方法会起作用,但它意味着,每当有路径被请求时,引擎就要等待路径查找器。若您将路径查找重组为自己的系统,您可将它分解成它自己的线程。路径查找器将会像资源管理器那样运行,在资源管理器中,新资源就是路径。

想查找路径的任何实体都可发出路径查找请求,然后再立刻从路径查找器取回一个“搜查令 (ticket)”。该搜查令就是一种路径查找系统用来查找路径的特殊句柄。这时实体可继续运行直至游戏循环到下一帧。实体可查验搜查令是否有效。若有效,实体找回路径;否则,它可在继续等待时继续实施所需的任何操作。

在路径查找系统中,搜查令用于记录跟踪路径请求,而系统则对路径请求进行处理,不必担心系统性能会受到影响。该类系统有一种积极效果,即自动跟踪发现的路径。所以,当收到对先前所发现的路径的请求时,路径查找器可为现有路径提供搜查令。在任何具有很多实体路径的系统中,该方法都非常高效,因为任何路径一被找到就可能会被再次需要。

战略人工智能

上篇文章所述,全面管理游戏的人工智能系统与自身的线程匹配完美。它能分析游戏场并给不同实体发送命令,当实体靠近游戏场时,它可分析命令。

在自身线程中的实体系统将很难为决策图搜集信息。这些发现可发送到战略人工智能系统,作为对决策图的最新请求。当战略人工智能更新时,它可解析这些请求,更新该决策图并进行判断调用。无论这两个系统(战略人工智能和实体)是否同步都是可以的:即使不同步,它们也不会影响人工智能的决策。(我们是在谈论 1/60 秒,玩家不会注意到人工智能反应中的单帧延迟。)

数据并行化

数据并行化非常优秀,并利用了具有多内核的系统。但是有一个很大的弊端:功能并行化可能并未充分利用所有的可用内核。当您拥有的内核数量多于任务时,您的程序将不再应用所有的可用处理能力(除非运行程序的平台对它进行了处理,但最好不要依赖专用于通用应用的功能)。输入数据并行化(见图 3)。



图 3:数据并行化,某单一功能可利用所有可用内核。

在功能并行化中,您利用一套完整的自动单元,并为它提供和它一起运行的自身线程。现在,您要将单一工作进行分解,并将其分配给不同线程来完成。这样做可达到与系统内核一起按比例扩大的优点。您有带八内核的系统?很好。有 64 位的吗?为什么没有?虽然功能并行化支持您先指定要线程化的代码段,再让其自由运行,但数据并行化可能还需一点额外工作以实现流畅运行。例如,您可能会使用内核线程(一种“主”线程),它可跟踪谁在处理什么任务。子线程将需向主线程请求“工作”,以确保避免将同一任务执行两次。

实际上,使用内核线程管理数据并行化是一种混合方法。内核线程正使用功能并行化,然后该线程在用于数据并行化的不同内核之间对数据进行分解。

实施

线程工具如 OpenMP* (在大部分操作系统中免费提供),可助您比过去更轻松地将代码分解成不同线程。只用编译指令标记可被分解的代码段,用 OpenMP 处理其余的代码段。要用工作模块分解事物,您只需把线程调用放入遍历所述资源的循环中。

在路径查找系统示例中,路径查找器会保存请求路径列表。然后它会依次遍历该列表并根据各个请求运行实际的路径查找功能,从而将它们保存在路径列表中。可将该循环线程化,从而将循环的每次迭代分解成不同的线程。这些线程将会在第一可用内核中运行,支持最大程度地利用可用的处理能力。当无任务可执行时,内核才会空闲。

用于多个请求以实施相同工作的那些系统潜力巨大。当这些请求被间隔开时,路径查找器会自动查验请求是否已得到处理。对于数据并行化,很可能会在同一时间发生对同一路径的多个请求,这会导致冗余,破坏整个线程点。

为解决该冗余及其它冗余问题,所述系统需跟踪记录正在进行的任务都有哪些,而且只有在它们完成之后才能把它们从请求队列中除去。所以,若收到的请求是针对已请求过的路径,就需要先进行检查,然后再返回到搜查令指定的现有路径。

不能随便生成新线程。该过程将涉及对操作系统 (OS) 的系统调用。当该操作系统要完成它时,它会完成所需代码,并创建线程。这可能会花费很多时间(相对于处理速度来说)。这就是为何我们不想生成更多线程。如果正在请求的工作已得到处理,那么切勿运行该任务。而且,如果该任务非常简单(例如从两个非常近的点位之间查找路径),则不值得对其进行过细分解。

下面介绍了路径查找功能线程将要进行的分解,并介绍了它如何将工作分解成数据线程:
 

  • 请求路径(开始,目标)。从路径查找器外部调用该功能,以得到一条线程。该功能:
    • 遍历完整的请求列表,确定该路径(或其相似路径)是否已被找到,然后再返回用于该路径的搜查令。
    • (若路径还未被找到)遍历主动请求列表以查找该路径;若该路径在该列表中,则该功能返回用于该待处理路径的搜查令。
    • 生成一条新请求并返回新搜查令(若以上方法均无效)。
  • 检查路径(“搜查令”)。通过使用该搜查令,该功能遍历完整的请求列表,并查找路径,其中该搜查令对该路径有效。它能够返回路径是否存在。
  • 更新路径查找器()。这是 shepherd 功能,可处理路径查找线程的费用。该功能可执行以下任务:
    • 解析新请求。相同路径的多个请求可通过不同内核同时生成。该段删除了冗余,并将多个搜查令(来自不同请求)分配至相同请求。
    • 通过主动请求循环。该功能支持所有主动请求并对它们进行线程处理。每个循环开始和结束时,代码标记为线程。每个线程将会 (1) 查找请求的路径,(2) 借助分配的搜查令将它保存在完成的路径列表中,以及 (3) 将任务从主动列表中删除。

解决冲突

您可能已注意到这一设置可能造成灾难性后果。所有需要写入请求队列的不同线程,或所有需要添加某些内容至已完成“桩”的数据线程,会导致写入冲突,即一个线程将某内容写入插槽 A,而另一个线程将其他内容同时写入插槽 A。该冲突会导致众所周知的“竞态条件”。

为避免写入冲突,代码段可标记为“关键”。当某内容标记为关键时,一次只有一个线程能够访问该代码段:所有想要执行相同操作(访问相同内容)的其他线程都需要等待。当多个线程相互阻止访问内容时,该行为会导致严重问题,如崩溃。该设置可切实避免崩溃。线程工作完成后,方便时可访问内存段,且无需关联其他线程可能需要的其他段。

保持系统同步


因此,您让所有的单独人工智能子系统实现了自主,使它们能够随意使用找到的所有可用计算资源。运行速度极快,但它们失去控制了吗?

游戏需要提供结构化用户体验。引擎必须能够保持系统同步。您不能让部分游戏元素先于其他元素运行 1-2 个帧。当敌人开始行动时,您不能让部队无所事事地等待路径。好父母需要公平对待子女。

主游戏引擎循环负责两类操作:渲染和更新。串行编程可帮助轻松保持相关系统同步。首先所有更新执行,然后渲染可绘制更新内容。此外,相关信息可能不易理解。

最终,移动更新(常常基于轨迹)的运行速度可能比渲染器快几帧。结果,动画会出现跳动情况,即实体可能呈现跳动和加速移动的情况。路径查找可能考虑实体位置快照,并可能运行无效数据。

各种系统的同步解决方案具有出色的简单性。事实上,它可应用于多数引擎。当主游戏循环得到更新时,它可跟踪全局时间索引。所有的线程将只需要处理当前(和过去,而非未来)的时间索引更新。

当有关当前时间索引的指定任务的工作全部完成,线程可处于睡眠状态,直到新的时间索引生成。这一行为不仅可帮助确保系统相互同步,而且可确保线程不会使用多余的内核。移动工作能够完美处理不断出现的碰撞和移动轨迹,并能在提前完成时共享处理能力。再次强调,您能够充分利用可用内核。

线程指南


以下是大家在设计多线程系统时需要了解的一些事情:

  • 功能并行化:用于系统可以自主运行的情况。一些功能需要配置在系统中以解决冲突和冗余问题。
  • 数据并行化:
    • 用于实施批量操作的情况。
    • 设计原则是确保回写保持最少程度,并在流程结束时发生。
    • 对最新信息(可在其他线程中编辑)的依赖度最低,或避免这种依赖。(我的战略信息过时 1/60 秒会怎么样?)
    • 确保您在工作时对于另一个系统的使用需求不会阻妨碍线程运行:“请求路径”,“检查路径”,而非“获取路径”。

线程失效时


 

有时,线程可能无法正常运行。借助 OpenMP 等工具,您可以轻松调整系统将即时把工作分解为线程的数量。借助英特尔® VTuneTM 性能分析器和英特尔® 线程调节器, 您能够清晰了解系统在不同并行化级别中的有效性。在下面这些案例中,您可能希望避免线程操作,然而:

  • 极度复杂的系统。如果子系统关联过多其他系统,子系统或其他系统常常需要等待,此时,线程操作可能无济于事。此外,系统本身可能获益于重新设计。
  • 原子工作负载。如果子系统的工作无法分解,您可能无法进行并行化处理。音频混合任务可能与线程一样可以发挥重要作用,但该任务工作需要将多种声音混合至最终传输至扬声器的频道。如果您的系统在混合之前对单个音频数据块进行了计算,那么它可能对其进行线程处理。
  • 高昂费用。这些系统中部分需要实施额外的工作(如路径查找)。如果线程带来的效益不足以弥补相关费用,那么可能需要避免实施或禁用线程处理。这可能适用于具有较少元素(实体、路径等)的系统。
  • 重复代码。在某些情况下,多个线程会使用相同代码,结果却造成代码部分浪费或被忽略。在工作开始之前,冗余检查一般能避免这种情况。

多颗处理器和多核处理器(和多颗多核处理器)能够显著增强线程处理的重要性。任何程序员的目标是充分利用可用的处理能力。系统人工智能愿景受到硬件发展现状限制可以理解,但不能因为硬件未得到充分利用而停滞不前。借助能够简化线程实施的现代工具,您完全应该设计支持线程处理的代码。

总结


开发有趣的、可高效运行的动态人工智能系统非常简单。首先应该提升效率和实施优化。通过合理组织系统以充分利用任务和数据并行化,您能够帮助确保系统实现最大运行速度,并能够随着标配计算内核的日益增多不断扩展以满足行业需求。

如本系列文章所述,游戏人工智能的人工特征智能特征更为显著。程序员有责任创建系统代理功能,以模拟真实对手的行为。从低级规则和路径查找到高级战术与战略人工智能,基本组件并不会过度复杂。


相关文章


第 1 部分:设计和实施
第 2 部分:路径查找和感知
第 3 部分:战术和战略人工智能

关于作者


Donald "DJ" Kehoe:作为新泽西理工学院信息技术项目的导师,DJ 开拓了游戏开发领域的专业化之路,并教授该项目中有关游戏架构、编程和关卡设计的许多课程,以及集成 3D 显卡与游戏的课程。目前他正在攻读生物医学工程博士学位,运用游戏和虚拟现实来增强神经肌肉康复的效果。

感谢


*《星际争霸 2》* 是 Blizzard Entertainment, Inc. 的注册商标和版权产品,需经许可才能使用。

有关编译器优化的更完整信息,请参阅优化通知