AOI:实现原理

以你之姓@ 2022-09-05 00:20 195阅读 0赞

1 AOI简介

AOI的全称叫Area Of Interest，感兴趣的区域。这个技术可以看做是服务器广播的一种。在MMO类型的游戏里是必须存在的。

MMO类型的游戏都会有野外和主城场景，一般来说，服务器只会同步你周边多少半径以内的玩家给你，太远的一是玩家屏幕看不到没有意义，二是同步太多的玩家对于服务器压力成倍数上涨。

想象一下，如果一个区域内有100个人，这些人可能都在不停的走路，如果是广播形式的话，那每一个人移动都要向另外的100个人进行位置同步。假如服务器每50ms同步一次玩家位置，那么服务器处理100个人位置就需要100\*100\*20 = 20万次广播。这显然是无法承受的。

那么为了降低这部分的服务器性能，就需要降低服务器同步的量级，一种解决方案就是AOI。核心概念就是只对那些感兴趣的观察者发送数据。基于上面的例子而言，如果我们能把这个区域细分为10个，假定平均分配的情况下，每个区域里则只有10个人。那么此时每个人移动的时候，他就只要同步给同区域的10个人，大大减少需要同步的次数。同时，如果我们能充分利用现代CPU的核数，使用多线程来处理，则这个部分的性能损耗会大大的降低。

但这个方案同时也会带来额外的问题，比如a这个人，之前在A区域，现在移动到了B区域，那么就需要一个管理器来协调A和B两个AOI区域的数据更新。虽然区域划分的越多，需要同步的次数越少，但是同样的，管理的复杂度就越高。所以，AOI需要根据实际的游戏场景做到一个合理的平衡。

2 AOI实现

基于上述的AOI理念，发展到现在会有一些相对成熟的方案。简单来说有三种，1广播 2九宫格/灯塔 3二维链表。我们大致介绍一下，不展开。

2.1 广播

广播其实就是暴力扫描了，这是最简单粗暴的方式，就如同前面所说，只要有变化就广播给所有人。这种看似很蠢的方式在以前的页游中用的还是比较多的。比如早期像《神仙道》这种页游，（PS:举例是说明游戏类型，并非指他们用的这种方法，实际上这个游戏过于久远，我没有研究过他们的方式，但早期我们自己做横版页游的时候就是广播通知）。一个场景地图 一般也就能承载几十人，大部分还是在打坐休息的，超过人数上限的可能会被调配至2线，3线这样。

2.2 九宫格/灯塔

九宫格和我们常规理解的九宫格相似，也就是说1个玩家所关心的内容其实就是跟他相邻的8个格子，如果算上他自己所在的格子的话，一共就是9个格子。MMO类型的游戏，大部分时候，人物是不会产生体积碰撞的，也就是说有多个人和自己站在同一个格子是肯定的事情。从另外一个方面来讲，我们所说的格子其实只是逻辑上的格子，它和场景上实际划分的单位格子之间会有一个映射比例，比如逻辑1格等于场景上的10X10，所以9宫格要关心的并不是8个格子而是9个。

好比这张图，B所关心的就是以B自己为中心的9个格子。

但灯塔是九宫格的一种改良，同步数据，不会再以某个玩家为中心。而是划分为一个watch点，这个点就像一个灯塔一样，监控它范围内的entity。当有玩家进出的时候，它会上报给上一层的管理器，然后管理器通知不同的灯塔做增删，如果只是在自己的灯塔范围内变化，它只会同步给自己监控范围内的entity。

就好比这张图，如果按照传统九宫格的话，B变化的时候A是不会得到通知的。但是如果把蓝色的点看做是灯塔的话，那么B变化，A会收到通知，因为它们归属在一个灯塔范围中。

灯塔相比于九宫格来说，更加的灵活。虽然一定程度上增加了同步数量，但是它也减少了九宫格那种以自己为中心的区域数量。甚至灯塔可以自由配置大小，这在一定程度上可以认为的降低服务器不同区域的负载。比如魔兽世界这种，刚开服的时候，可以把新手区的灯塔配置的小一些，密集一些。等开发一段时间后，逐渐向高等级区域转移，以减缓服务器的负载均衡。

2.3 二维链表

一般游戏的区域同步都是以地面作为划分依据的，不会存在于三维空间。如果要存在那就是另外的算法了，不讨论。以平面为参考，就可以将其分成x轴和y轴两个链表。并将每个对象按照坐标值从小到大相应的排列在相应的坐标轴上面。

