什么是AOI AOI 即 Area Of Interest, 常见于各类MMORPG, ARPG等类型的游戏中, 通过AOI来管理场景中的玩家, NPC, 怪物等等对象 玩家在场景中移动时, 位置等信息通过AOI广播给场景中所有能看到该玩家的对象, 同时, 玩家可视区域内, 所有对象的信息发生变化时, 玩家也会收到通知.
为什么需要AOI 当一个地图场景内, 有100个玩家分散的各处, 当某一个玩家移动时, 就需要广播通知给场景内所有能看到该玩家的对象, 如果遍历场景内的所有对象, 检查视野, 会降低服务器的性能, 使用AOI的部分目的就是为了解决这个问题.
常见AOI算法
九宫格算法 九宫格算法会将地图划分为N个相同大小的格子, 以格子为单位管理对象, 当某个对象的数据发生更新时, 同步数据到该对象为中心的九个格子即可. 主要实现代码如下:项目地址 由on_entity_action
驱动, 触发ENTER
, LEAVE
, MOVE
等事件
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 void AOI::grid_aoi::on_entity_action (uint64 uid, entity_action action, ...) { switch (action) { case entity_action::ENTER: { va_list args; va_start (args, action); const int pos_x = va_arg (args, int ); const int pos_y = va_arg (args, int ); va_end (args); position pos (pos_x, pos_y) ; this ->on_entity_enter (uid, pos); } break ; case entity_action::LEAVE: this ->on_entity_leave (uid); break ; case entity_action::MOVE: { va_list args; va_start (args, action); const int pos_x = va_arg (args, int ); const int pos_y = va_arg (args, int ); va_end (args); position pos (pos_x, pos_y) ; this ->on_entity_move (uid, pos); } break ; } }
进入视野
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 void AOI::grid_aoi::on_entity_enter (uint64 uid, const position& pos) { auto iter = this ->_entitys.find (uid); if (iter != this ->_entitys.end ()) return ; map_grid* grid = this ->get_grid (pos); if (!grid) { int index_x = pos2grid_index (pos, this ->_wide, x); int index_y = pos2grid_index (pos, this ->_hige, y); grid = this ->new_grid (index_x, index_y); } entity* e = new entity (uid, pos); grid->_uids.insert (uid); this ->_entitys.insert (std::make_pair (uid, e)); this ->broadcast_near (pos, entity_action::ENTER, e); }
离开视野
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 void AOI::grid_aoi::on_entity_leave (uint64 uid) { auto iter = this ->_entitys.find (uid); if (iter == this ->_entitys.end ()) { aoi_debug ("[on_entity_leave] not found entity <%llu>" , uid); return ; } entity* e = iter->second; if (!e) { aoi_debug ("[on_entity_leave] entity <%llu> is nullptr" , uid); return ; } map_grid* grid = this ->get_grid (e->_pos); if (!grid) { aoi_debug ("[on_entity_leave] before is nullptr, entity uid <%llu>, pos <%d, %d>" , e->_uid, e->_pos._x, e->_pos._y); return ; } this ->broadcast_near (e->_pos, entity_action::LEAVE, e); grid->_uids.erase (uid); this ->_entitys.erase (uid); delete e; e = nullptr ; }
更新
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 void AOI::grid_aoi::on_entity_move (uint64 uid, const position& pos) { auto iter = this ->_entitys.find (uid); if (iter == this ->_entitys.end ()) { aoi_debug ("[on_entity_move] not found entity <%llu>" , uid); return ; } entity* e = iter->second; if (!e) { aoi_debug ("[on_entity_move] entity <%llu> is nullptr" , uid); return ; } map_grid* before = this ->get_grid (e->_pos); if (!before) { aoi_debug ("[on_entity_move] before is nullptr, entity uid <%llu>, pos <%d, %d>" , e->_uid, e->_pos._x, e->_pos._y); return ; } map_grid* after = this ->get_grid (pos); if (!after) { after = this ->new_grid (pos2grid_index (pos, this ->_wide, x), pos2grid_index (pos, this ->_hige, y)); } e->_pos = pos; if (*before == *after) this ->broadcast_near (pos, entity_action::MOVE, e); else { addr_set before_grids, after_grids, cross_grids; this ->on_change_grid (before, after, before_grids, after_grids, cross_grids); std::vector<entity*> entitys; for (auto & addr : cross_grids) { map_grid* grid = (map_grid*)addr; for (auto & uid : grid->_uids) { entity* watch = this ->get_entity (uid); if (watch) entitys.push_back (watch); } } for (auto & watch : entitys) this ->_action_event(e, entity_action::MOVE, watch); entitys.clear (); before->_uids.erase (e->_uid); after->_uids.insert (e->_uid); for (auto & addr : after_grids) { map_grid* grid = (map_grid*)addr; for (auto & uid : grid->_uids) { entity* watch = this ->get_entity (uid); if (watch && watch->_uid != e->_uid) entitys.push_back (watch); } } for (auto & watch : entitys) { this ->_action_event(e, entity_action::ENTER, watch); this ->_action_event(watch, entity_action::ENTER, e); } entitys.clear (); for (auto & addr : before_grids) { map_grid* grid = (map_grid*)addr; for (auto & uid : grid->_uids) { entity* watch = this ->get_entity (uid); if (watch && watch->_uid != e->_uid) entitys.push_back (watch); } } for (auto & watch : entitys) { this ->_action_event(e, entity_action::LEAVE, watch); this ->_action_event(watch, entity_action::LEAVE, e); } entitys.clear (); } }