我们再来探讨一种常用的算法A0l(Area ofInterest，感兴趣区域)。射击游戏《绝地求生大逃杀》、角色扮演游戏《天涯明月刀》的场景都很大，且每个场景通常都会拥有大量角色，由于需要同步的消息量通常会很大，因此服务端要承受巨大的广播压力。以第3章的《球球大作战》为例，如果战场中有50名玩家，每人每秒更新5次位置，那么服务端每秒要发送50x50x5=12 500条位置协议，压力很大。另一例子是如图所示的传奇类游戏，一个场景放置了几百上千的怪物，如果这些怪物的信息要一次性同步给玩家，服务端的性能压力非常大。AOI算法可以有效地缓解该问题。
一、感兴趣区域
AOI算法可翻译成“感兴趣区域”算法，它基于角色扮演(MMORPG)、射击(FPS)类游戏“角色仅关心周边事务”的事实。在角色扮演游戏中，玩家只能与附近的NPC和其他玩家进行交互;射击游戏也是如此，只能攻击较近的敌人，至于距离太远的，玩家根本看不到他们。如果只同步角色附近区域内的事务，就能有效减少广播量。如图8-29所示，角色A、B...N在同一个场景。由于客户端屏幕分辨率的限制，在同一屏中，玩家A只能看到A、B和E三个角色，玩家K只能看到K和H两个角色。给定一个比玩家视野稍大的范围，只向他广播该范围内的事件，这个范围称为“感兴趣区域”图中，圆形区域A和K分别是角色A和K的感兴趣区域。角色A只关心周边的E、B和G的事务角色K只关心周边的H、C和D事务。相对的，假如角色A移动一步，服务端只需要把消息广播给E、B和G即可，从而减少广播量。
二、实体模型
要使用AOI算法，需要规划好场景的抽象。玩家、NPC、怪物都能在场景中走动，而且只能与附近的元素进行交互。所有这些“场景中的元素”都有一些共同的功能，为了统一处理，实体模型的类结构会把角色、NPC、怪物都作为“实体”的派生类(如图所示)
如下代码展示了实体类的具体内容，它至少包含id、x和y三个属性。id是实体的唯一标识，x和y是实体的位置坐标。实体至少包含moveto和get sight两个方法，调用moveto可以把实体移动到新的位置，好调用get sight可以获取实体感兴趣区域内的其他实体。
function entity()
{
local e = {
--属性
id = 101,
x = 120,
y = 180,
--方法
moveto = function(x,y)...
get_sight = function()...
--回调
on_enter_sight function(id)...
on_leave_sight function(id)...
}
return e
}
例如，在下图中，调用实体K的get sight，会得到C、D和H。做好实体抽象后，服务端只需要把角色状态广播给get sight获取到的玩家即可，从而极大地减少了广播量。
实体类还可以包含on enter sight和on leave sight两个回调，当有实体进入或走出感兴趣范围时，就会分别调用on_enter sight或on leave_sight方法。例如，在下图中，若F向左移动进入A的感兴趣区域，实体类就会调用A的on enter sight方法。当调用on enter sight方法时，服务端就会通知客户端执行加载模型资源的操作，相反，当调用onleavesight方法时，服务端就会通知客户端执行卸载资源的操作，以节省内存。
做好抽象后，根据具体的实现方式，这些方法和回调可能会有不同的运行效率，但不会影响上层的游戏逻辑。AOI的具体实现方法有很多种，其中最简单粗暴的方法是，调用getsight时，遍历场景中所有的实体，只返回距离较近的实体，但显然这种做法效率较低。“九宫格”是一种业内常用的、效率较高的算法，下面就来讲解九宫格法的具体实现。
三、九宫格法
九宫格法是一种常用的AOI算法，能通过较低的计算复杂度寻找角色周围的实体。
如图所示，先把游戏场景划分成一个个的小格子，格子尺寸依照客户端一屏能看到的范围而定，使一屏最多能够看到4个格子，其中，深色方块代表客户端的感兴趣区域。每个格子拥有横竖两个方向的索引，第一个格子是(0,0)，第二个格子是(0,1)，以此类推。
场景的数据结构具体如代码所示，可以通过“space.ceils[i]l]"找到其中的某个格子，每个格子都保存了其区域内的实体id。例如，在上图中，101和102这两个实体在s(0,0)的范围内，那么space.ceils[0][0]等于{101,102}。
space = {
--格子
ceils = {
[0] = {
[0]={101,102},
[1]={},
...
[7]={}
},
[1]={
[0]={},
...
[7]={},
},
...
}
}
可以把角色周围的9个格子当作它的感兴趣区域，在上图中，客户端角色位于s(1,2)格子内，那么s(0,1)、s(0,2)等(图中的灰色区域)就是它的感兴趣区域，查找9次space.ceils即可获取它感兴趣的实体，运行效率是O(1)。为了保证space.ceils中实体数据的正确性，在角色移动时，需要同时维护space.ceils表，开销也不大。
由于角色的位置具有连续性，因此可以认为它移动前后要么是在同一个格子中，要么就是在周围的8个格子中(如图所示)，总共有9种情况，因此称为“九宫格”。
如果移动前后角色在同一个格子中，则无需进行特殊处理。如果角色向右跨过格子(如图所示)，则需要给左边三个格子(s(2,4)、s(3,4)、s(4,4))的实体发“离开”的通知(回调)，再给右边三个格子(s(2,7)、s(3.7)、s(4,7))的实体发“进入”的通知。
代码展示了九宫格算法中角色移动的具体实现。代码中，on_enter和on_leave方法分别代表调用格子里所有实体的on enter sight和on leave sight方法;add和remove方法分别代表从格子中添加和删除实体。
维护好格子数据之后，程序还会向新位置周围的9个格子广播移动协议(broadcast move)。由于跨过格子的另外7种情形与“情况2:向右走”的实现相似，因此代码中省略了这7种情形的具体实现。
function moveto(x, y)
local ceils = space.ceils
--新坐标所在的格子
local new_cx,new_cy = get_ceil_idx(x,y)
--旧坐标所在的格子
local old_cx,old_cy = get_ceil_idx(self.x, self.y)
--保证持续地移动
if math.abs(new_cx-old_cx) > 1 or math.abs(new_cy - old_cy) then
return
end
--移动
self.x = x
self.y = y
--9种情况
--情况1:还在原来的格子
if new_cx == old_cx and new_cy == old_cy then
--无须处理
end
--情况2向右走
if new_cx == old_cx+1 and new_cy == old_cy then
on_leave(self.id, ceils[old_cx-1][old_cy-1])
on_leave(self.id, ceils[old_cx-1][old_cy])
on_leave(self.id, ceils[old_cx-1][old_cy+])
remove(self.id, ceils[old_cx][old_cy])
on_enter(self.id, ceils[old_cx+2][old_cy-1])
on_enter(self.id, ceils[old_cx+2][old_cy])
on_enter(self.id, ceils[old_cx+2][old_cy+1])
end
end
对于场景很大、角色很多的游戏，使用AOI算法不仅能够减少广播量，还能用它减少物理碰撞的计算量。以《球球大作战》为例，小球只会与周边的球发生碰撞、只能吃到周边的食物，若使用AOI算法，则只需要检测小球是否与感兴趣区域内的实体发生碰撞即可。