游戏AI LOD交易员
游戏AI的LOD控制
这次我们来一同看看AI LOD的一个另类控制技术，如果你对AI LOD一无所知也没关系，本文会为你们做个科普。但请注意，本文着重讨论其思想，具体实现你们可以参考文末附带的项目，或者去看看原论文。
LOD的概念
提到 细节层次 （Level of Details，简写LOD），大家可能首先会想到图像渲染，像游戏中大地图的3D物体会随玩家与其距离的远近而变化精度（主要是模型面数的变化，有时还会直接剔除）。Unity中的「LOD Group」组件就是做这事的。
而在游戏中这种变化玩家一般是难以察觉的，毕竟远距离的东西本身就不易看清，再让它「模糊」点也不会怎么样。当然，「穿帮」的时候也不是没有，比较常见的就是玩吃鸡游戏跳伞时，地面建筑突然出现的情况，只不过一般这些都不会太影响游戏体验。
有了这样可靠的自动调整技术，开发者可以摆放更多/更精致的物体在场景中，而无需太担心玩家设备的渲染压力。可以说LOD成为了现代大型游戏的基石技术之一，能在游戏中看到丰富美丽的画面它厥功至伟。
AI的LOD
图像中的LOD聚焦模型面数的调整，为的是缓解GPU压力；LOD的概念也存在于游戏AI中，AI中的LOD则聚焦的是代码运行「代价」的调整，为的是缓解CPU压力。
AI的LOD通常可以从 复杂度 和 运行频率 两方面考虑：
- 「复杂度」可以通俗的理解为代码逻辑的难易程度。比方说，直线运动的复杂度肯定比A星寻路的复杂度低。在有障碍的地形上，怪物的移动通常要运用寻路算法，但对于那些玩家难以注意到的怪物的运动，我们就可以取巧——暂时用简单的直线运动代替。
- 「运行频率」就如其名，指代码运行的频率。比如，我们可以每两帧调用一次怪物AI相关代码而不是每帧都调用，对于更不引人注目的，我们还可以设置为更低。通过减少相关代码运行的次数，也可以降低CPU压力。
我们可以在《原神》团队公布的AI框架设计中看到AI LOD相关内容：
可以看到，实际AI LOD的内容还是很细的，包括了感知、目标搜索、寻路、决策、动画播放等等，「运行频率」最高有30Hz，最低则是5Hz。那AI LOD的变化要根据什么进行调整呢？也和图像LOD一样 「离玩家距离越近LOD越高，反之越小」 吗 (⊙ˍ⊙)？
这的确是最传统的做法，但其实仔细想想，这样做是有不小局限的：
- 限制了角色分布。开发者必须要考虑玩家近距离能接受的最多NPC的数量，如果玩家身边有超过100个智能角色，玩家的CPU压力是否会过大？所以，开发者不会让一块小区域内有太多的角色。
- 限制了AI的真实度。你可能打算使用很好的AI行为决策方法，把角色做得更活了一样，有一两个这样的角色倒还好。如果有20个呢？有100个呢？CPU可不只是做AI这一个工作上呀，考虑到游戏还有很多要处理的事情，这么设计AI显然是行不通的。
- 距离阈值的较为繁琐。AI LOD的变化很大程度依赖事先做好的距离判定值，这些值的设置需要开发者耐心调试。比如，我们设置当玩家与角色距离小于10m时，该角色的AI LOD为「高」；当距离大于10m且小于50m时为「中」……像10、50这些就是LOD变化的「距离阈值」。如果值过小，就会让玩家发现「穿帮」，例如玩家距离角色30m时已经注意该角色了，而此时角色AI还在「中」LOD，玩家就会发现角色正以较低的频率运行，一眼假(* ￣︿￣)；而值过大，就会导致CPU占用过高，例如将角色的「高」AI LOD阈值设置为100m，那想必有玩家周围的很多角色都会变得「栩栩如生」，即便这个角色玩家根本不可能注意到，结果就是画面变卡。所以，开发者不得不根据经验、耐心地调试，找到合适的阈值。
AI LOD交易员
在这篇论文中，作者提出了一种特别的AI LOD调整方案—— 「LOD交易员」。它将运行AI所用到的系统资源视为「可投资的资产」，将场景中的各个AI当作「投资对象」。然后一一与之进行「交易」，即为每个AI确定各自的AI LOD方案，从而使得「利润」最大化——也就是在不透支系统资源的情况下，协调场景中各AI的LOD，使得总体能表现得最具真实性。
让我们一起来看看这是怎么做到的吧！
1. 特征图
首先要做个预处理工作——绘制好每个AI的 「特征图」。
- 什么是「特征」？
像之前提到的「感知、目标搜索、寻路、决策、动画播放等等」，这些 AI LOD控制的具体内容 ，我们就称之为「特征」。每个「特征」都应当有多于1个的LOD（否则就没有调整的必要了(￣▽￣)~），以寻路为例，假设它有两个LOD，一个「高」一个「低」，高 LOD 可以表示「使用 NavMesh 寻路」，低 LOD 可以表示「直线穿行抵达」。
我们将所有AI特征与其LOD的组合称为 「特征解决方案」。例如，一个角色AI的所有特征为：模型可见性、寻路、行为动画、目标查找，那么{可见性：高} + {寻路：高} + {行为动画：中} + {目标查找：低}，就是一种特征解决方案。
可见，根据这样的排列组合，一个AI会有不少的特征解决方案。而特征之间很多是相互关联的，在这一系列的特征解决方案中，会存在相当一部分不合理的方案。比如{可见性：低}+{寻路：高}+{行为动画：低}+{目标查找：高}，这个特征解决方案明显不合理，因为在模型不可见（我们将可见性「低」LOD视为隐藏模型）的情况下高质量寻路毫无意义。
所以，为了更好表示 特征之间的约束关系 从而 筛除不合理的特征解决方案，我们使用特征图。它是一种单根节点的无环图（如果你对「图」这种数据结构不是很了解的话，墙裂建议去学习一下，它是很基础也很有用的(￣m￣）），比如论文中的这个包含8个AI特征的特征图：
图中，圆圈表示的就是「特征」，方框表示的就是各特征所有的LOD；比如「Action anims（行为动画）」特征，就有三个LOD——None（无动画）、LQ（低质量）、HQ（高质量），这里高低质量动画可能是通过开关IK动画来区分的。
我们还能看到图中有两种「箭头」——虚线的和实线的。虚线表示的是 LOD切换顺序，比如「Exists」特征，就只能从「Yes」变为「No」，反之则不行；实线表示的是 特征与LOD的依赖关系，比如「Behavior」特征，它只有在「Exists」特征的LOD为「Yes」时才允许采用，也因为有这样的箭头，特征图能 得出「合理」特征解决方案。
作者所用的特征图最终只得出了252个特征解决方案，相比穷举的方式，剔除了非常多的不合理方案。
- 一个AI就有上百个特征解决方案，那多个AI会过多吗？
以普遍理性而论，特征图是可以共用的，也就是说，一个游戏中的几十种怪物，它们虽然形态各异、动作各异，但都可以用同一个特征图（因为它们的「特征」都相差不大，都有可见性、寻路、行为动画等），所以不必担心特征解决方案数量的问题。而且遍历特征图来得到特征解决方案的过程完全可以在开发时就完成（像使用Navmash那样），而不占用游戏运行。因此，即便有多个特征图或者一个特征图有过多特征也没关系。
在我实现的项目中，使用了XNode插件来实现特征图的绘制，并且没有实现虚线箭头（感觉不是很实用），更具体内容可以看我项目里的文档。
2. 评估AI的重要性
区别于传统的根据距离来调节AI LOD的方式，我们会通过AI角色的「重要性」来调整。那何谓「重要」呢？一个游戏任务中，玩家密切追踪的关键剧情角色是重要的；与玩家相距非常近的路人角色也是重要的；玩家刻意聚焦观察的角色也是重要的……可以说，角色的「重要性」与玩家的心理密切相关，玩家关注的角色就需要高的LOD，否则就容易「穿帮」。几乎所有的「穿帮」都可以归为这三类：
- 不现实的状态（Unrealistic state，简称 US），一眼假的那些「穿帮」。比如，一个角色从一个空盘子里吃东西，或者穿墙跑，都可能导致不现实状态。
- 基本不连续 （Fundamental discontinuity，简称 FD），当角色当前状态与玩家对他过去状态的记忆相悖时，它就会发生。比如，角色在转角处消失，或者在玩家离开时停在原地数小时，都可能产生基本不连续。
- 不现实的长期行为（Unrealistic long-term behavior，简称 ULTB）， 这种「穿帮」的破坏体验感的程度最轻，通常需要玩家长期观察才能察觉。比如，角色总是随机地而不是有明确目标地行走，汽车永远不会耗尽汽油，诸如此类。
虽说我们不会「读心术」，但却有办法「旁敲侧击」玩家对一个角色的关注程度：
- 角色 占据屏幕空间的大小。这点显而易见，不过多解释。
- 角色与玩家 视野中心的偏移程度。玩家关注的往往是屏幕正前方的角色，因此，离屏幕中心越远的角色一般越不受关注。
- 玩家对角色的 记忆程度。对于通常角色而言，根据某遗忘曲线可以知道，越是最近遇到的角色，玩家的记忆程度就越高，通常也较受关注，而随着时间流逝又会大幅衰减。
- 玩家对角色的 持续观察时间。玩家老是盯着某些角色看，或者说某些角色老是出现在玩家视野中，玩家可能就会更关注它们。这可以通过统计角色出现在玩家视野的时间来判断。
- 玩家 再度观察角色的可能性。一个角色被玩家「遗忘」又重新关注的可能性，这与玩家的「记忆」密切相关。玩家对一个角色的记忆程度越高，越是可能对它进行再度观察，论文推出了一则公式来预测玩家返回观察的可能性。
- 其他。这一点与游戏内容相关，比如，那些在任务中至关重要的角色，就更有可能受玩家关注；还有场景中的精英怪、Boss，也更有可能受玩家关注……这部分是开发者根据需要进行补充的内容。
综合上面这些因素，我们就可以为「重要性」做一个可量化的定义了。在论文中，作者是将其制成了三维的「重要程度向量」，对应造成三种类型的「穿帮」的可能性。
而这个「制成」方式也很简单，只是将相关联的数据进行乘算再乘上一个常数，保证每个数据都有相同的数量级。
3.交易
接下来就是进行LOD交易，也就是调整LOD的过程了。首先还要说明一点，进行交易的LOD资源也是一个N维向量，维度的多少取决于AI消耗的资源类型，像文末实现的项目中，我的资源向量就是4维的（表示CPU、GPU等）。需要注意的是，这个向量的初始值需要提前给定，也就是确认可分配的各资源总量。
还需要为每个LOD 也设置好消耗资源，比如一个特征为「Locomotion」，它其中的「高」LOD资源消耗就是 (10, 10, 10, 10)；「中」LOD资源消耗就是 (4， 4， 4， 4)。就像下面这样：
当然，具体数值的设定还要结合特征本身，比如「寻路」几乎不使用GPU资源，那寻路的LOD消耗资源中，GPU相关的数值就可以是0。
既然一个LOD就有一个「资源消耗向量」，一个特征解决方案又是各特征的LOD的组合，而资源的维数也是固定的，那我们可以将一个特征解决方案的资源消耗以矩阵的形式表示（一点线性代数的知识）。
-
假设，某特征解决方案：{可见性：高} + {寻路：中} + {行为动画：低}，那么：
这样一来，一个特征图的所有特征解决方案的系统资源消耗，就可以用一个「矩阵列表」表示了。
整个「交易」过程可用分为2个阶段：
- 升级阶段。升级阶段会按照「重要程度向量」从大到小的、尽可能多的选择角色AI的LOD进行升级，直至场景中的所有角色AI都有最高的AI LOD（通常不可能）或者有资源消耗殆尽。这个过程就是最大程度地选择场景中玩家关注的角色，并提高它们的AI LOD。
- 降级阶段。在升级状态结束后，如果有资源耗尽，就意味着有「资源总量向量」中有些维度上的数值变为了负数。降级阶段会按照「重要程度向量」从小到大的、尽可能多的选择角色AI的LOD进行降级，从而回收资源，直至资源总量均大于0（也就是没有耗尽现象）。这个过程就是降低玩家不关注的AI的LOD来回收系统资源。
如此，「交易」就可以保证玩家关心的那些角色的AI LOD保持在较高水平并且系统资源还不透支。这其中其实还涉及了很多数学细节，篇幅所限，我无法详细为大家讲解了。
- LOD交易员的计算消耗会很大吗？
在我实现的项目中，对100个有着252个特征解决方案的AI进行「交易」，总耗时不超过 2ms（论文中作者的测试项目报告的结果是平均耗时57us）。我与论文作者的测试场景不相同、代码实现也不相同（矩阵的实现是手写的，没有什么加速过程）、也没有用到多线程或者Computer shader……所以有点差距，但也可以看出，这种调整方法耗时并不大。
尾声
和往常一样，这次分享的项目只是个粗糙的实现，几乎没有使用什么第三方库，但我认为这样也适合更具体地了解其实现。只不过，这次这个是做成插件的形式，它曾参加「BOOOM暴造 x Unity 开发者社区 游戏创作挑战」的「AI插件赛道」并获特别奖 （但并未有实践运用，可能多少还是有问题的，感兴趣的同学可以参考看着。不与论文完全一致哦，因为论文作者也只给了伪代码＞︿＜
这个插件相关的使用视频我发在B站上了，有需要可以看看。最后，提前祝大家新年快乐呀~