一般的 AOI 模块有两种实现方式，最常用且最简洁的方式是打格子。无论是小格子也好（一格只能占一个对象）还是大格子也好（一格是一个较大区域，在区域内再使用 O(N^2) 算法逐一比较），实现起来都很清晰明了。

按 KISS 原则，我建议没有特殊需求的情况下都使用格子的算法。当然，格子算法也有一些不足，比如格子本身的内存消耗，跟场景规模有关，却与对象实现无关，有时候，会浪费大量内存（独立进程可以一定程度回避这个问题）；对于变化不定的 AOI 半径，固定单位长的格子方案在效率上也略有缺陷。

另一个思路是几年前我在和天下组的同事聊天时了解的。为每个对象创建两或三个维度上的线段，并对线段端点做插入排序。我本身对这个算法不太感兴趣，就不展开谈了。

昨天晚上躺下比较早，翻来覆去睡不着，想到一个新的思路来实现 AOI 模块。

最 KISS 的方案是每个心跳一一比较 AOI 对象的距离。时间复杂度是 O(N^2) ，在 N 比较小时，其实是最佳方案。因为其实现非常简单。注意这里，对于 A 和 B 两个对象， A B 和 B A 是两组。这是因为 A 的 AOI 半径和 B 的 AOI 半径很可能不同。那么对于 N 个对象，要比较 N * (N-1) 次。除非游戏中玩家都在小副本中，且副本里的 NPC 数量不多（或者 NPC 之间不需要做 AOI ）不然在大规模场景中难以接受。

btw, 所谓被动怪，就是不需要做 AOI 处理的 NPC 。在很多游戏中大量放置，除了帮助脑残玩家快速升级外，也是为了节省服务器资源。wow 中那些 NPC 之间也会野外碰见并交战，NPC 间会呼朋结友一起上的设计，其实是很考验 AOI 模块性能的。

应该如何提高 N 比较大时的性能？

我们主要，相隔较远的物体，是不需要时时检测它们之间的距离的。而大部分物体间隔都远超双方的 AOI 半径。我们只要从这里着手改进算法就可能得到很大的性能提高。

比较容易想到的是使用一个timer。我们可以根据两个物体间的距离，以及移动速度，估算出一个最短相遇时间。这个时间往往远超一个心跳。按这个时间，把 AOI 检查放到 timer 队列里即可。

我在实现时是这样做的：要求场景服务器在发送物体坐标时，同时发送一个线速度的建议值。我按这个值的两倍计算物体两两间的相遇最短时间，并注册 timer 。以后只要不超过这个速度的两倍就可以忽略它。否则，重新计算跟这个物体相关的所有目标距离，调整对应的所有 timer 在 timer 队列中的位置（这需要特制一个 timer 模块来提供这个功能）。

这个优化依旧有一个问题。它需要为每对物体创建一个 timer 节点。所以空间复杂度是 O(N^2) ，这可能大大超过内存预算（虽然独立进程也可以缓解这个问题，但只要想一下，N 可能上万，就知道问题有多严重）。

我们需要进一步的优化。

在游戏中，大部分对象是老死不相往来的，由于是那些身处各地的 NPC 。只有极少数出生地不同的 NPC 会由于脚本设计游走各方。而玩家，那些有可能大范围活动的对象，相对 NPC 的数量又是少了一个数量级。我们只要在内存中除掉这些无谓的数据就好了。

假设半径 100 米在游戏中是一个比较大范围，NPC 没事不会超过这个活动范围，而玩家一般情况下跑过 100 米也需要一段时间（这要花上好几秒，秒对于 CPU 是个很长的时间单位）。

我们可以给所有对象设置一个 100 米为单位的活动范围。如果两个对象之间的直线距离大于 200 米加上他们的最大 AOI 半径，我们就可以不记录这两个对象之间的关系（认为它们不可能相遇）。而一旦一个对象离开它原来的记录原点超过 100 米，就认为它发生了迁徙，立刻把它对场景中所有的对象重新做一次比较（时间复杂度 O(N) ），这个操作固然慢，但是还可以接受，而且并不常发生。
 

关于AOI服务器的优化