云风的 BLOG: AOI 服务器的实现

以前谈过多次 AOI (Area of Interest) 的实现，因为我们的游戏尚在开发，模块需要一个个的做。前期游戏世界物件不多的时候用个 O(N^2) 的算法就可以了：即定时两两检查物件的相对距离。这个只是权益之计，这几天，我着手开始实现前段时间在 blog 上谈过的独立的 AOI 服务器。

既然是独立进程，设计协议是最重要的。经过一番考虑，大约需要五条协议，四条是场景服务器到 AOI 服务器的（列在下面），一条由 AOI 服务器发送消息回场景服务器。

创建一个 AOI 对象，同时设置其默认 AOI 半径。注：每个对象都有一个默认的 AOI 半径，凡第一次进入半径范围的其它物体，都会触发 AOI 消息。
删除一个 AOI 对象，同时有可能触发它相对其它 AOI 对象的离开消息。
移动一个 AOI 对象，设置新的 (2D / 3D) 坐标，并给出线速度的建议值。
设置一个 AOI 对象相对另一个的 AOI 半径，覆盖其默认设置。注：AOI 半径可分两种，一为进入半径，二而离开半径。通常一开始，每个 AOI 对象为其它对象均设置一个进入半径；当消息触发后，由场景逻辑重新设置一个离开半径。例如，一个 AOI 对象的默认半径是 10 米，当它被创建并指定坐标后，任何物体进入它的 10 米范围内，都会立刻由 AOI 服务器发送出一个 AOI 消息；而后两者之间不会再自动触发消息。场景服务器收到消息后，可主动向 AOI 服务器设置新的 AOI 离开半径 12 米，当此物体远离到 12 米远后，离开消息触发；下一步再由场景服务器重置进入半径。

这套协议相对简单，可以满足游戏的一般需要，并隐藏 AOI 服务的实现细节。对象全部由 handle 方式传递，由场景服务器自己保证 handle 的唯一性。在我这次的实现中，每个 AOI 对象同时只能拥有一个 AOI 半径触发器，但是协议本身无此限制。

下面，我们再来看一下实现细节。

一般的 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 服务的一个框架了。实现它们还需要两三天时间。

Comments

有位兄台提到用“折线法”将二维坐标信息降维到一维进行处理。有一点没有说到，即玩家坐标改变后，已经排好序的数组要更新，这个也可能比较耗时。

Posted by: lua | (13) March 30, 2015 11:21 AM

小哨兵的故事:
>-------------------------------------
一个装备了一支射程为 500m 步枪的士兵, 蹲在了一个瞭望塔里....
因为他很喜欢完PSP....
所以他绝对在不影响工作的情况下, 尽量满足自己的PSP欲望....
....
一天, 一个叫"刘翔"的人出现在2000m左右的范围内,
哨兵发现了...
但是他的射程没有这么远...拿"刘翔"没办法...
他估计了"刘翔"的速度是V = 10m...
他开始执行如下操作:
1. 预计刘翔进入射程的最短时间是T = dS/V;
2. 开始玩T时间段的PSP;
3. T时间之后..再来估算dS..然后返回"1.";

Posted by: ViCross YISA | (12) December 11, 2008 11:12 PM

特别喜欢看呼朋唤友的NPC打架。^^

p.s.: 搜索npc，您还会来到http://www.npc.gov.cn/zgrdw/home/index.jsp这个地方。

Posted by: 逗 | (11) November 27, 2008 09:08 AM

刚才写了不少错别字,aio应为aoi ,

Posted by: Anonymous | (10) November 26, 2008 01:29 PM

昨天晚上想了个方法。想象1个从地图左上角开始，向右下角的水平逐行扫描线（类似CRT的电子枪扫描轨迹），
那么，这个轨迹上一定包含有全部的点（也就是地图中的对象），每个对象都有唯一的1D上的扫描距离，
也就是相对左上角的扫描折线段长度。

首先，
对每个对象计算其扫描折线长度，Obj.y*(mapwidth+1)+ obj.x +1 , 结果与其handle结合1个记录，全部的点计算完放在数组中
然后按照地图的垂直高度为每个水平扫描线起点计算1个起点距离，Line*（mapwidth+1），赋予0handle也加入数组，
（这里对地图做了虚拟扩展1单位，原有对象在新虚拟图中水平有1单位offset , 可知每个水平扫描线的起点折线长度值一定是唯一的，）
对结果数组按照其折线长值做快速排序。对排序结果2分查找出全部水平扫描线起点在排序结果中的位置保存在数组中。

下面开始正式获取每个物体的AOI对象集合。

对物体做循环，

设循环条件 Y = (Obj.Y - r) ~ (obj.y + r)

可得到其在当前 Y 扫描线与obj aio圆形相交点的水平offset及相交线段的宽度w。涉及1个三角函数，可以查表近似快速计算。
按照该offset和y可知该交点的折线距离crossd，
从前述全部水平扫描线位置数组中获得对应的该水平线段在排序结果中的起点下标Low和下一水平线段的下标high.
在low 和 high-1之间做2分比较，得到位置 pos ( V[pos] <= crossd < V[pos+1]);
从pos起就是该水平坐标上处在obj aio圆中的连续物体，一直向下取直到物体的折线距离增长超过宽度w

2*r个循环下来就得到了该物体的全部aio对象。

做了测试，设地图为10k x 10K单位，对象10k个，全部具有40的aio半径，全部计算1次的代价大约是50ms (P4 3.0G)
这个算法速度与地图大小无关，只和对象数量及aio半径有关。也没什么内存占用，而且在遍历物体aio对象的时候
还可以进行多线程并行处理。

Posted by: Anonymous | (9) November 26, 2008 01:25 PM

AOI 服务器是什么服务器？头一次听说~

Posted by: 星际工作室 | (8) November 26, 2008 11:07 AM

= =!
刚才说错了，应该是叫做递归逐维分组

Posted by: sjinny | (7) November 26, 2008 09:51 AM

为什么没有使用四叉树之类的呢？GPG里介绍过的那个递归逐维排序怎么样？

Posted by: sjinny | (6) November 26, 2008 09:40 AM

AOI 的問題和碰撞檢測很相似，如果以半徑作為 intersection test 的話，那就是 sphere 的碰撞檢測。可以使用碰撞檢測 broad phrase 的 sweep-and-prune加速，其平均複雜度是O(n)。

以前的項目曾做 n-dimensional vector 的 AOI，除了地理的 dimension (e.g, <x,y>, <x,y z>)，還可以加入例如物件的類別、HP等等。

不過碰撞和 AOI 有一點不同，就是 AOI 有 subscription 和 publishing region，即是要檢測兩個 sets 的交集，而碰撞則只有一個 set (of collision shapes)。