游戏算法-AOI基本介绍

一、直接比较所有对象

最直观也是最效率最低的一种方法。当一个事件发生，我们需要获得AOI范围以内的物体时，直接遍历游戏中所有的对象，并且进行坐标判断，如果小于或者等于AOI的范围，则为需要的游戏对象。

这种方法实现非常简单，但是带来的问题是当游戏世界中对象较多时，效率会直线低下，一般用于FPS的游戏，一般的用户不是很多，比如守望先锋，都可以不用考虑AOI方案。

二、空间切割监视的方法

将空间按照一定的方法进行分割，例如根据AOI范围的大小将整个游戏世界切分为固定大小的格子。当游戏物体位于场景的时候，根据坐标将它放入特定的格子中。

例如玩家1在位置7中，如果游戏内的AOI的范围为1个格子。当我们需要获取这个玩家周围的AOI对象时，只需要遍历7周围9个里面的对象即可。

可以看出空间分割在计算AOI对象时，只需要遍历周围几个空间格子即可，大大提高了计算效率。但是该方法也有缺点，格子数和空间大小成为正比，空间越大，所需要的内存空间也越大。果玩家数里远远小于空间的格子数，使用这种方法来计算AOI可能比第一种算法还差。

三、十字链表

格局物体的X,Y坐标分别建立两条链表A、B。在链表A上，根据对象的X坐标进行排序；在链表B上，根据对象的Y坐标进行排序。如果游戏世界内有下列坐标的对象：

（2，2），（3，4），（6，5），（1，5），（3，1），（5，2）

那么在十字链表里有如下数据结构：

当我们需要知道一共对象AOI范围内所有对象时，只需要在X、Y两条链表上向两个方向遍历即可

 X链表，——> 按照X坐标排序

Y链表，——> 按照Y坐标排序

十字链表发在计算AOI范围内对象时，计算量非常小，且跟空间大小无关，因此省去大量无效的遍历过程。除了这些优点外，十字链表法也有一些需要注意的地方，因为在两条链表中都必须按照大小顺序进行排列，因此对象在不停的移动，会带来比较大量的计算。

参考资料：

《游戏开发》-网易互动娱乐事业群

云风blog：云风的 BLOG: 开发笔记 (13) : AOI 服务的设计与实现

深入探索AOI算法：深入探索AOI算法 - 知乎