最快速的视野管理算法

导语： 本文提出一种利用无序数组、双向链表、位标记进行视野管理的算法，可以将每次增、删、查视野列表的复杂度降为O(1)。

1. 视野管理的必要性

在大型多人在线游戏MMO（Massively Multiplayer Online）中，多个玩家在同一场景，此时玩家需要能看到其附近的玩家，同时不需要看到与其距离远的玩家。这就是视野管理需要做的事情：为每个玩家维护一个视野列表，管理每个玩家可见视野内的其他玩家。

MMO游戏中，视野对服务器造成的压力主要来源于两点：

一，玩家频繁移动造成视野列表的频繁更新的压力；

二，广播视野列表的带宽压力。

因为视野列表中的玩家频繁变化，有的玩家离开当前玩家的视野，有的玩家新进入当前玩家的视野，因此当前玩家的视野列表需要进行频繁的增、删、查操作，因此增、删、查操作的时间复杂度要尽可能的低，从而缓解视野列表频繁更新的压力。如果当前视野列表中有100个玩家，每个玩家都移动了一段距离，为了让其他玩家看到自己的移动，每个玩家都需要被通知其他99个玩家的移动，这就需要广播100*99个数据包，随着地图中玩家数目增加，造成广播量急剧增加，对带宽造成极大压力，因此玩家的视野列表需要有规模限制，从而缓解带宽压力。

本文提出一种利用无序数组、双向链表、位标记进行视野管理的算法，可以将每次增、删、查视野列表的复杂度降为O(1)。

2. 视野管理算法

2.1 九宫格

游戏中地图用来承载阻挡、静态建筑、NPC（非玩家控制角色：Non-Player-Controlled Character）、WRAP点等。玩家在地图上移动，其可见的其他玩家即发生变化，如果玩家的每次移动，都更新视野列表，时间成本太高，因此只有当玩家离开某个区域时，才更新视野列表，而在这个区域内的移动，并不更新视野列表。为了划分这个区域，引入九宫格概念，如图1所示，九个格子的总面积大于一个手机屏幕，小于两个手机屏幕。大于一个手机屏幕的原因是，可以预先计算当前屏幕外的一些玩家，但又没有必要预先计算太多的屏幕外玩家，因此小于两个手机屏幕，玩家可见的范围为以玩家为中心周围九个格子内的其他玩家。如果玩家Me在格子5内移动，则不主动更新视野列表，玩家可见范围为红色和绿色格子内的玩家（如果玩家Me视野列表内的玩家He从一个格子移动到另一个格子，导致Me和He不可见，也会导致玩家Me的视野列表发生更新，称为被动更新），如果玩家Me从格子5移动到格子8则主动更新视野列表，玩家可见范围为紫色和绿色格子内的玩家。

[1507791719564_5075_1507791715333.png]

图1 玩家从九宫格的格子5移动到格子8

2.2 视野管理的数据结构

视野管理共采用三个数据结构：无序数组、双向链表、位标记。无序数组的增删时间复杂度为O(1)；双向链表可以在遍历视野列表时避免遍历整个无序数组；位标记在判断两个玩家是否相互可见时时间复杂度为O(1)。

2.2.1 无序数组

视野管理的数据结构首先是采用无序数组：每个玩家有两个数组，一个数组A存储其他玩家信息的对象指针，对象包含三个元素：其他玩家的指针、当前玩家在其他玩家视野数组中的索引、其他玩家在当前玩家视野数组中的索引，第二个索引供双向链表使用，A数组某些元素可能空置；另一个数组B辅助管理A数组，数组元素是一个结构体，成员变量为：标识变量、记录A的空闲位置的变量，数组B的规模与数组A规模大小相同。其中，数组B的第i个元素中的标识变量表征A数组的第i个元素是否被分配。另外，设置两个指针在B数组上移动，分为头指针和尾指针，用于维护、快速查找A数组上空闲的位置，如果分配空闲位置，头指针向右移动，如果回收已分配位置，尾指针向右移动。

