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

C++ 评论

什么是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();
	}
}

山中Developer

游戏行业 后端developer