游戏服务器场景管理AOI方案
在MMOPRG（大型多人在线角色扮演游戏）服务器中，AOI（Area Of Interest，兴趣区域）是一项不可或缺的技术。从广义上讲，AOI系统支持游戏世界中的任何物体个体对一定半径范围内发生的事件进行处理。不过，在MMOPRG中，绝大多数需求仅涉及对半径范围内物体的离开和进入事件进行处理。当玩家进入一个游戏场景并能看到其他玩家时，背后的AOI系统便在发挥作用。显然，AOI实现方案的优劣直接决定了服务器能够承载的同时在线人数上限，也影响着策划对游戏玩法的设计空间。通常，回合制和即时制的MMOPRG会选用不同的AOI方案。
严格来说，AOI是碰撞检测的一种特殊情况。除了碰撞集本身，它还包括两个状态间碰撞集的差异报告。例如，若物体P在[A位置]时的可见集为[Old]，当物体P从[A位置]移动到[B位置]，其可见集变为[New]，那么[Old]和[New]之间的差异存在两种可能：
- 物体ObjOld原本在[Old]中，但不在[New]中。
- 物体ObjNew在[New]中，但原本不在[Old]中。
为了便于理解，下文将物体具体化为玩家。上述两种差异的直观表现通常为：
- 玩家P的客户端画面会移除玩家ObjOld的显示（若所有玩家的AOI半径一致，玩家ObjOld的客户端画面也会移除玩家P的显示）。
- 玩家P的客户端画面会添加玩家ObjNew的显示（若所有玩家的AOI半径一致，玩家ObjNew的客户端画面也会添加玩家P的显示）。
最直接实现AOI需求的方法是将全世界玩家的信息全部同步给客户端。然而，这种方案的复杂度为O(n^2)，服务器难以承受。不过，对于超小地图且玩家人数在十人以下的特殊需求而言，这或许是一种简洁的解决方案。
目前比较流行的方案是网格法，它具有简单、高效的特点。该方法将地图按照设定的格子大小划分为网格。当玩家移动到某一坐标时，可轻松将其归入该坐标所属网格G的玩家链中。玩家的可见集可以通过聚合以网格G为中心的九宫格中的玩家链得到。获取两次移动间的可见集差异也并不困难。但网格法也存在一些弊端：
- 格子宽度通常比地图的最小单位尺度大很多，在需要精确距离触发的场景中，需要借助定时器等方案来实现。
- 在大场景地图中，网格数量会过多。
- 当面临不同对象拥有不同AOI半径的需求时，可能需要引入其他方案来辅助完成。尽管如此，若非必要，网格法仍是非常理想的AOI方案之一，因其简单高效。
在碰撞检测方面，利用空间划分来剔除远距离物体的多余运算的思路是很自然的。显然，QuadTree（四叉树）、Octree（八叉树）、BSPTree（二叉空间分割树）等都是可行的方案。但对于MMORPG中大量玩家的移动行为而言，Sweep and Prune（扫描与裁剪）方案更为高效。该方案最初由D. Baraff在其1992年于康奈尔大学的博士论文“Dynamic Simulation of Non - Penetrating Rigid Bodies”中提出，而“ I - COLLIDE: An Interactive and Exact Collision Detection System for Large - Scale Environments”（1995）这篇论文则给出了一个改进的src实现。这两篇论文都可以通过谷歌搜索直接获取。（顺便提一下，GPG2中Steven.Rabin提出的RDC（递归聚维？）其核心原理可能也源于此）。Sweep and Prune方案的优点是对凸多边形的大规模实时小步长运动系统支持良好。相对于传统空间划分方法O(n * log2n)的时间复杂度，它几乎能降低到O(n + s)。
该方案达到上述优点的前提是场景中物体虽然可以无限制地移动，但移动步长相对较短。利用这个短步长的特性，可以假设每个物体在下一帧中的移动对整个排序好的interval N维链表来说变化很小。因此，它的移动是基于前一个有序状态的小范围轴向比较，复杂度几乎线性可控。而MMORPG玩家的移动就属于小步长运动，跳转场景导致的节点增加和删除是小概率事件。若要避免Sweep and Prune方案在节点增加和删除方面的弱点，可以引入系列unrolled linked list（松散链表）对interval链表进行分段。这样，在删除和增加节点事件发生时，可使用二分查找法定位到指定的unrolled link list进行可控链表段之间的增删操作。Sweep and Prune方案甚至可以演化为多线程版本，具体实现可参考“Efficient Large - Scale Sweep and Prune Methods with AABB Insertion and Removal”（2008）。不过，对于非海量物体的场景，使用该方案可能有些大材小用。
此外，还有一些可行的方法可以简单有效地提高AOI系统的运行效率：
- 区分场景中物体的特性：例如，售卖NPC、玩家和具有AI且能自动攻击范围内玩家的怪物这三种物体应区别对待。售卖NPC无需看到任何物体，但需要被玩家看到；玩家需要看到所有物体；怪物则只需要看到玩家，无需看到其他怪物和NPC。区分物体特性的方法很简单，引入一个简单的Interest机制即可。比如使用InterestMask，通过一个 & 操作就可能跳过大量的后续处理；也可以使用更通用的InterestFilterCallback。
- 合理利用网络延时：MMORPG运行在非即时的网络环境中，公网上120 - 200ms的延时通常是玩家可以接受的。我们在接受这一事实的同时，也应加以利用。虽然在实现上可以在玩家移动的同时进行可见集的差异广播，但即使服务器每隔200ms向某个玩家同步一次可见集信息，在很多MMORPG的玩法中也是可以接受的，并且这种方案还可以引入其他特别的优化。
- 基于聚集点进行局部优化处理：在在线游戏中，玩家并非理想地平均分布，玩家集中的区域大多受玩法影响，如功能性NPC周围、刷怪区域、摆摊区域等。在这些密集玩家聚集的区域，上述算法的时间复杂度都会趋近于O(n平方)。此时，可以考虑对达到一定阈值的区域进行特殊处理。
- 根据可操作距离区分同步频率和同步信息层次细节度（LOD）：该方法源于一篇论文，具体做法是在同步A物体的AOI信息时，根据AOI范围内物体与A的距离远近区分信息同步频率。假设将A的AOI范围物体按远近分为近（可操作）、中（不可操作，但影响游戏感受）、远（不可操作，且不精确移动也无妨）三级。近的物体实时同步且LOD高，中的物体按较高频率同步且LOD中，远的物体则低频率同步且LOD低。当物体移动时，原来的中、远距离物体会依次变为近的物体，逻辑上准确无误。但可能会出现跑动后的拉扯行为，若无法接受，可引入dead reckoning进行行为预测。
- 策划参与优化：这一点虽列在最后，但并非不重要。实际上，无论如何优化AOI算法，最有效的优化方式还是策划在设置玩法时尽量避免单点（小区域）大量聚合玩家。因为单点聚合后复杂度接近O(n^2)，这是非常不明智的做法。这也是为什么很多MMORPG会划分门派，每个门派通常拥有不同的场景。相比于程序优化，策划优化才是上策。