如果从Me的视野列表中删除He，首先查找He在Me的A数组的索引，单独查找索引的算法并非O(1)的算法，但批量查询索引的算法是O(1)的算法，详情见下文：视野管理的流程。 通过索引可以直接查到该玩家He在Me的A数组中存储位置，然后清空Me的A数组中该玩家He信息，并将Me的B数组对应的位置的分配标记置为空闲，B数组的尾指针位置记录新空闲位置，尾指针右移；如果要加入一个玩家He，通过Me的头指针查询到Me的B数组中存储的第一个空闲位置，并检查B数组中该位置的分配标记，如果分配标记为空闲，即可将新入玩家He放到Me的A数组中该位置，并将Me的B数组中该位置置为已分配，头指针右移。

假设视野列表大小为5，下面以表格的形式演示本文算法，表格的前三行对应B数组每个元素对应三元组（ArrayIndex,EmptyIndex,State），其中ArrayIndex是B数组元素位置索引，EmptyIndex是A数组中空闲的位置索引，State是A数组中该位置是否被分配（只是为了校验）：值为E表示A数组该位置未被分配，可在该位置存储新进入视野列表玩家；值为U表示该位置已分配，存储了视野列表中的玩家。表格的第四行（Pointer）行，标记在B数组游走的两个指针的游走位置，Head：表示头指针；Tail表示尾指针。下面展示B数组在为A数组分配和回收位置时的变化。

初始状态如表1所示，初始状态视野列表为空，即A数组中不存储任何可见玩家，B数组中EmptyIndex记录A数组全部位置：0、1、2、3、4；B数组中State全部为E，表示A数组全部为空；B数组中的两个指针Pointer都指向第一个位置。

假设需要分配A数组中三个空闲位置给进入视野列表玩家，此时遍历Head指针和Tail指针中的位置，因为这两个指针之间的位置存储的都是空闲位置，每分配一个空闲位置，都将对应State标记为U，同时Head指针右移动，分配的位置为A数组中的0、1、2。结果状态如表2所示。

接着，假设删除一个玩家（该玩家在A数组中索引为2），则将Tail指针所指位置的EmptyIndex改为2，同时Tail指针右移，表示Head和Tail指针中的空闲位置多了2，将B数组中位置2处的State改为E，表示A数组中索引为2的位置空闲。状态结果如表3所示。

然后，再分配A数组中两个空闲位置给新进入视野列表玩家，此时遍历头指针Head和Tail指针中的位置，将A数组中位置为3、4分配给新玩家，将B数组中3、4处的State改为U，Head移动到0处，状态结果如表4所示。

最后，清空A数组中所有玩家（4个玩家索引分别为0、1、3、4），将Tail指针所指位置1的EmptyIndex改为0,0位置处的State改为E，Tail指针右移，直到所有玩家清空，状态结果如表5所示。

表1 初始状态，视野列表为空

[1507791869793_9606_1507791865281.png]

表2分配三个位置给进入视野列表玩家的结果状态

[1507791982039_6548_1507791977596.png]

表3删除A数组中位置为2的玩家的结果状态

[1507792053094_630_1507792048576.png]

表4分配两个位置给进入视野列表玩家的结果状态

[1507792109087_9551_1507792104666.png]

表5删除A数组中全部玩家后的结果状态

[1507792169884_626_1507792165377.png]

2.2.2 双向链表

