多人游戏AOI

玩家交互分类

1. 玩家和npc的交互（异步）
2. 玩家和环境的交互（同步）
3. npc和环境的交互（异步）

AOI (Area of Interest)

当玩家进行移动时，同时也会对玩家范围内的玩家进行广播位置同步，使得其他玩家知晓当前玩家进行的移动位置和移动范围。当玩家进入一个游戏场景时，玩家所看到的各种各样的Entity（玩家，NPC，怪物）都是通过服务端的AOI系统进行处理

AOI

九宫格

所谓九宫格，是把场景内的所有实体的位置按照格子划分，譬如划分成边长200的正方形，要找出中心玩家AOI范围内的其他实体，就把这个范围内设计到的格子内的玩家都做一边比较

灯塔（九宫格优化版）

灯塔算法就是是把整个场景通过不同的粒度，利用网格划分成一个一个的大小相等的小区域， 在每个区域里树立灯塔。在Entity进入或退出格子时，维护每个灯塔上的Entity列表。灯塔好在哪？假设我们想知道某点周围10格内有哪些Entity，在没有灯塔的情况下，我们需要遍历所有的Entity计算其是否在范围内，随着地图内的Entity越来越多，查找的效率也会越来越差，所以我们需要一种方法来过滤那些明显不需要参与计算的Entity，所以我们将地图分割成一个个区域，在其中心放置一个假想的"灯塔"，每个"灯塔"都会保存区域内的Entity，这样当我们需要知道某点周围10格内有哪些Entity时，我们只需要计算出范围内有哪些"灯塔"，然后获取这些"灯塔"保存的Entity列表，针对这些Entity进行计算就能节省大量计算

• 优点
  • 实现简单
  • 相较于暴力法，灯塔法将大量Entity分散到了多个灯塔中，对于每个灯塔还是 O(n*n)的复杂度，但由于把Entity数据量大量降了下来，所以性能要好的多
• 缺点
  • 存储空间不仅和Entity数量有关，还和场景大小有关
  • 浪费内存（由于某些区域可能没有Entity存在，但是仍需要对其申请固定的内存，对内存有所浪费）
  • 且当场景规模大过对象数量规模时，性能还会下降。因为要遍历整个场景。对大地图不太合适

十字链表

十字链表算法是根据二维地图，将其分成x轴和y轴两个链表。如果是三维地图，则还需要维护多一个z轴的链表。将对象的坐标值按照大小相应的排列在相应的坐标轴上面。所谓十字链表，即把地图坐标轴中的 X 和 Y 轴看成是2个链表，将玩家的 X 坐标按照从小到大插入 X 链表，将玩家的 Y 坐标按照从小到大插入 Y 链表，查询时根据玩家的坐标分别从2个链表中取出范围内的所有玩家，对两个玩家列表做交集，即为我们需要发送消息的玩家列表3。

• 优点
  • 节省内存空间，没有Entity那么就不会占用内存空间
  • 由于是有序链表，可以采用二分法进行快速搜索
  • 由于链表特性插入和删除不会那么麻烦
• 缺点
  • 大数据量的搜索性能还是有待提高、但是可以通过跳表等进行优化