游戏算法-AOI九宫格python实现

将空间按照一定的方法进行分割，例如根据AOI范围的大小将整个游戏世界切分为固定大小的格子。当游戏物体位于场景的时候，根据坐标将它放入特定的格子中。

例如玩家1在位置7中，如果游戏内的AOI的范围为1个格子。当我们需要获取这个玩家周围的AOI对象时，只需要遍历7周围9个里面的对象即可。

实体的事件：

• 进入场景enter：进入一个格子，取出周围9格的对象，向它们发送Enter(我)事件，同时向我发送Enter(对象)事件。
• 离开场景leave：取出周围9格的对象，向它们发送Leave(我)事件。
• 移动move：
  • 如果没跨格子，直接取9格的对象，向它们发送移动事件。
  • 如果跨过格子，计算{OldGrid-NewGrid}，向它们发送Leave(我)事件，向我发送Leave(对象)事件；计算{NewGrid-OldGrid}集合，向它们发送Enter(我)事件，向我发送Enter(对象事件；计算{NewGrid*OldGrid}集合，向他们发送Move(我)事件。
     

空间分割在计算AOI对象时，只需要遍历周围几个空间格子即可，大大提高了计算效率。

但是该方法也有缺点，格子数和空间大小成为正比，空间越大，所需要的内存空间也越大。

如果玩家数里远远小于空间的格子数，使用这种方法来计算AOI可能比全部遍历效率还差。

实现

实体Entity：有三个事件，enter.leave,move事件

class Entity(object):# 场景实体def __init__(self, eid, x, y):self.id = eid  # 角色IDself.x = xself.y = yself.last_x = -1  # 是用来参与判断实体是否有进入或者离开 AOIself.last_y = -1def __str__(self):return "<{0}, {1}-{2}>".format(self.id, self.x, self.y)def enter(self, eobj):print("{0} enter {1} view".format(eobj, self))def leave(self, eobj):print("{0} leave {1} view".format(eobj, self))passdef move(self, eobj):print("{0} move in {1} view".format(eobj, self))

格子：场景根据大小分成若干格子，每个格子管理一个区域

角色所在的位置，由格子管理

class Grid(object):# 格子def __init__(self, gid, min_x, max_x, min_y, max_y):self.gid = gid  # 格子IDself.min_x = min_x  # 格子坐标x范围self.max_x = max_xself.min_y = min_y  # 格子坐标y范围self.max_y = max_yself.players = set([])  # 角色ID

比如此图，分成36个格子

场景：控制生成格子数量，管理格子和实体对象

class Scene(object):# 场景，由多个格子组成def __init__(self, min_x, max_x, cnts_x, min_y, max_y, cnts_y):self.min_x = min_xself.max_x = max_xself.cnts_x = cnts_x  # X轴方向格子的数量self.min_y = min_yself.max_y = max_yself.cnts_y = cnts_y  # y轴方向格子的数量self.grids = {}  # 管理格子对象self.map_entity = {}  # 管理实体对象

完整代码：

python版本：2.7

# -*- coding: utf-8 -*-class Entity(object):# 场景实体def __init__(self, eid, x, y):self.id = eid  # 角色IDself.x = xself.y = yself.last_x = -1  # 是用来参与判断实体是否有进入或者离开 AOIself.last_y = -1def __str__(self):return "<{0}, {1}-{2}>".format(self.id, self.x, self.y)def enter(self, eobj):print("{0} enter {1} view".format(eobj, self))def leave(self, eobj):print("{0} leave {1} view".format(eobj, self))passdef move(self, eobj):print("{0} move in {1} view".format(eobj, self))class Grid(object):# 格子def __init__(self, gid, min_x, max_x, min_y, max_y):self.gid = gidself.min_x = min_xself.max_x = max_xself.min_y = min_yself.max_y = max_yself.players = set([])  # 角色IDdef __str__(self):return "<{0}, {1}-{2}: {3}>,".format(self.gid, self.min_x, self.min_y, str(self.players))def add(self, eid):self.players.add(eid)def remove(self, eid):self.players.remove(eid)def get_player_ids(self):return list(self.players)class Scene(object):# 场景，由多个格子组成def __init__(self, min_x, max_x, cnts_x, min_y, max_y, cnts_y):self.min_x = min_xself.max_x = max_xself.cnts_x = cnts_x  # X轴方向格子的数量self.min_y = min_yself.max_y = max_yself.cnts_y = cnts_y  # y轴方向格子的数量self.grids = {}self.map_entity = {}  # 实体对象self.init_grid()def __str__(self):res = ""for y in xrange(self.cnts_y):for x in xrange(self.cnts_x):gid = y * self.cnts_x + xres += str(self.grids[gid])res += "\n"return resdef init_grid(self):# 生成格子for y in xrange(self.cnts_y):for x in xrange(self.cnts_x):gid = y * self.cnts_x + xmin_x = self.min_x + x * self.grid_width()max_x = self.min_x + (x + 1) * self.grid_width()min_y = self.min_y + y * self.grid_height()max_y = self.min_y + (y + 1) * self.grid_height()self.grids[gid] = Grid(gid, min_x, max_x, min_y, max_y)def grid_width(self):# 每个格子在x轴方向的宽度return (self.max_x - self.min_x) / self.cnts_xdef grid_height(self):# 得到每个格子在Y轴方向高度return (self.max_y - self.min_y) / self.cnts_ydef get_surround_grids_by_gid(self, gid, include_self=False):# 周边的格子对象surrounds = []grid = self.grids[gid]y, x = divmod(grid.gid, self.cnts_x)for y_i, x_j in ((-1, 1), (-1, 0), (-1, -1), (0, -1), (0, 1), (1, 1), (1, 0), (1, -1)):cal_y = y + y_ical_x = x + x_jif cal_x < 0 or cal_x >= self.cnts_x:continueif cal_y < 0 or cal_y >= self.cnts_y:continuecal_gid = cal_y * self.cnts_x + cal_xsurrounds.append(self.grids[cal_gid])return surroundsdef add_eid_grid(self, eid, gid):self.grids[gid].add(eid)def remove_eid_grid(self, eid, gid):self.grids[gid].remove(eid)def get_eids_by_gid(self, gid):return self.grids[gid].get_player_ids()def get_gid_by_pos(self, x, y):# 通过，x, y得到对应格子IDidx = (x - self.min_x) / self.grid_width()idy = (y - self.min_y) / self.grid_height()gid = idy * self.cnts_x + idxreturn giddef get_surround_eids_by_pos(self, x, y, include_self=False):# 根据一个坐标 得到 周边九宫格之内的全部的 玩家ID集合gid = self.get_gid_by_pos(x, y)grids = self.get_surround_grids_by_gid(gid)eids = []for grid in grids:eids.extend(grid.get_player_ids())if include_self:eids.extend(self.grids[gid].get_player_ids())return eidsdef add_to_grid_by_pos(self, eid, x, y):# 通过坐标 将eid 加入到一个格子中gid = self.get_gid_by_pos(x, y)grid = self.grids[gid]grid.add(eid)return giddef remove_to_grid_by_pos(self, eid, x, y):# 通过坐标 将eid remove到一个格子中gid = self.get_gid_by_pos(x, y)grid = self.grids[gid]grid.remove(eid)def update_pos(self, update_eid, x, y):if update_eid not in self.map_entity:# 首次进入eobj = Entity(update_eid, x, y)self.map_entity[update_eid] = eobjgrip_id = self.add_to_grid_by_pos(update_eid, x, y)eids = self.get_surround_eids_by_pos(x, y)for eid in eids:ob = self.map_entity[eid]ob.enter(eobj)else:eobj = self.map_entity[update_eid]eobj.last_x = eobj.xeobj.last_y = eobj.yeobj.x = xeobj.y = y# 格子内移动old_gid = self.get_gid_by_pos(eobj.last_x, eobj.last_y)new_gid = self.get_gid_by_pos(eobj.x, eobj.y)if old_gid == new_gid:eids = self.get_surround_eids_by_pos(x, y, True)for eid in eids:self.map_entity[eid].move(eobj)else:# 移动格子self.remove_eid_grid(update_eid, old_gid)self.add_eid_grid(update_eid, new_gid)old_surround_gids = self.get_surround_grids_by_gid(old_gid)new_surround_gids = self.get_surround_grids_by_gid(new_gid)# 新格子事件处理for grid in [grid for grid in new_surround_gids if grid not in old_surround_gids]:for eid in grid.get_player_ids():self.map_entity[eid].enter(eobj)# 老格子事件处理for grid in [grid for grid in old_surround_gids if grid not in new_surround_gids]:for eid in grid.get_player_ids():self.map_entity[eid].leave(eobj)for grid in [grid for grid in old_surround_gids if grid in new_surround_gids]:for eid in grid.get_player_ids():self.map_entity[eid].move(eobj)def test():scene = Scene(0, 100, 4, 0, 100, 4)scene.update_pos(1, 0, 0)scene.update_pos(2, 50, 20)scene.update_pos(3, 99, 99)print(scene)print("<25-1> sorround: {0}".format(scene.get_surround_eids_by_pos(25, 1, True)))print("<50-50> sorround: {0}".format(scene.get_surround_eids_by_pos(50, 50, True)))scene.update_pos(3, 25, 1)scene.update_pos(3, 99, 99)test()

运行结果：一个场景分成16个格子，大小为100 * 100

<0, 0-0: set([1])>,<1, 25-0: set([])>,<2, 50-0: set([2])>,<3, 75-0: set([])>,
<4, 0-25: set([])>,<5, 25-25: set([])>,<6, 50-25: set([])>,<7, 75-25: set([])>,
<8, 0-50: set([])>,<9, 25-50: set([])>,<10, 50-50: set([])>,<11, 75-50: set([])>,
<12, 0-75: set([])>,<13, 25-75: set([])>,<14, 50-75: set([])>,<15, 75-75: set([3])>,<25-1> sorround: [1, 2]
<50-50> sorround: [3]
<3, 25-1> enter <1, 0-0> view
<3, 25-1> enter <2, 50-20> view
<3, 99-99> leave <1, 0-0> view
<3, 99-99> leave <2, 50-20> view

 深入探索AOI算法：深入探索AOI算法 - 知乎