云风的 BLOG: AOI 的优化

去年写过几篇过于 AOI 模块的设计。将 AOI 服务独立出来的设计早就确定，并且一定程度上得到了其他项目组的认可。（在公司内部交流中，已经有几个项目打算做此改进）

最近一段时间，我在这方面做进一步的工作。（主要是实现上的）

首先，基于 KISS 的考虑，删除了原有协议中的一些不必要的细节。比如，不再通知 AOI 模块，对象的移动速度。移动速度虽然对优化很有意义，但毕竟是一冗余数据。考虑这些，容易掉入提前优化的陷阱。

其次，增加了一条设置默认关心区域的协议。这是出于实用性考虑。

原本的考虑中，我希望应用者按需为每对实体设置 AOI 消息。但是，当场景中实体过多时，将浪费大量的进程间通讯带宽（内存和处理速度上倒是可以优化）。往往，一个 AOI 实体不会关于过远的其它实体，所以增加一条协议，可以缩减大量的模块间交互。即，那些老死不相往来的实体间的消息就直接过滤掉了。

在实现上，我采用的最简单的了望塔方案。如果应用层需要让每个实体最多关心半径为 100 米内的其它实体，那么就按合适的间隔（比如也是 100 米）设置一个了望塔对象，由了望塔通知它，附近有哪些东西。

了望塔对应用层是不可见的，它只是一个具体的实现方案。而这个通知协议也只保证大略的信息。只是通知实体，附近（不一定是严格的设定半径，但一定大于应用层设定的范围）实体的增删。

应用层根据这条协议维持自己私有的一个可见集合，再结合其它 AOI 协议得到精确的 AOI 消息。

了望塔的分布应该怎样设置？

一开始我首先想到的是简单的按 2D 网格分布。但是这个方案不到 20 秒就被否定，因为直觉告诉我它不是最优的。然后我试图寻找更好的方法。比如交错开排布。

      __    __    __
     /  \__/  \__/  \
     \__/  \__/  \__/
     /  \__/  \__/  \
     \__/  \__/  \__/

画出来后，同事说，这不就是移动通讯中用的蜂窝网吗？

是啊，很容易证明这就是最优的分布方案。因为每个实体只需要被三个了望塔监控就可以了，而不是 2D 矩形网格方案的四个。六边形的外接圆之间的覆盖面积比例（重复区域）也比正方形的小。

实现时，我们可以生成多级的蜂窝网应付不同的应用层需求。

Comments

这个瞭望塔方案，不是跟网格差不多么？能否介绍下两者的差别？

Posted by: Lynn | (23) July 18, 2015 09:12 PM

多谢云风大哥的指教~强烈支持您~

Posted by: 独孤残云 | (22) June 7, 2010 05:28 PM

三年前跟网易电话面试的时候就聊过这个了。也问了我很多其他方面实现细节的问题。我一一给他解答，竟然还不满足。我跟他说我整套系统全实现了，那人竟然还有脸问我要源代码...借着面试偷取人家的知识产权实在是太不要脸了 Posted by: d | (19) September 27, 2009 10:39 AM

Posted by: Anonymous | (21) February 14, 2010 03:26 AM

Posted by: d | (19) September 27, 2009 10:39 AM 这算是什么产权啊，看起来像是一相情愿的想法. 像云风这样经常在blog上写下自己的想法, 引起讨论和思考才是值得尊重的.

Posted by: lichking | (20) October 14, 2009 11:35 AM

三年前跟网易电话面试的时候就聊过这个了。也问了我很多其他方面实现细节的问题。我一一给他解答，竟然还不满足。我跟他说我整套系统全实现了，那人竟然还有脸问我要源代码...借着面试偷取人家的知识产权实在是太不要脸了

Posted by: d | (19) September 27, 2009 10:39 AM

想问一个问题，这里的AOI服务器的定位是怎样的。我自己的定位是“场景管理”，提供的服务包括运动模拟和空间查询。之所以把这两个放在一起，是因为这两件事可以共享同一套数据结构，特别是当需要做实体间碰撞时，分开可能会很麻烦。

Posted by: sjinny | (18) September 25, 2009 10:41 PM

什么啊

Posted by: vêtements hommes | (17) September 25, 2009 02:42 PM

好吧，关于蜂窝网络看来是我没有做好功课。

Posted by: analyst | (16) September 25, 2009 11:09 AM

