一直想花点时间好好研究下游戏AOI的实现，把这一块完结掉，整合到 server 上面去。这里我对代码进行注释AOI。 记录下云风的基本文章，顺序阅读
开发笔记 (13) : AOI 服务的设计与实现： http://blog.codingnow.com/2012/03/dev_note_13.html
开发笔记(26) : AOI 以及移动模块： http://blog.codingnow.com/2012/09/dev_note_26.html
开发笔记(28) : 重构优化： http://blog.codingnow.com/2012/11/dev_note_28.html
实体
每个实体都维护着一个版本号，当实体进入场景，移动，更新状态时，版本号+1。
实体的状态类型分别有：观察者（Watcher），被观察者（Marker），已离开（Drop）。
观察者：可以观察半径内实体的状态。进入，移动，离开。
被观察者：可以让观察者 观察 到自己。
结构体如下：
struct object {
int ref; // 引用数
uint32_t id; // 唯一标识
int version; // 实体新进入场景 或 改变了状态 或 改变了位置, 则 version +1
int mode; // 实体状态
float last[3]; // 上一次位置坐标
float position[3]; // 当前位置坐标
};更新状态
先看下接口
// space 场景管理对象
// id 实体唯一标识
// mod 状态 w(atcher) m(arker) d(rop)
// pos 位置 x,y,z
void aoi_update(struct aoi_space * space , uint32_t id, const char * mode , float pos[3]);当我们需要添加一个实体到场景，或需要移动实体位置，或要更改实体状态时，都统一调用 aoi_update 接口
aoi_message 接口
// ud 自定义参数
// watcher 观察者
// marker 被观察者
typedef void (aoi_Callback)(void *ud, uint32_t watcher, uint32_t marker);
// space 场景管理对象
// cb aoi消息回调
// ud 自定义参数，会在cb回调时带上
void aoi_message(struct aoi_space *space, aoi_Callback cb, void *ud);调用 aoi_message 接口可获取实体信息通知。接口完成功能包括有：
-
将 移动 的实体放进
move集合中；将 微动 和 静止 的实体放入static集合中。
move 集合分为watcher_move和marker_move。代表 观察者移动集合 和 被观察者移动集合。
static 集合也分为watcher_static和watcher_static。代表 观察者静止集合 和 被观察者静止集合。
这一步是一个 O(n) 复杂度的操作 -
校验 （watcher_static 和 marker_move）；（watcher_move 和 marker_static）；（watcher_move 和 marker_move），循环检索实体两两之间的距离，如果小于感知半径，则发送 进入视野AOI消息(包括进入和移动)，如果大于感知半径的2倍，则直接返回。如果以上条件都不符合，则将这两个实体放入到
热点对列表中。
这3对循环检索，每一对的复杂度为 O(n)。 -
再下一次 tick 时间执行 aoi_message 接口时，我们先判断
热点对列表。每个热点对，是我们需要尝试判断是否会触发 AOI 消息的两个 id 对。 如果一对热点对里，其中一方实体的状态改变了，则删除此热点对，因为等下上面的 1,2 步骤会处理。如果两个实体的状态的都没有改变，我们就比较 他们的距离，当距离小于感知半径时，发送AOI消息，并删除此热点对；否则保留此热点对等待下个 tick 处理。可能大家会问，为何要维护热点对列表了？其实主要是用于处理实体的微动情况。实体的状态发生改变，包括实体进入场景，移动（移动距离超过感知半径的一半，如感知半径时20，那么移动>=10时才算移动）， 离开。实体的微动是指移动距离小于半径的一半，微动是不会改变实体的状态，所以我们要在热点对里去判定。某个实体的微动是否进入到了其他实体的感知 范围内，或离开了其他实体的感知范围。
热点对列表操作复杂度为 O(n)
总结
此 AOI模块 与场景大小无关，只与实体数量和位置有关。由上面的 aoi_message 接口可知，整个 AOI模块 的复杂度为 O(n)。
加入热点对是由上面第 2 步形成。既热点对肯定是一个观察者+一个被观察者，如果观察者和被观察者长时间处于微动或静止，而且他们的距离大于2倍
半径，他们将不会进入热点对，既不会被遍历，也没有比较距离的运算。
在逻辑层，收到AOI消息后，应该把实体加入到自己的关心列表中，以后在处理遍历这个列表时，有足够多的机会把不再关心的实体删掉。例如需要做身边广播 时我们就可以遍历下此列表。