开发笔记(26) : AOI 以及移动模块
最近在试图优化游戏服务器，提升承载能力。
加了一些时间检测模块。由于已经重新编写了服务器底层框架，并修改了消息协议，这样底层就有能力监控每条服务的相应时间了。
以前这方面没有做到，是因为：从底层看来，仅仅是一个个的消息包的流动。而一条完整的协议响应却是有多个包进出的。当处理一个服务请求的过程中，向外做了一次远程调用，那么当前服务体就被切出了，直到回应的 session 响应才继续。在新的设计中，session id 被暴露给底层模块可见，这就使监控变得可行。
另外，由于是完全用 C 语言编写而不再使用 Erlang ，我们可以使用成熟的 profile 工具。gprof 使用起来非常方便，容易对性能热点定位。
不过，经过实测，大量的 CPU 时间是消耗在 lua 虚拟机内部。也就是说，在底层框架上做改进已经没有多少可以压榨的了。或许进一步优化通讯协议还有一些工作可以做（合理的协议可以使得上层的数据处理更简洁），不过，工作中心移到 Lua 层面会更有效一些。
相关工作从多个方面入手。
首先想到的是使用 LuaJIT 。不过，我们一开始是工作在 Lua 5.2 上面，而 LuaJIT 似乎不打算完全支持 5.2 版，我需要适度的做一些向前兼容工作。之前我已经记录了一些相关的东西 。在写完上篇 blog 后，我加入了 LuaJIT 的 mailinglist ，LuaJIT 的作者相当的勤奋，基本上提交的 bug 都在半天内可以修正；大多数合理的功能需求也可以满足。或许向前兼容这个事情不一定需要完全自己搞定。我们不需要完全支持 Lua 5.1 ，只需要支持 LuaJIT 2.0 即可。那么，推动 LuaJIT 2.0 去支持一些 Lua 5.2 的新特性也不错。比如就在昨天，LuaJIT 支持了 Lua 5.2 中增强的 debug.getlocal 。
由于我们的进度压力，LuaJIT 的兼容问题暂时搁置了。还有一些工作需要其他同学的协力支持，而他们，正在为努力完成游戏特性而努力。暂时不太可能安排的出时间来做这些调整。
就目前粗略的估测，大量的 CPU 时间消耗在地图上怪物和 NPC 的行动处理上面。尤其是在没有人的地图上，地图进程也占掉了大量的 CPU 时间。
我认为这个问题可以从两方面解决。
其一，也是早在几个月前就提出的，需要细分 NPC 的 AI 驱动模型。
目前，NPC 分成两类，主动攻击附近对象的和只有被攻击才还手的。这样分类可以减少 CPU 的开销，因为被动 NPC 可以在无人干扰它的时候尽量不占用 CPU 资源。
但我认为，光这样分类还是不够的。应该有第 3 类 NPC ：对附近玩家会有主动行为，但是不会理会周围对立势力的 NPC 。
因为，场景中 NPC 的数量是远远超过玩家的。有相当数量的 NPC 会主动根据环境改变而思考和运动，通常，这是采用心跳的方式来定期思考的。而我们完全可以设计成它们中的大多数在无玩家在附近时，都是沿袭着一层不变的运动模式。他们不需要时刻去关注周围是否有敌对势力出现。这样在无人区域，CPU 开销是最小的。
而一旦需要它们主动出击，可以是由他人发送的激活消息完成。比如，一个玩家看到了一个会主动攻击的 NPC ，则由玩家的 agent 发送一个激活消息给它，激活它的 AI 模块。而不是它自己的 AI 模块利用自己的心跳定期检查。
其二，运动模块设计大量的 3D 矢量计算，目前放在 Lua 里去运算是有一些不必要的开销的。这种密集运算，在没有 JIT 的时候，显然是在 C 中计算更高效一些。
基于这两点，我重新设计了 AOI 模块的接口，整合入了运动模块，重新用 C 实现了一下。这次重构是基于这半年的实际编写逻辑的需求提炼，主要是为了让场景逻辑更方便使用，把那些已经稳定下来的需求放在 C 代码中高效运作。
最终总结出来的需求是这样的：
查询某个对象或每个坐标为中心半径 n 之内的所有对象。
作为观察周围的对象（观察者），比较关心周围对象的变动情况。
对象会做匀速直线运动，或者简单跟随另一个对象运动。
我觉得，查询周围对象列表和关心周围对象变动情况这两个需求是可以合并的。即，每次查询都给出和上次查询的差集。如果有必要，对象可以自己维护周围对象列表。
让这个模块产生对象进入和退出另一个对象的 AOI 区域消息，这种消息驱动模式可能并不是一个高效的方案。因为大部分情况下，我们并不需要处理所有的进出消息，而更多的是在必要的时候查询周围列表。这样外界查询就比主动向外发送消息来的高效。且主动查询更具有实时性，如果需要查询一个坐标周围的对象集合，可以临时生成一个对象，而不必等待之后的消息产生。比较符合上层的业务逻辑。（比如施放一个范围攻击的远程炸弹，需要查询到爆炸范围内的所有对象）
把对象的运动放在模块内部，有利于 AOI 模块的高效实现。尤其是跟随这种运动模式，放在外面实现会导致数据频繁交换，暴露 AOI 模块内部过多细节。
曾经考虑把对象抵达目的地，或是接近目标对象也作为特性实现出来，作为一种消息通知。后来觉得没有特别的必要，徒增了接口以及实现的复杂性。对于热切关注自己周围发生的事件的对象，他们用心跳去轮询周围对象列表已经足够满足要求了。
花了一整天时间实现了这个模块。不过使用它可能是下个月的事情了。这个月其他同学都太忙着实现游戏特性。这样也好，可以再做一些思考，尽可能在使用前完善一下接口。下面列出这个模块的 C 接口：
struct map * map_new(float w, float h);
void map_delete(struct map *m);
int map_insert(struct map *m, const char * mode);
void map_erase(struct map *m, int handle);
void map_location(struct map *m, int handle, float pos[3]);
void map_moveto(struct map *m, int handle, float target[3]);
void map_follow(struct map *m, int handle, int who);
void map_speed(struct map *m, int handle, float speed);
void map_move(struct map *m, float tick);
const float * map_velocity(struct map *m, int handle);
const float * map_position(struct map *m, int handle);
int map_around(struct map *m, int handle, float rad_short, float rad_long,
void (*around_cb)(void *ud, int handle, int enter), void *ud);
这里最关键的是 around 这个 API 。它负责查询某个对象周围的对象。这个查询是带状态的，即，只会返回和上次查询的差异结果。查询半径是一个条带，由长短半径共同决定，这是为了防止结果颠簸。
这个 API 只承诺返回进入 rad_short 半径内的对象，以及会查询到超过 rad_long 半径的对象离开。
move 接口用来驱动模块内部的对象移动。这些移动是由 moveto 或 follow 引发的。
所有的对象都有唯一整数 id ，由 insert 方法生成；且 id 不会因为 erase 而复用。
position 和 velocity 可以查询到对象的坐标和移动矢量。
又这些 C 接口，可以轻松封装到 lua 中使用。Lua 层的 API 更简洁一些，这里不再列出。
btw, 前一个版本的 AOI 模块在旧文中描述过 。至今工作倒也很正常。这次的改变原因主要是想进一步解决性能问题(通过提供部分对象移动的特性)，以及提供给上层更加方便的接口（主要是查询某个区域的对象）
Comments
不知道这个会不会开源呢？感觉结构比之前那个要好
Posted by: nil | (23) January 19, 2015 02:37 PM
云大，这个移动模块会开源吗？
Posted by: teardemon | (22) June 17, 2014 10:07 PM
请教云风,如果需要为你的aoi编写单元测试,应该要怎么写呢?谢谢.
Posted by: GodZza | (21) November 1, 2012 01:19 PM
我们上一个游戏在对AOI做优化的时候，实现的想法和你的想法有些大同小异：经典的gameserver，地图上的NPC按分块进行激活，默认情况下所有NPC都是冻结的，他们既不跑AI，也不跑AOI。只有在有玩家“接近”或“进入”此地图分块的时候才会激活这个区域的NPC，包括AOI和AI。
Posted by: Jeff.Wang | (20) October 25, 2012 03:43 PM
12分期待云风的游戏，好想玩玩
Posted by: 爬爬虾 | (19) October 8, 2012 10:56 AM
这些代码太专业了，看不是很懂。
Posted by: yujie | (18) October 6, 2012 05:01 PM
我看还是提高设备比较好！
Posted by: 博彩通 | (17) October 3, 2012 01:55 PM
很好的文章，很喜欢，希望楼主能多写点！
Posted by: 不锈钢合页 | (16) October 2, 2012 04:19 PM
云风没考虑过这些用go语言实现吗
Posted by: 池中物 | (15) September 28, 2012 04:23 PM
int send_msg(const byte* buf, const size_t len)
Posted by: standard | (14) September 26, 2012 11:26 AM
请达人实现下面这个功能类。急求！！
int send_msg(const byte& buf, const size_t len)
{
//....
}
int send_msg(const meta& m)
{
return send_msg(m.raw(), m.raw_len());
}
meta m;
m['age'] = 18;
meta name;
name['surname']=string('green');
name['givenname']=string('jam');
m['name']=name;
m['address']=meta();
m['address']['province']=string('guangdong');
m['address']['city']=string('shenzheng');
meta& hobby=m['hobby'].list_type();
hobby[0]=string('basketball');
hobby[1]=string('football');
..
hobby[10]=string('music');
Posted by: standard | (13) September 26, 2012 11:24 AM
文章写得不错，好评一下、
Posted by: sdzkjy | (12) September 26, 2012 09:34 AM
因为有不同阵营的怪, 巡逻碰头后会相互攻击的设定.
=======
赞这个设定！
Posted by: Soli | (11) September 25, 2012 04:24 PM
我觉得这个设计里可能存在着一个问题,就是过多地用心跳主动去轮询周围实体状态来达到同步.
我建议自己维护周围对象列表,通过进入,退出是可以做到的.各实体的同步,由状态发生变化的实体来通知自己周围列表的其它实体,达到即时的同步.
Posted by: Ben | (10) September 25, 2012 01:26 PM
用垃圾回收机制,NPC身上加一个计数器,当有玩家类实体,enter的时候计数器++,当leave的时候计数器--,计算器等于0时,NPC处于假死状态(AI关闭).
Posted by: Ben | (9) September 25, 2012 12:59 PM
写的太好了，改天我也写写！
Posted by: 不锈钢合页 | (8) September 24, 2012 09:52 AM
看多了这些接口，，，就会觉得，面向对象的接口是多么舒服啊
Posted by: lichking | (7) September 21, 2012 09:52 PM
@invalid
因为有不同阵营的怪, 巡逻碰头后会相互攻击的设定.
Posted by: Cloud | (6) September 21, 2012 08:20 PM
其实……何不让所有怪都只受玩家激活？
这样，当玩家不观察它们的时候，就无需任何CPU资源；而一旦玩家接近到即将看到它们，它们才开始行动……
——上帝一定就是这样造我们的世界的。一定是这样。薛定谔的猫证实了这一点^_^
Posted by: invalid | (5) September 21, 2012 07:06 PM
一个人物的移动，都会对移动的信息对周围的对象进行广播，NPC收到移动信息后再决定是否攻击或者激活npc的策略，这样NPC就不使用心跳了。NPC在地图上的巡逻，也可以使用上发条的方式，有非NPC的信息时就上发条，进行走动，没人时发条走完就不走了。
Posted by: 明月照大江 | (4) September 21, 2012 06:36 PM
发现个小问题: skynet_mq.c:215 类型是不是弄错了
Posted by: pz | (3) September 21, 2012 04:15 PM
这类游戏AI和移动是紧密联系的~
Posted by: pass86 | (2) September 21, 2012 02:02 PM
呵呵，你这个关于ai的设计让我想到一个哲学上的问题：没有被人类观察到（无论用何种手段）的事物是否存在。这是个不可证伪的问题（至少就我的能力而言），就好比你们游戏的玩家在游戏中始终没办法知道当一个怪附近没有玩家时，这个怪是否具有AI。玩家们有个上帝——开发者，所以这个问题是有解的。但对于人类来说，这个问题就不好办了~
Posted by: 萧文彬 | (1) September 20, 2012 08:27 PM