AOI

AOI 全称为Area Of Interest 在大型多人在线网络游戏中，一个人的行动想让其他人知道他的变化，则需要通过服务器广播消息给其他人，这样其他玩家的客户端就能够感知到并进行显示。 如何管理这些信息同步的发送，就是AOI要做的事情。

最简单的做法，一个人物的行为通知整个游戏世界的其他人物，对于一些局内竞技类游戏来说，一把游戏里面十来个人，或者百来个人，没有什么压力。 但是对于一些大量玩家在一个地图里的游戏来说，这个方案就是无法承受的，因为广播次数会达到n²级别。

在网上搜索资料大多看到几种做法

• 格子
• 十字链表
• 四叉树

对于单个角色（玩家，NPC，怪物，或者其他一些物体）来说，他们感知的范围不一样，例如玩家，玩家只关心自己屏幕上能够看到的。 所以当一个角色产生行为时，只需要通知能够感知到自己的那部分角色。 对于角色的感知范围，需要维护有，

• 有角色进入
• 有角色离开
• 角色感知范围改变
• 等等

格子的算法是将整个游戏地图切分成一个个格子，这样角色能快速遍历出自己附近的格子的其他角色。 简单，方便，但是要把一个地图的格子都初始化出来，比较浪费内存。

对于链表来说，动态分配内存，就不会担心浪费内存的问题。维护两个双向链表结构体，一个x轴一个y轴。 对于每一个node节点，有一个row和col，横向和纵向，横向和纵向都可以向前后移动。插入和删除可以用跳表的方式快速定位，节点就算多时间复杂度也不会高。

因为不同的角色监视范围可能不一样，所以当一个角色(A)被另一个角色(B)监视的时候，有可能角色(B)的行为不需要通知角色(A)，但是角色(A)的行为要通知角色(B)， 那角色(A)有行为的时候，就不单单需要通知角色(A)可视范围内的玩家。 因此分为两个大类，监视者和被监视者

当一个角色(A)首次进入世界时，可以根据自己的范围来遍历出范围内的其他角色，让其他角色的被监视列表加入该角色(A)。 如何快速确定该角色(A)被哪些角色监视了。简单做法当然是遍历范围外的其他角色，看看这些角色的监视范围有没有监视到该角色(A)。 还有监视范围内的其他角色离开了这个范围，该如何从被监视列表中删除角色(A)。

在网上搜索相关资料。 看到一个做法是增加哨兵。在一个角色的感知范围边界增加哨兵，这样，当角色移动和进入世界时，可以通过范围内的哨兵，来确定自己是否进入了某个角色的范围或者离开了某个角色的范围。 但是这种做法会导致节点数量翻倍。 角色移动的时候可以在通知的时候计算距离判断是否离开范围。 但是进入世界的时候，不用哨兵目前只想到遍历所有角色。O(n)的复杂度，也还能接受。

四叉树的解决方案也是分格子，将一个大地图，分为四块，然后这四块分别再分为四块。也就是四分， 比格子好的地方在于，不用为整个地图提前分配内存，用到哪块再创建。 给定四叉树的深度，就能确定每一块小格子的编号。设深度从0开始 深度为2的四叉树有64个叶子节点

设定好哪些坐标属于哪些编号。

新建节点时，跟附近的节点(如果已创建)互相建立关系near 当需要广播时，给角色格子的near格子发送消息。

另外还看到云风一个blog，看了下github代码

首先在每一个图里，将对象分类两类，watcher和marker，观察者和被观察者

然后这两类里面，还细分为，static和move，静态和移动的

这样就一共有四个小类，

• watcher_static
• watcher_move
• marker_static
• marker_move

维护一个链表hot，热点对，每一对是一个watcher和marker

一个哈希表+链表map，，维护所有热点对象

每次修改时，标记对象的mod，就是static或者move，还有记录上一次距离。

然后检查热点对，每一对对象在超出aoi半径一定距离的时候，才会删除，但是超出半径不通知，在半径内的才会发消息通知。

再然后重新标记mod。标记的对象会互相检测是否需要生成热点对。

不解的地方在于，代码看起来如果一个图内有大量的移动对象，互相检测会导致n²的复杂度。 好处是如果短时间内移动对象少的话，效率不错，该方案实现也简单。