5.1 KiB
AOI
对于AOI(area if interest)介绍的文章实在是太多了，比如常用的灯塔，9grid，十字链表等等，这些本质上是在面对海量的数据量做裁枝。最近同事聊起来说在做AOI优化部分的工作，于是就感兴趣跟他聊起来现在的实现，以及优化的方向。 其实现在的实现就是最最标准和简单的9 grid的实现。 每次对象在add, move, delete时，会返回一个集合，表示需要通知的其他对象。 当如果N个对象全部都是在同一个grid里面而且同时产生事件，那这个简单的算法会是O(NxN)的性能开销。
我觉得，对于aoi来说，所做的事情就只有一件事情，根据此时的snapshot，和上一次的snapshot对比生成diff（变化的对象），返回给对应的watcher(观察者)。在这段时间内假如A对象从 b点移动到了c点，但又回到了c点，diff里面将不会包含这个A对象移动的信息。 驱动AOI工作应该是每次调用update，并不是在操作函数add, move, delete。 这样，可以自己决定在合适的时机(比如在每帧末尾或者固定时间执行)调用update获得这段时间需要通知的事件集合，这样在面对之前N个对象在同一个grid同时移动的时间开销将会降到O(N)。
但是对每个watcher创建snapshot开销太大，在同一个grid里面的watcher中的snapshot是一样的，所以可以只需要对grid做snapshot，不过这样被修改的grid对象会存储翻倍，而且每次update时要生成snapshot，性能上肯定会无法接受。
其实对于snapshot本身只是为了diff，那其实可以在grid上记录下两次update之间的改动，在update时直接根据改动来生成diff列表，之后再把改动合并到grid存储objects的集合中就好，这样就避免对整个grid的snapshot。
所以我就实现了 AOI来证明了想法。 ;D
AOI 内部实现
首先你可以通过aoi.aoi_new(map_row, map_col, grid_row, grid_col)来构建一个aoi_obj，aoi_obj:aoi_add(obj_id, marked, pos_x, pos_y)接口来向aoi 场景中添加一个对象id为obj_id的object，所有的object可以是watcher，maker，或者同时为两者。 只有watcher才会收到maker产生的事件，watcher之间不会产生任何事件。 aoi_obj:aoi_remove(obj_id) 函数为移除一个对象, aoi_obj:aoi_set(obj_id, pos_x, pos_y)更新一个对象，以及aoi_obj:aoi_update()更新整个aoi对象，返回需要通知的watchers的makers事件。 事件分为三类D删除，A添加，U更新。 每个对象的更新会根据grid_row和grid_col被存储在对应的grid对象上。 grid_obj的定义如下：
local obj = {
aoi_obj = aoi_obj,
grid_idx = grid_idx,
watchers = false,
objs = {},
touchs = false,
merge = false,
result = {},
}
其中watchers记录了当前grid上面的所有watcher对象id，objs记录的是上一次update之后当前grid的object，touchs记录的从上一次update到现在grid上面有改动的对象信息，其中merge和result是在update时会用到的字段。 aoi_add, aoi_set, aoi_remove这些接口最后都会设置到对应的grid的touchs中。当执行update时，会计算出需要通知的有watcher的grids， 对每个grid的周围的9个grid下生成对应的diff，每个grid的diff会最多包含以下三种:GD grid中object被删除事件集，GAgrid中object被添加事件集，GUgrid中object更新事件集。这些结果会存储到result table中。 之后根据每个watcher来选择对应的结果集，避免反复的计算。
在update实现时这里有个优化：是从被touch的grid来找到那些watcher，还是从有watcher的grid来找到那些grid被touch。 当被touch的grid大于有watch 的grid个数，会选择直接从有watcher的grid去处理。反之，从touch的grid来处理。这样的好处是避免了，update在watcher和 touch的maker差距很大时，无效的遍历。
最终我在自己机器Intel(R) Core(TM) i7-4578U CPU @ 3.00GHz上面测试了在同一个grid添加10K个对象，仅仅只需要0.028496s.
订阅通知
其实对于服务器来说，aoi的工作并不只是只能完全放到服务器来做。根据灯塔算法，将整个world划分成等大的grid，客户端自己计算统计那些grid需要订阅（关心），那些grid应该取消订阅。服务器对于每个grid定时同步订阅的watcher数据。 服务器的工作就会变得很简单，维护一系列grid上面订阅的对象，同时把grid上产生的事件通知给对应的订阅者即可。 客户端当进入新的grid，会产生订阅协议，服务器将整个grid的状态同步过去。取消订阅时，客户端将在对应的grid的对象自己移除，同时服务器也不会通知相应grid的事件。驱动全部都是通过客户端来发起， 这样服务器所做的工作就只是同步订阅的grid数据这一个简单的事情，也很容易通过多个服务做横向扩展。 对于slg来说，我觉得这是个比较好的aoi方案。