开发笔记 (13) : AOI 服务的设计与实现
今天例会，梳理了工作计划后，发现要开始实现 AOI 模块了。
所谓 AOI ( Area Of Interest ) ，大致有两个用途。
一则是解决 NPC 的 AI 事件触发问题。游戏场景中有众多的 NPC ，比 PC 大致要多一个数量级。NPC 的 AI 触发条件往往是和其它 NPC 或 PC 距离接近。如果没有 AOI 模块，每个 NPC 都需要遍历场景中其它对象，判断与之距离。这个检索量是非常巨大的（复杂度 O(N*N) ）。一般我们会设计一个 AOI 模块，统一处理，并优化比较次数，当两个对象距离接近时，以消息的形式通知它们。
二则用于减少向 PC 发送的同步消息数量。把离 PC 较远的物体状态变化的消息过滤掉。PC 身上可以带一个附近对象列表，由 AOI 消息来增减这个列表的内容。
在服务器上，我们一般推荐把 AOI 模块做成一个独立服务 。场景模块通知它改变对象的位置信息。AOI 服务则发送 AOI 消息给场景。
AOI 的传统实现方法大致有三种：
第一，也是最苯的方案。直接定期比较所有对象间的关系，发现能够触发 AOI 事件就发送消息。这种方案实现起来相当简洁，几乎不可能有 bug ，可以用来验证服务协议的正确性。在场景中对象不对的情况下其实也是不错的一个方案。如果我们独立出来的话，利用一个单独的核，其实可以定期处理相当大的对象数量。
第二，空间切割监视的方法。把场景划分为等大的格子，在每个格子里树立灯塔。在对象进入或退出格子时，维护每个灯塔上的对象列表。对于每个灯塔还是 O(N * N) 的复杂度，但由于把对象数据量大量降了下来，所以性能要好的多，实现也很容易。缺点是，存储空间不仅和对象数量有关，还和场景大小有关。更浪费内存。且当场景规模大过对象数量规模时，性能还会下降。因为要遍历整个场景。对大地图不太合适。这里还有一些优化技巧，比如可以把格子划分为六边形 的。
第三，使用十字链表 (3d 空间则再增加一个链表维度) 保存一系列线段，当线段移动时触发 AOI 事件。算法不展开解释，这个用的很多应该搜的到。优点是可以混用于不同半径的 AOI 区域。
接下来我要来实现这个 AOI 服务了，仔细考虑了一下，我决定简化以前做的设计 。
首先是最重要的协议设计。以前我认为，AOI 服务器应该支持对象的增删，可以在对象进入对方的 AOI 区域以及退出 AOI 区域时发出消息。
这次我重新思考了一下，觉得是可以简化的。
我只打算支持固定 AOI 半径，下面是我重新设计的协议：
typedef void * (*aoi_Alloc)(void *ud, void * ptr, size_t old_sz, size_t new_sz); typedef void (aoi_Callback)(void *ud, uint32_t id, uint32_t id); struct aoi_space; struct aoi_space * aoi_create(aoi_Alloc alloc, void *ud, float radis); void aoi_release(struct aoi_space *); // w(atcher) m(arker) d(rop) void aoi_update(struct aoi_space * space , uint32_t id, const char * mode , float pos[3]); void aoi_message(struct aoi_space *space, aoi_Callback cb, void *ud);
核心只有两条协议，即最后两个 C API 。update 用来更新对象的状态；message 用来获得 aoi 消息。
这次不打算发送离开 AOI 区域的消息，而只会发送进入 AOI 区域的消息。如果对象始终维持在 AOI 区域中，尽量不发送新的消息，不确保这一点，但不会有过于频繁的消息推送。
我把对象分为两类，一类叫观察者 Watcher ，另一类是被观察者 Marker 。一个对象可以同为 Watcher 和 Marker 。在 Marker 进入 Watcher 的 AOI 区域时会触发消息。
对象用 32 位 id 表示；update 的 mode 参数用来表示这个对象是 Watcher 还是 Marker 。形式如 fopen 的 mode 参数。写上 "wm" 表示即为 Watcher 又是 Marker 。mode 还可以传入 "d" 表示 Drop 丢弃掉这个对象。
为什么不需要退出 AOI 区域的消息？我认为，在使用 AOI 服务时，往往只是用来简化比较距离的操作。收到 AOI 消息后，用户可以选择把对象加入自己关心的列表。以后在处理遍历这个列表时，有足够多的机会把不再关心的对象删掉。具体使用时，建议在对象超过两倍 AOI 距离后再取消关注。后面会看到为什么不能在对象离开 AOI 区域后立刻删除，因为那样可能导致不再收到重新进入 AOI 区域的消息。
使用时，定期调用 message 函数。每次调用称为一个 tick 。在这个 tick 里，会把发生的 AOI 事件以回调函数的形式发出来。
以上 API 很容易封装为一个网络服务，方便使用。接下来几天，我将按下面提到的算法实现这个 C 模块，并且开源。 :)
这次我不打算用打格子的方法来实现 AOI 模块。经过一番思考，我觉得我找到了一种更好的算法。
我把对象的状态分为三类。
第一类称为静止 (static) 。当一个对象在当前 tick 内没有更新坐标，就认为它是静止的。
第二类称为微动 (shift) 。当一个对象更新了坐标，但新坐标和上个关键坐标距离较小（不超过 AOI 半径的一半）时，我们认为这个对象是微动的。
第三类称为运动 (move) 。当一个对象第一次出现，或它的新坐标离上个关键点距离较大时，我们认为这个对象在运动。进入运动状态的对象会把自己的关键点坐标更新为当前位置。
在 AOI 空间中，我储存了 6 个集合对应 Watcher 和 Marker 的三类状态。一开始，这 6 个集合都是空的。
另外，在空间中还保存有四个集合，属于新增的微动对象 (shift new) 和新增的运动对象 (move new)。
在 update 函数中，新的 id 一定被加入 move new 集合。需要删除 (drop) 的 id 则简单打上 drop 标记。以前提到过的 id ，则查询更新的坐标和旧坐标的距离，更新其状态。如果有状态较之以前有改变，则分别置入 shift new 或 move new 集合。否则什么也不做。
message 函数被调用时，处理这些集合，就可以获得 AOI 消息。算法如下：
一，遍历 shift 和 move 集合，如果发现里面的对象当前 tick 没有更新，则把它放到对应的 static 集合中去。如果状态发生改变（从 shift 变成了 move 或从 move 变成了 shift ）则从对应集合删掉，因为它们已经存在于 shift new 或 move new 集合中了。如果对象处于 drop 状态，则减掉对象的引用（对象用引用记数管理）。
二，把 shift new 集合里的对象和 static , shift 以及 shift new 集合里的对象逐个比较。如果他们距离较近（两倍 AOI 半径之内），则生成一个热点对，放到热点对列表中。（关于“热点对”，下文会展开解释）。这里的比较指 Watcher 集合和 Marker 集合的交叉比较。比较双方都同为 Watcher 和 Marker 时，注意只比较一次。这很容易实现，因为可以用 id 的大小来做鉴别。
三，将 move new 集合里的对象，和 static , shift , shift new, move , move new 的对象配对一一加入热点列表。不必做距离判断。
四，将 shift new 合并入 shift 集合，move new 合并入 move 集合。
五，在每个 AOI 空间中，都有一个列表，我们称为热点队列表。每个热点对，是我们需要尝试判断是否会触发 AOI 消息的两个 id 对。这个列表里会有哪些 id 对呢？如果你理解了上面几个步骤的处理，就能想到，包含有至少一个运动对象的对象对，距离比较近的微动对象对；没有完全处于静止状态的对象对，也没有距离较远的微动对象对。我们在处理这些热点对时，比较它们和上个 tick 处理时，对象状态是否发生了改变。只要至少有一个对象对象发生了改变，就将这个热点对抛弃。（因为一定有新的正确关联这两个对象的热点对在这个列表中）对于其他有效的热点对，我们比较其中两个对象的距离，当距离小于 AOI 半径时，发送 AOI 消息，并把自己从列表中删除；否则保留在列表中等待下个 tick 处理。
以上算法略微有点复杂，但实现起来并不困难。为什么它效率很高呢？
因为，如果对象处于某种速度跨越不大的运动状态中，而 AOI 距离和运动速度相比比较长，那么，运动的对象将比较长时间的停留在微动（ shift ）状态。如果对象停止了运动，则会切换到静止 ( static ) 状态。这两种状态之间的对象，若距离比较远，他们将不会进入热点对，及不会被遍历，也没有比较距离的运算。
只有处于运动状态的对象，会在每个 tick 和其它所有对象做一次比较。而只有少数高速运动或跳转的对象会被打上 move 标记。一般微动 (shift) 的对象则以一个周期被标记为 move 。这些操作是低频的。
完全静止的对象之间的遍历和比较则完全被优化掉了。
这篇是一个粗略的想法。大概需要这周余下的时间来实现。在实现过程中，可能会发现一些没有想到的细节，届时再来修改。
3 月 7 日:
昨天花了一天实现。发现许多可以简化和改进的地方。我认为可以把 static 以及 shift 都合并到 shift ，简化处理流程。
在实现集合的时候，一开始先用双向链表。而关系对用 hash 表。实作觉得过于复杂，就简化为数组和单向链表了。每次 message 生成的时候用一个 O(n) 的遍历生成几个需要的集合。这样比维护双向链表实现的集合的变化要简洁，性能感觉也不会有太大的损失。
代码已经放到了 github 上。大致应该是正确可用的。内存分配器可以定制，如果需要优化性能，定制一个内存分配器很重要。因为运动期动态的内存增删都是一针对 pair_list 固定大小的。专门定制可以减少内存占用，减少碎片，加快速度。实现也很简单，做一个固定大小的内存池即可。有空我会实现一个默认的定制内存分配器。
关于测试，今天小 V 同学帮我写一个一个图形化的测试程序，可以直观的看到效果，并核对有没有 AOI 消息的遗漏。大体上是没有问题的。
Comments
请问您同学的图形化测试大致是怎么能够做到呢，我也想要学习一下，谢谢博主
Posted by: 墨迹 | (30) January 11, 2022 12:04 PM
有个疑问，只是简单把对象划分为marker,watcher是不是不够，仅已知的对象（不考虑策划另外添加的）就有：售卖NPC / 玩家 / 有AI自动攻击范围内玩家的怪物，怪物只需要看到玩家，不需要看到其他怪物，也不需要看到NPC，这种也给打上watcher的标记，是不是计算的浪费
Posted by: zdy | (29) November 12, 2020 10:44 PM
我去Github上拜读了你的代码，不过有些疑问。
1. 每次update的时候都需要map_foreach, 我理解下来这是要遍历一次地图内的对象列表，可是这是不是太低效了？
2. 你的优化是为了减少仅标记为marker时产生的计算量。但实际使用中，地图上的对象也仅仅是NPC有这种需求。而NPC在地图上只有很少的数量，这种优化真的有必要？
Posted by: albert.xu | (28) January 3, 2018 08:08 PM
请问直接在服务器端用box2d判断行不行，机制好像类似
Posted by: jack | (27) April 12, 2014 07:11 PM
这个感觉跟光子贴图要解决的问题很像啊，能用动态ｋｄ树吧
Posted by: thatname | (26) August 7, 2013 01:52 PM
@Cloud
不好意思我看错了..
原来是我改成c++的时将状态直接放到判断中,而原来项目中set_push已经将mode提出来了
Posted by: GodZza | (25) April 27, 2012 12:03 PM
@GodZza
没看出现在这样有什么问题
Posted by: Cloud | (24) April 27, 2012 11:47 AM
云风大大,本人使用了你的aoi代码.目前发现有一个bug.就是对象在分派到不同的4个处理列表时,如果该对象为MODE_MOVE,不应该立即取消其MODE_MOVE状态,应该在分派完成后再取消.具体在set_push 函数.
Posted by: GodZza | (23) April 27, 2012 11:16 AM
当npc在灯塔边界的时候，他的视野有可能超过灯塔照亮的范围，这时候怎么处理？
Posted by: zfgf | (22) April 11, 2012 02:46 PM
http://www.cppblog.com/Files/jaxe/AOIDemo.rar
这个是DEMO 程序。
Posted by: 浩毛 | (21) April 6, 2012 11:00 AM
就十字链表的方法是最高效的。
我以前做的DEMO 测试证明4000个移动实体相互的AOI计算只需要10多毫秒，单独做AOI服务毫无必要
Posted by: 浩毛 | (20) April 6, 2012 10:59 AM
云风大哥的微博地址多少呢？知道的留个话吧。谢谢哈~
Posted by: rainman | (19) March 16, 2012 11:32 PM
@ix
所以我的库可以动态的把对象设置被 marker ，去掉 watcher 属性。
Posted by: Cloud | (18) March 9, 2012 10:16 PM
很多单位并不需要在任意时刻知道自己aoi里有哪些单位吧,通常一个单位只在需要的时候想要遍历一下自己附近的单位,这种需要是很低频的吧.
Posted by: ix | (17) March 9, 2012 07:50 PM
博主分析的很精彩，慢慢学习消化··
Posted by: 新加坡移民 | (16) March 9, 2012 03:11 PM
请问AOI Shower可以开源吗？
Posted by: Anonymous | (15) March 9, 2012 01:42 PM
非常期待中……
Posted by: 感悟人生的句子 | (14) March 9, 2012 09:34 AM
差距啊， 太懂 膜拜
Posted by: crazy | (13) March 9, 2012 09:12 AM
懂了。shift(static)和shift new差别巨大。
学习了。还不会出现打格子那种聚堆退化的现象。
Posted by: yy | (12) March 8, 2012 03:49 PM
“把 shift new 集合里的对象和 static , shift 以及 shift new 集合里的对象逐个比较。如果他们距离较近（两倍 AOI 半径之内），则生成一个热点对，放到热点对列表中。”
这一个步骤，感觉也是很耗时。
shift的人占绝大部分，而shift与各shift集合之间都已经逐个比较了。对实际优化效果表示怀疑。
如果对这一步进行网格优化，感觉又和直接网格差不多了。
Posted by: yy | (11) March 8, 2012 03:32 PM
沙发有点亮。。。。
Posted by: callee | (10) March 7, 2012 04:39 PM
不错学习了！
Posted by: www.khkpw.cn | (9) March 7, 2012 04:29 PM
move new 集合增删操作，需要保证线程安全么
Posted by: foman | (8) March 7, 2012 04:13 PM
每天都在关注开发日志，不过从头读来，发现云大侠不爱画图，我没有太多游戏开发相关的开发知识，很多只能停留在表面想想，看看热闹。云大侠是热爱技术，乐于分享的，不忙的时候能不能讲些基础的，比如常用的开发工具，游戏架构层次（通常有哪几部分组成），常用的开发模式，服务器选型等。也想从整体看看游戏是怎样练成的。
Posted by: alex | (7) March 7, 2012 03:11 PM
MARK，期待。。。。
Posted by: CoolDesert | (6) March 6, 2012 06:36 PM
类似于ospf的方式，每个对象记录相邻对象的位置，避免孤岛存在，运动时，更新自身相邻对象位置表，通知相邻对象更新自身表。
Posted by: elffinal | (5) March 6, 2012 04:27 PM
@Zooks
shift 的价值在于
shift 和 shift 以及 shift 和 static 对象间, 如果距离大于 2 倍 AOI 半径就再接下来的时间不再处理了.
直到 shift 对象变成 move 对象.
直观说, 当两个对象间隔很远, 我们很长一段时间都不要管他们两.
Posted by: Cloud | (4) March 6, 2012 01:12 PM
多谢分享。
从本质来说，通过划分，减少运算。
区域内的对象，分为了 marker 和 watcher
移动幅度，分为了 static shift move
不需要处理 static marker 能减少许多遍历，这是肯定的。
但是 shift 价值是什么？
没有减少遍历，每个 shift marker 都需要遍历 watcher 对象。
也没有减少比较对象距离的操作。shift 对象，需要比较距离，才能判定是否需要结为热点对；而 move 对象，也需要比较距离，才能判定是否发送 AOI 消息。
那么，shift 和 move 还有区别么？
并且，还需要计算一次与上次位置的距离，才能区分 shift 与 move 。运算反而增加了？
Posted by: Zooks | (3) March 6, 2012 11:44 AM
居然没有人回复？沙发
Posted by: fnsoxt | (2) March 6, 2012 11:38 AM
请问博主是搞网游开发的吗？那游戏中的人物形象设计需要一些3D软件吗？
Posted by: 平面设计 | (1) March 6, 2012 09:03 AM