这么做有两个好处，第一能够快速给新插入的对象进行排序（顺着链表找就好了），第二就是能够快速定位该对象的变化需要给哪些对象发送消息。

比如有一个已经排好序的对象集合，按X轴坐标排序:

a->b->c->d->e->f->g->h

如果这时候新增了一个z，位于c和d之间，那么查找之后添加的位置就是。

a->b->c->z->d->e->f->g->h

这里会有个很严重的问题，链表是二维的，也就是说你必须在X和Y链表上各排一次，如果对象数量少还没什么有影响，对象数量多的时候，排序算法会严重影响AOI的性能。

三种方法，从性能和便捷程度而言，第二种即九宫格/灯塔的方式是普遍，最好的。

3 世界地图上的AOI

介绍完AOI的原理和实现之后，我们要说说它在SLG类型上的应用了。世界地图是一个超大的沙盘，理论上它可以看做是MMO游戏的开放性大场景。只不过和MMO不同的是，沙盘可以上帝视角跳转到任何地方，当然也要说MMO也可以出定点传送功能也没问题。但从传统的实现上看，沙盘的AOI需要比MMO更快的切换和响应。同时，一般玩家进入地图的时候，总是会以自己为焦点，在一定的区域范围内滑动查看情况的。

综合上述的游戏特点，我们的服务器使用了一种改良方案，九宫格+灯塔的模式。首先世界地图肯定是可以缩放级别的，也就是说玩家缩放了视角之后，能看到的东西就会更多，那么这在一定程度上会要求服务器以比最大视角更大的区域进行同步方能展示全部信息。这部分使用灯塔实现。

另外我们会左右滑动屏幕以拖拽地图，这样就有可能离开自己所处的灯塔范围，当玩家正好停留在多个灯塔的交接处的时候，那么就需要同时同步多个灯塔的变动情况，尤其是行军队列这种移动的AOIEntity。哪怕你停住不动了，它也会在不同灯塔范围进行切换，这个时候，不同灯塔之间的数据组合可以看做是相邻九宫格。

这里同步数据的最核心交互是客户端的焦点。也就是说服务器下发的数据，基于客户端提供的视野焦点。灯塔的另外一个好处就是，客户端可以不停的上报焦点，但是服务器可以在一定程度内不理睬这条协议，只要你不离开当前的灯塔范围。但也会有极端情况，就像刚才说的，正好处于多个灯塔范围的时候，需要同步多个灯塔内容。

4 AOIEntity的类型

从前面的系列文章中已经有了一些说明。世界地图的每种元素都是需要同步的，这些需要同步的元素都是Entity的一种。它大概包含了十几二十种。其中大部分是属于静态的，比如怪物、矿点、玩家城堡、要塞、神殿等等。最难处理的其实就是行军的这种动态元素。

行军有很多种，比如集结、采集、攻击怪物、攻击玩家、攻击要塞等等。对于不动的元素，只要维护一张static的表即可，每次要同步的时候全部送给客户端。对于移动的元素，除了行军之外，还有玩家焦点，并且应该是以玩家焦点为主，筛选不同的世界元素进行推送。当然这部分是服务器的实现，再次就不做过多介绍，等我们服务器大佬有空会公布出来的。

5 客户端AOI

那前面说了那么多，都是跟服务器相关的，客户端不就是接受显示就完事了么？

对、肯定、没错。但如果只是这么做的话，就只在第一层。前面我们说了，服务器推送的AOI比我们实际的范围要大，严格来说要大很多。因为玩家要移动地图肯定都是以最高视角移动的，这样一次移屏的距离才最高。也就是说，这种情况下，客户端接收到的AOI数据有很多是视野外的，不需要显示的。

如果客户端不作处理，照单全收，服务器推多少就创建多少，创建完不在摄像机视角内又要剔除不是白做无用功吗？

所以，客户端在服务器大的AOI区域内又嵌套了一层小的AOI，用来管理显示区域的内容。也就是说，客户端和服务器同步实际的AOI区域数据，客户端基于当前的数据和当前客户端的AOI范围进行数据裁剪，以最大限度的减少无用的创建和剔除。这会大幅度提高世界地图的渲染效率。  
   
原文链接：https://blog.csdn.net/awhlmcyn/article/details/119006846

[https://blog.csdn.net/dcldz5007/article/details/102286288][https_blog.csdn.net_dcldz5007_article_details_102286288] 简易AOI

[https_blog.csdn.net_dcldz5007_article_details_102286288]: https://blog.csdn.net/dcldz5007/article/details/102286288