2007年7月20日 – J.M.P. van Waveren，Id Software
关于ID SOFTWARE
弗洛伊德将 id 定义为人类心理结构的原始部分；Id Software 总部位于德克萨斯州麦斯奎特市，成立于 1991 年。从成立之初至今，id Software 作为独立游戏开发商和技术提供商，持续引领技术、设计和艺术效果市场领域。Id 叱咤游戏行业多年，其标志性品牌（如德军总部、毁灭战士、雷神之锤和雷神战争）已成为数代游戏玩家的主流文化。有关 Id Software 的更多信息，请访问 www.idsoftware.com。
关于作者
J.M.P. van Waveren 毕业于荷兰代尔夫特理工大学计算机科学系。他在电脑游戏领域拥有十年以上的技术开发经验，曾参与多款 3A 级游戏大作的研究和开发，如：雷神之锤 III 竞技场、重返德军总部、毁灭战士 III、雷神之锤 4、雷神战争。他目前就职于 Id Software，负责新一代游戏技术的开发。
摘要
为了让第一人称射击 (FPS) 游戏呈现智能行为，受人工智能 (AI) 控制的人物角色需要在空间和时间上注意周围环境。在当今的高细节游戏中，要通过实时环境采样在游戏中获得这种意识，是尤其耗费资金的。此外，在PC游戏环境中仍非常常见的单CPU/核系统上，只有极少占比的CPU时间被分配给AI。因此，需要尽可能多地使用预先计算的数据结构，以便让AI能够快速分析环境并制定智能决策。Id的新产品“深入敌后:雷神战争”采用了革新性的id Tech 4游戏引擎，它本就有一套系统能够允许虚拟玩家（机器人）快速获得所需的空间和时间意识，以便在游戏中有更好的表现。在该系统的预计算阶段，以一个或多个双流形三角网格的形式计算配置空间（C空间）的边界表现 (b-rep)。这是一个复杂且耗时的过程，其中需要对数百万的三角形执行几何操作。为了显著提高此过程的速度，通过 Incredibuild 分布式编译技术，将工作划分成许多独立的组块，以便允许实施最大化的并行处理。在电脑游戏的AI预计算领域，Incredibuild 能够非常有效地缩短编译时间，并由此缩短整个开发周期。
AI预计算
空间和时间意识是在FPS游戏中获得好战绩的关键。人的大脑非常善于识别和预测，真人玩家在FPS游戏中利用这些能力来迅速对周围环境形成意识。在对某个FPS游戏有了多次体验之后，人们能够轻松辨别自己在环境中所处的位置，快速预测即将发生的事情，从而能够决定要去哪里以及要做什么。在任何给定时刻，FPS游戏中受人工智能 (AI) 控制的人物角色同样需要能够快速获得空间和时间意识，从而明智地决定要去哪里以及要做什么。
虽然多核系统能够快速处理PC游戏环境，但仍存在大量单CPU/核系统。在这些系统上，分配给AI的CPU时间通常仍不超过10%。同时，游戏环境的复杂性和动态性正显著增大。环境的多边复杂性在近几年显著增大，在当今的游戏中，利用先进的实时物理模拟技术，环境中有多得多的动态对象在移动。为了应对这种增大的复杂性，同时尽可能减少对CPU的占用，必须为AI预先计算出一切能够被预先计算的内容。在环境中不发生变化且保持静止的一切内容都在预计算的考虑范围内，以便形成相应数据结构，方便由AI控制的人物角色能快速理解其在环境中的位置和处境。此外，预先计算能够实时加快动态对象处理的数据结构也很重要。
AI的“预计算”数据可以通过编程或手动的方式添加到游戏中。关卡设计师看似轻松地将AI的某些提示（比如路标、路径、营地、任务点等）加入到关卡中。但设置理想的路标并创建理想的路径从而让 AI 能够轻松到达关卡的所有位置，并不是一件轻松的事情。此外，随着策略复杂性提高，关卡中需要设置的提示也越复杂。关卡设计师通常需要手动设置大量提示，以覆盖整个环境。在设置提示前，关卡设计师需要接受相关提示设置方面的培训，这需要占用时间。关卡设计师也可能出错，尤其是在需要设置的提示较复杂并且/或者对最优设置的定义不佳的时候。手动设置的路标、路径和提示需要经过连续测试，才能杜绝错误，确保AI能够按照预期那样使用这些提示。
由于具体实施中的漏洞，为AI提供其所需信息的算法解决方案可能在一开始就出现问题。然而，就算漏洞得到了修复，它通常也无法恢复原状，但在采用手动解决方案的情况下，在开发期间，任何时候都可能出现人为错误。算法解决方案能够带来可扩展性、可重复性和一致性。此外，扩展成本要低得多。聘请、培训和雇佣别的关卡设计师非常花钱。算法解决方案可能在一开始需要一定编程时间，但从长远来看，仅通过使用更多的计算能力，就能够在较短的时间内编译更多关卡，这要便宜的多。
区域意识系统
雷神战争 (ETQW) 中的机器人利用区域意识系统 (AAS) 来理解、导航并快速意识周围环境。这种区域系统在离线编译过程中自动从关卡几何体中推导出来。AAS 编译过程的第一步涉及构造配置空间（C 空间）的边界表现 (b-rep)。C 空间的 b-rep 包含一个或多个双流形三角网格，描述世界几何体与机器人（或玩家）所在包围体的 Minkowsky 总和。在下一个步骤中，AAS 编译器在 C 空间的 b-rep 上识别可行走的表面。这些可行走的表面被细分为最少数量的可行走区域，这样，机器人或玩家就能够在区域中的任意两点之间直线移动。这需要大量的过滤操作，才能忽略不应被视为玩家导航障碍的小细节。下一步，计算所谓的“可到达性”，指定机器人如何能够从一个区域导航至另一个区域。
AAS 实施了一种层级性路线规划系统，用于实时搜索环境中的路线。该系统包括缓存管理器，用于缓存路线并因此避免频繁地重新计算路线。路线规划系统的层级性质让路线计算变得非常快速，并最大程度减少了缓存量。一旦计算出了路线，便可以使用路径优化器来在环境中沿某条路线规划笔直和弯曲的路径。路径优化器沿地面追溯，测试 AI 是否能够到达某个点或者是否能够沿特定方向行走。这些地面追溯非常快速，因为 AAS 能够过滤掉所有不妨碍玩家导航但却能够通过常规碰撞检测查询返回的所有小细节。一旦计算出了优化路径，便可以使用系统来围绕动态障碍物的任意复杂构造计算路径。如果途中存在动态障碍物，该系统便修改优化路径。在计算新路径时，障碍物规避系统还会考虑环境中的静态边界，以免 AI 进入静态世界几何体。AAS 旨在快速提供所有本地世界边界，如墙和凸台，在规避障碍物时，需要考虑这些边界。
AI 需要能够做到的最基本事情之一是，意识到其在环境中的当前位置，并理解直接境况。AI 的许多其他系统采用的是时空一致性，通过先前的已知位置来理解 AI 的当前位置。然而，在高动态游戏环境中，事件的发生并不是始终能够被预测到的，AI 可能移动到远离任何先前已知位置的位置。比如，AI 可能已经走到靠近凸台的位置并可能被推落凸台，爆炸可能炸飞 AI，或者 AI 被车辆拖行，等等。在不知道先前位置的情况下通过常规环境采样来意识在环境中的当前位置（比如，通过查找最近路标的方式），在当今的高细节度游戏环境中，是需要巨大资金投入的。
AAS 让 AI 能够在任何时候意识到其在世界中的当前位置，仅需计算 10 至 20 个点积，不必缓存先前已知位置。当 AI 意识到到其当前位置时，系统立即提供大量 AI 所需的信息，让其能够智能地决定要去哪里以及要做什么。然后，系统允许 AI 快速执行额外的查询，以搜集其所需的任何额外信息，如路线、路径、行进时间以及环境的其他属性。
分布式计算
目前，C 空间的 b-rep 构造是 AAS 编译过程中最昂贵的步骤。出于多种原因，AAS 编译器被构建成将 C 空间的 b-rep 计算所涉及的工作划分成许多独立的小组块。几何处理中涉及的数学并不太复杂。但通常难以预测几何处理算法需要覆盖的所有不同情形。即便算法覆盖了所有情形，且在理论上完美无瑕地工作，但由于存在浮点舍入，算法也无法带来期望的结果。几何处理算法的实施通常涉及许多行用来处理浮点舍入的代码。为了总体上规避大量浮点舍入误差，并简化舍入误差处理，可以使用合理定义的浮点值范围，以原点为中心，以小组块的方式进行几何处理。在将工作划分成小组块后，还能够更轻松地分析并排除算法开发期间的问题。小组块能够被快速地重新计算，问题能够被定位并以独立于几何体其余部分的方式进行分析。
由于工作已被划分成许多独立的小组块，因此能够利用网格计算解决方案轻松加快 C 空间的 b-rep 构造。Incredibuild 分布式编译技术对于网格计算解决方案有着至关重要的意义，它能够最大程度减少集成时间，且使用非常简单。Incredibuild 使文件系统虚拟化，并自动分配工作，包括执行工作时所需的可执行文件。换句话讲，可以在本地修改关卡几何体，并且可以在本地重新编译可执行文件，不必手动将工作和可执行文件重新分配至多台计算机。为了通过 Incredibuild 获得最佳性能，需要精简且加载速度非常快的可执行文件。幸运的是，可以针对手上的任务，轻松地仅将绝对必要的源代码拆分到 Win32 平台应用中。有三种接口能够查询 Incredibuild 任务，其中一种是 XML 接口。创建简单的 XML 文件，其中列出了工作以及处理工作时要用到的可执行文件。然后可以将 Incredibuild xgConsole.exe 命令行应用作为管道进程来调用，使得平台输出能够被重定向至游戏应用或关卡编辑器。
结果
我们实施并测试了多种不同的方法来并行构造 C 空间的 b-rep。这种算法通常首先用在单线程应用中。自然发展的结果是，使用多个线程。如果不使用多个线程，也可以选择调用多个进程，每个进程构成工作的组成部分。这与 Incredibuild 的工作方式非常相似，但是仅使用一台计算机。下一种选项显然是使用 Incredibuild 并在许多计算机之间分配工作。我们使用这四种方法对多个 ETQW 关卡进行了编译，并测量了编译时间。下面列出了所使用的关卡的一些统计数据。针对每个关卡列出了玩家碰撞检测所用的三角形数量。此外，还列出了包含几何体的小组块数量，其中每个组块以单独的文件存储。接下来，列出了所有组块文件的总大小，同时还列出了用于描述 C 空间的 b-rep 的三角形数量。
下图显示了使用不同方法的关卡编译时间。单线程方法使用了搭载有两个 Intel 2.8 GHz 双核 Xeon CPU（禁用了超线程的“Paxville” 90nm NetBurst 微架构）的系统上的一个核心。多线程方法使用了四个线程，其中每个线程占用同一系统上的一个（共四个）核心。多进程方法使用了四个进程，其中每个进程同样占用同一系统上的一个（共四个）核心。Xoreax Grid Engine 方法使用由 14 台计算机组成的网络，处理器频率共计 78.6 GHz，总共包含 27 个核心，其中 9 个核心基于 Intel NetBurst 微架构，18 个核心基于 Intel Core 2 微架构。这些计算机全都加入一个 1 Gb 网络，由于网络基础架构的速度快以及文件量小，因此实现了最小化的网络开销。
即便在启动新进程时存在一定开销，但使用多进程的速度比多线程快。线程不单独使用自有内存池，因此存在内存争用问题。这就使多线程解决方案陷入困境，而多进程解决方案中的每个进程则拥有自己的地址空间。Incredibuild 解决方案利用可用的 CPU/核心数量实现了极具线性化的扩展。在上述例子中，Incredibuild 甚至利用可用频率实现了相对于单线程的线性扩展，因为基于 Core 2 微架构的核心比 Paxville 核心速度快。
深入应用
由于可用 CPU 能力快速增大，而内存和 IO 带宽并不以同等速率增加，因此压缩就变得更为重要。为了降低对存储空间和带宽的需求，将使用越来越多的 CPU 能力。从网格计算的角度讲，不对称压缩格外令人关注，其中，游戏期间的实时解压着实快速，而离线压缩如要以最高的压缩比实现尽可能好的质量，则可能需要执行大量计算。网格计算非常适合这种类型的离线压缩。Incredibuild尤其适用于声音压缩和纹理压缩。通常存在许多声音和纹理，而在有大量声音和纹理的情况下，可以将这些声音和纹理进一步划分成许多小组块，以便通过 Incredibuild 进行大规模并行处理。