@mmosquito, 首先，怎么实现了望塔并不重要。连望塔本身只是一优化辅助手段，了望塔的优化就只是优化的优化，即次要的次要。了望塔的成本是跟实际应用有关的。我在前文写过大量的有关 AOI 的实现，强调的一点是，模块独立，甚至放到独立进程。如果想跨进程通讯去扩展，单个了望塔节点的成本占的比例未必比移动基站小。无论单个成本大也好小也好。了望塔作为一个内聚性很高的模块，采用六边形或四边形，实现的复杂度更多的是对底层的实现的影响；分布的选择的影响是体现在高一个层次的。另外，AOI 的区域是圆的。在 2d 游戏里，如果只是用来做消息广播，因为屏幕是方的，自然是划方格子比较划算。只是，划格子广播消息这种应用，如果是我来实现，未必会跟上面讨论的 AOI 模块放到一起。单独写效果可能更好。 btw, 我不打算说服谁 :) 。

Posted by: Cloud | (15) September 25, 2009 10:46 AM

@cloud 这个蜂窝网络的我也看了，通信采用蜂窝网络是希望节点少，每个节点都要建站都是成本啊，而在游戏中的aoi不过是些内存，并不是越少越好。所以我跟下面发帖的很多同仁一样，这并没有说服我。

Posted by: mmosquito | (14) September 25, 2009 09:55 AM

analyst 说的很清晰我昨天也想到了，因为我做的2d游戏，所以同步区域是小于屏幕（观察区域），导致用9个 4个要求每个观察区大小>屏幕(r)，而9个要求2个观察区大小>屏幕(r)，那么都取最小,4个为4r^2,9个为9(r/2)^2 = 2.25r^2，看上去9个要小，但是实际的应用你不会用极端情况，而是总有一定冗余，冗余下来我看就差不多。 analyst说还可以得到更小的查询面积，但是会增加存储空间以及对象重新hash的开销，未必划算也确实如此，也会增加函数调用的次数。但是也未必不划算，这是我想说的，因为每个区域小，所以查询会快点（包括插入和删除）因为aoi在网游中往往不仅用来同步，也用来索敌和碰撞。

Posted by: mmosquito | (13) September 25, 2009 09:38 AM

蜂窝网络 http://www.hudong.com/wiki/%E8%9C%82%E7%AA%9D%E7%BD%91%E7%BB%9C

Posted by: Cloud | (12) September 25, 2009 01:23 AM

哈，云风真会望文生义，移动通讯蜂窝网就是按蜂窝状分布的6边形型网格，那真是笑话了。无线通讯要面对各种地形、建筑，信号的传播路径非常复杂，有反射和折射，基站怎么可能按6边形型网格排列呢？用6边形型网格是可以做到只查询相邻3个格子，不过那样的话，6边形的边长必须大于等于2倍的观察半径，3个格子的总面积=18 * 3^(1/2) * r^2 如果采用正方形网格，若格子边长大于等于2倍的观察半径，需要查询相邻4个格子，则总面积=16 * r^2 若格子边长等于观察半径，则需要查询相邻9个格子，总面积=9 * r^2。进一部缩小网格大小，还可以得到更小的查询面积，但是会增加存储空间以及对象重新hash的开销，未必划算。总之，6边形网格是最劣算法。

Posted by: analyst | (11) September 25, 2009 12:01 AM

我比较想知道的是，六边形以复杂性为代价带来的好处……另外就是，如果给定一个矩形的空间范围（AABB），如何快速定位到它所覆盖到的格子……

Posted by: sjinny | (10) September 24, 2009 10:58 PM

六边形是 3 个就够不是 7 个，四边形是 4 个，不是 9 个。 3 个是指，每个对象最多只需要被 3 个了望塔监控，每个实体需要了解周围的情况，也最多只需要向附近 3 个了望塔去查询。直观不直观对外并不重要。因为 AOI 对外的接口里并没有“了望塔”这个概念。也就是说，这仅仅只是实现细节。如文中所言，了望塔本身是对 AOI 模块的一个优化。标题中的“优化”指的是了望塔这个方案，而不是指“了望塔”的分布方案。做原型的阶段，我们完全可以不实现“了望塔” 的。用蜂窝状的分布（减少成本）解决这个问题，应该是很成熟的技术了。就好象提供一个函数库供你的程序调用，你无须关心这个库是用 C 实现的，还是汇编，还是别的。只有实现会涉及接口变更的时候，我们才关心怎样实现。比如如果用 C++ 去实现一个库，如果直接导出 C++ 的 API ，就会使库的使用变的很糟糕。实现起来不直观吗？和四边形相比，仅仅只是一个区域判定略微复杂一点。且只是从一行代码变成三行代码的区别。除非使用这个模块的人需要关心这个形状，否则对别人不会有影响。

Posted by: Cloud | (9) September 24, 2009 03:31 PM

蜂窝网很不直观，我看了看，没理解到为什么3个瞭望塔就可以，我看是7个，比方形的格子的9个少2个而已。希望我不是太蠢哦。在看看你上个月写的慢慢的，我学会接受一些东西：比如相信编译器。比如别耍小聪明。比如不要牺牲代码清晰性。比如防御式编程。比如先把代码做的可靠。比如采用时间复杂度更高，但简洁的算法。

