游戏服务器AOI算法-九宫格

什么是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) {
// 没有预先将场景划分N个格子, 只有在用到某个格子时才会创建, 节省内存
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();
}
}