AOI的概念

AOI（Area Of Interest），通常是指服务端对玩家感兴趣领域的划分的技术。
这个技术的应用场景是服务端存在非常多的单位，客户端不需要渲染所有的单位，服务端也可以避免将所有单位的信息广播，所以其目的是降低客户端的渲染压力、减小服务端的带宽压力。

这个问题的指导思想就是：世界很大，我只看眼前，我只关注周围的单位，太远的单位我并不关心。

好久之前有一个小朋友问过我，背那些算法和数据结构的八股文有什么意义，我当时跟他说，这是你翻身的武器，我们不要文凭，不要出身，只要你能背下八股文就能给你高薪的工作。
同时他们非常有用，在你深入做底层问题的时候，本质上就是面对CPU、内存、数据结构和算法，早就是脱离于语言存在的东西。

问题简化

AOI问题是一个实际应用中常见的优化问题，把它抽象成一个算法题的话应该是这样。你要维持一个数据结构，能够快速地获取周边足够近的n个单位，同时能够快速地修改所有单位的坐标。

目标就很明确了，需要一个快速获取某个单位或者某个坐标周围足够近的单位，这个足够近是项目自己定义的，它可以是距离，也可以是某种近似。

这里提到了两种思路，也代表了坐标计算的两种思想，既可以围绕单位做数据结构，也可以围绕坐标做数据结构，他们带来的优劣也会很明显体现在单位和坐标上。

基于单位设计数据结构，那就应对大量的单位就是难点；基于坐标设计数据结构，那核心要解决的难点就是如何应对更大的坐标和世界。

常见解法1： 遍历

直接遍历游戏中的所有对象，然后比对距离就可以了。

其实moba、fps的场景不太关注AOI，或者说关注的方式是有不同的，它们关注的更多不是能不能见，而是要见哪些数据，这篇我先不展开讨论，有机会再展开聊。

在这种少量玩家开房间的游戏场景，如果有AOI更多也是为了防作弊，毕竟客户端不会有大量的渲染压力，降低渲染压力才是这个问题的核心目的。

但对于同屏上百上千的单位的MMORPG游戏而言，这个方案肯定是会卡死服务端的。

常见解法2： 九宫格

这个是围绕坐标设计的数据结构，思路很简单，将整个世界按照固定的格子大小，均匀地划分成很多个格子，然后维护每个格子里的单位列表。

单位进出和查找都是O(1)的，它很简单而且高效，但缺点也很明显，基于格子设计的问题就会出在格子上：

缺点分析

首先的问题是，应对大世界的地图占用内存过高，而且内存使用率低，可能有大量的格子是空的；
当然这里可以用稀疏矩阵去维护这个格子，但是这样进出和查找的时间复杂度就可能是O(n)了。

本来还想提一下格子内单位数量过多，但是这个问题好像是所有AOI都会遇到的通用问题，即使做了AOI，同一个城镇甚至同一个NPC前面可能站着上百上千个玩家，这个时候任何AOI算法都不生效的，只能去做分层。

所以不算这个算法特有的缺点。

常见解法3： 十字链表

这个是围绕单位设计的数据机构，每个单位会存在两条x-y方向的链表上，能够非常快速地遍历在关注单位周边的单位，查找节点很快是因为可以用O(1)的复杂度获取一个最近的单位。

就像前面说的，这个算法更多的是收到但数量影响，当单位数量非常多的时候，坐标修改可能涉及到频繁地链表进出的计算。

常见解法4： 灯塔算法

灯塔算法算是结合了遍历和九宫格的算法，如果只有一个灯塔它就退化成了暴力的遍历算法，如果按照均匀地划分成九宫格，它就退化成了九宫格。

相比九宫格是固定格子的划分，灯塔是可以立一个灯塔圈定一个范围，所有进入这个范围的单位都需要在灯塔登记一下，那玩家AOI的区域就需要找附近几个灯塔，并且遍历里面的所有玩家。

优点：结合了坐标+单位，变得很简单，并且在部分场景能够很好的运行
缺点：结合了坐标+单位，即跟场景大小有关，也跟单位数量有关，这里需要很细致的优化

必要解法： 分层

就像在九宫格的缺点分析里提到的，无论是哪种AOI算法，它都无法解决一个npc面前有成百上千玩家的应用场景，所以分层是所有算法之上都要做的事情。

总结

就写这些吧，后面慢慢补充。

参考

https://www.modb.pro/db/177776
https://blog.csdn.net/haha1fan/article/details/129122406
https://blog.codingnow.com/2012/03/dev_note_13.html
https://iyichen.xyz/2020/04/talk-about-aoi
https://wykxwyc.github.io/2022/04/23/How-AOI-Work-in-Games/

End.