Posted by: mmosquito | (8) September 24, 2009 10:58 AM

"另，由于独立性的要求，以外部向 AOI 模块发起查询请求也是不合适的。（不适合独立进程工作）" 这句话我是不是可以理解为AOI会主动的根据服务器中的实体的关心范围向他发送周围实体的情况？如果是这样的话的确可以解决范围魔法的问题，因为施法者已经知道周围的实体位置。但是这样的通讯量会不会由于实体数量的增多呈几何级别的增长？

Posted by: Louis | (7) September 22, 2009 11:48 AM

不知道你具体的协议是怎样的，按照我的理解是这样的： 1.创建实体（名字，位置，速度） 2.移动实体（名字，位置，速度） 3.销毁实体（名字） 4.创建AOI（实体名，AOI名，半径） 5.销毁AOI（AOI名）以上假设要求AOI必须挂在某个实体上。但是现在考虑一个范围法术，火焰之雨。我现在假设，AOI进程之外，其他进程不做场景管理（即本身不提供根据空间范围查找对象列表的服务），那么施法过程可能会这样： 1.逻辑进程向AOI进程发消息，创建AOI（因为火焰之雨的影响范围是玩家点选的） 2.在逻辑进程维护一个对象列表，里面是火焰之雨影响范围内的所有对象 3.以一个定时器定期轮询这个列表，从里面筛选符合条件的对象，对其施加影响 4.法术产生的影响需要告知周围的人，而这又依赖于AOI 5.法术结束时，发消息销毁AOI（以及专为其创建的实体）就这个过程来说，感觉服务器组内部的消息来回很多。如果AOI本身与逻辑写在一个进程里，那么上面的很多异步过程都只是一个同步的函数调用。所以从编写逻辑代码的角度看，把AOI独立出来后会使逻辑代码的编写变得复杂。我自己的玩具代码也是因为这个而暂停了。毕竟我之所以认同把AOI拿出来，是因为我觉得这样可以减少逻辑进程的复杂性，然而这只是减少了逻辑进程底层的复杂性，却增加了上次功能逻辑的复杂性。假设可以把这个异步的过程当作同步过程来写，然后用某种方法来保存和恢复现场（就像线程切换那种），不知道这个是不是就是所谓的协程。但是如果无法做到这种语言层面的改进，还有没有其他的什么办法吗？

Posted by: sjinny | (6) September 21, 2009 12:51 AM

AOI 模块设计的重点在于如何把模块独立以及设计通讯协议。实现的方法是次要的。用了望塔也仅仅是实现的一个优化手段，所以了望塔如何实现更是次要中的次要。蜂窝状的分布主在减少对外交互的信息量。以及在塔间切换的数据量。根据不同的应用需求，往细节里还会有不同的实现方案。比如管理稀疏地图和稠密地图的优化策略必然不同。对象默认 AOI 区域大致相同和大小不一，优化策略也会不同。这些实现的不同应该屏蔽在接口之下。另，由于独立性的要求，以外部向 AOI 模块发起查询请求也是不合适的。（不适合独立进程工作）

Posted by: Cloud | (5) September 20, 2009 12:58 PM

我假设蜂窝内的定位性能不是问题，但是至少用规则的2D网格会更加直观，也能使网格的尺寸和AOI的尺寸更加独立。

Posted by: sjinny | (4) September 20, 2009 01:41 AM

蜂窝在的效率的确比矩形网格分布有效率，但如何判定对象在哪个蜂窝网格是个问题。个人感觉2D网格效率是不高，但实现起来非常方便，只需要对象的X,Y坐标就可以通过2个整除就能确定对象所处的网格单元，而且绝对的精确。以此而增大的计算量未必高的无法接收，甚至可能比用于精确判定在哪个蜂窝网格所多花的计算量要小。

Posted by: yuanhj7908 | (3) September 19, 2009 06:55 AM

不清楚这样的结构要怎么用。如果是2D的网格，作为一个二维数组来看待时很容易使用，因为可以根据一个矩形两个点的坐标方便地算出所覆盖的格子的下标范围。这样当一个AOI移动时，查找覆盖范围内的对象会很容易。而且这样可以任意调整格子的大小和AOI的大小，而在蜂窝结构里，蜂窝尺寸和AOI极限尺寸直接是不是互相约束的？

Posted by: sjinny | (2) September 18, 2009 10:08 PM

恩，蜂窝网，希望了解实际的效果，呵呵~~

Posted by: anders0913 | (1) September 18, 2009 04:36 PM

云风的 BLOG

思绪来得快去得也快，偶尔会在这里停留

AOI 的优化

Comments

Post a comment