采用无序数组的一个弊端是数组中存在很多碎片，有些位置并没有存储玩家。这就导致遍历玩家的视野列表时，需要把整个无序数组A全部遍历一遍，极端情况下玩家的视野列表一个玩家都没有，但也需要遍历整个数组。因此采用双向链表辅助存储，双向链表中每个节点存储的元素和无序数组A存储的元素一样，存储其他玩家信息的对象指针，对象包含三个元素：其他玩家的指针、当前玩家在其他玩家视野数组中的索引、其他玩家在当前玩家视野数组中的索引，但所有节点都是有效的，如果视野列表无其他玩家，则双向链表为空。遍历玩家的视野列表时，只需要遍历双向链表即可，不用遍历整个无序数组。双向链表增删时间复杂度均为O(1)，将一个玩家加入无序数组A时，将其插入双向链表尾部；将一个玩家从无序数组A删除时，因为无序数组和双向链表存储的元素一样，从无序数组中拿到存储元素，将该元素从双向链表删除即可。

2.2.3 位标记

游戏中需要频繁的判断两个玩家是否相互可见，然而采用无序数组+双向链表的数据结构，最快只能采用遍历双向链表的方法，该时间复杂度为O(n)，因此采用第三个数据结构：位标记辅助完成这项工作。每个场景中的Obj数量是有限的，我们游戏每个场景的Obj数目最大为2048，ObjID编号从0到2047，每个玩家是否可见用一个bit表示。所以每个玩家共需要2047个bit表示是否与其他2047个Obj可见，即0.25M。假设He的ObjID为10，判断Me是否可见He，只需要查看Me的第10个位标记是否为1即可。

2.3 视野管理的流程

如图1所示，玩家Me从格子5移动到格子8，老视野可见的玩家为红色和绿色格子内的玩家，新视野可见的玩家为紫色和绿色格子内的玩家。首先遍历Me的双向链表，对所有老视野列表的玩家打上标签1，然后遍历紫色和绿色格子内的玩家，如果玩家He已打标签1，则将玩家He打上标签2，说明玩家He在新视野和老视野都可见；如果玩家He没打标签1，则说明玩家He是新进视野的玩家，加入EnterList；重新遍历Me的双向链表，如果玩家He仍然是标签1，说明玩家He只在老视野，没在新视野中，加入LeaveList，同时记录玩家He在玩家Me视野数组中的索引。例如Me在格子5时老视野列表里的玩家为：User1、User2、User3、User4、User5、User6；Me移动到格子8时，紫色和绿色格子内的玩家有User3、User4、User5、User6、User7、User8。首先对双向链表User1到User6六个玩家打标签1；然后对User3到User8打标签，因为User3到User6已打标签1，所以对这4个玩家打标签2，而User7、User8没打标签1，所以这两个玩家加入EnterList；再遍历双向链表User1、User2因为仍然是标签1，所以将这两个玩家加入LeaveList，同时记录这两个玩家在Me视野数组中的索引Index1、Index2。

对LeaveList的两个玩家User1、User2，首先根据User1的索引Index1从Me的视野数组A中删除，并将Me的B数组对应的位置的分配标记置为空闲，B数组的尾指针记录新空闲位置Index1并右移；将Me双向链表中User1对应的节点删除；将位标记User1对应的bit置为0。因为视野是相互的，根据Me的A数组中记录的Me在He的A数组中的位置，将Me也从User1的视野列表中删除。对User2采用同样操作。

对EnterList中的玩家，需要按照优先级高低放到不同的桶里，比如队友的优先级比其他玩家优先级高。然后按照优先级高低的顺序加入视野列表，如果视野列表已满，优先级高的玩家仍然没进入视野列表，需要从视野列表中删除优先级低的玩家，以便腾出空间将优先级高的玩家加入。对EnterList的两个玩家User7、User8，通过Me的头指针查询到Me的B数组中存储的第一个空闲位置，并检查B数组中该位置的分配标记，如果分配标记为空闲，即可将新入玩家User7放到Me的A数组中该位置，并将Me的B数组中该位置置为已分配，头指针右移；将User7对应的节点插入双向链表尾部；将位标记User7对应的bit置为1。因为视野是相互的，也需要将Me加入User7的视野列表。对User8采用同样操作。