灯塔AOI简易实现
首先咱们来讨论下游戏开发中的几个坐标系，为了方便解释，我截取了灯塔AOI DEMO当NPC数目为0时候的样子（代码地址以为有帮助的童鞋记得给我代码点个星^_^）git
先对这张图简单说明下：github
- 蓝色的坐标轴表示是灯塔AOI坐标系，绿色的坐标轴表示的是游戏坐标系，向左为X轴正方向，向上为Y轴正方向（这个坐标是我本身后面画上去的）
- 深蓝色的点表示灯塔AOI坐标，左下的表示(0,0)，右上表示(1,1)
- 深绿色的点表示游戏坐标，左下表示(0,0)，右上表示(1,1)
- 每一个灰色的小格子表明一个游戏坐标（边长为15像素）
- 每一个黄灰的大格子表明一个灯塔AOI坐标（边长为11个灰色小格子）
- 瓦片地图大小为宽：100个灰色小格子 高：70个灰色小格子
- 深蓝色的方块为玩家，大红色方框为玩家在游戏坐标系中的视野（视野半径为10个灰色小格子），兰色方框表示玩家在灯塔坐标系中的视野
像素
这个是客户端图形实际显示要用到的坐标（和游戏逻辑无关），每一个图片长宽各多少像素，描点在什么位置，可是在游戏中直接使用像素做为计量单位(坐标点)十分不方便，好比物体的移动，何况移动也不会一个像素一个像素移动，因此咱们作了一层抽象(格子)，游戏相关的贴图(地图/人物/道具)必须是格子的整数倍，这样游戏中全部的物体才能被正常显示，而不会产生误差。code
格子/瓦片（游戏坐标系）
什么是格子？格子是游戏逻辑使用的最小单位，表明游戏坐标系的点，它的单位为像素(DEMO中15*15像素为一格)，游戏中全部设定都必须是格子的整数倍，因此不会出现有物体在两个格子之间，致使坐标不肯定的状况，物体的移动的步长单位也变成多少格，而不是像素了，即若是使用像素做为坐标点，从(0,0)移动到(0,1)，则移动了1个像素，如今用格子做为坐标点，从(0,0)移动到(0,1)，则移动了15个像素。对象
什么是瓦片？一张大的世界地图或者背景图能够由几种地形来表示，每种地形对应一张小的的图片，咱们称这些小的地形图片为瓦片。把这些瓦片拼接在一块儿，一个完整的地图就组合出来了，这就是瓦片地图。blog
在DEMO中，为了简化逻辑，我将瓦片设置为一倍格子大小，玩家和NPC的大小也设置为一倍格子大小。游戏
灯塔AOI坐标系
为何须要灯塔AOI？假设咱们想知道某点周围10格内有哪些对象，在没有灯塔AOI的状况下，咱们须要遍历全部的对象计算其是否在范围内，随着地图内的对象愈来愈多，查找的效率也会愈来愈差，因此咱们须要一种方法来过滤那些明显不须要参与计算的对象，因此咱们将地图分割成一个个区域，在其中心放置一个假想的"灯塔"，每一个"灯塔"都会保存区域内的对象，这样当咱们须要知道某点周围10格内有哪些对象时，咱们只须要计算出范围内有哪些"灯塔"，而后获取这些"灯塔"保存的对象列表，针对这些对象进行计算就能节省大量计算。为了方便表示和管理这些"灯塔"，咱们为其分配了新坐标(左下为(0,0))，这个新的坐标系即灯塔AOI坐标系(这个坐标系是用来作碰撞检测的)图片
灯塔视野和玩家视野
"灯塔"的视野越小，在碰撞检测时能过滤的无效对象就越多，可是整张地图"灯塔"的数目也就越多，消耗的内存就越大，并且对象进出灯塔的计算量就越多内存
"灯塔"的视野越大，在碰撞检测时能过滤的无效对象就越少，碰撞检测的计算量就越大，想象下只有一个"灯塔"的状况，即退回了没有灯塔AOI系统的状况游戏开发
因为玩家的视野通常是固定的（屏幕显示区域大小通常固定），因此灯塔视野大小通常是玩家视野的1/2或1/3比较合适开发
灯塔坐标的计算
假设要计算游戏中某点所处的灯塔坐标(详细逻辑见代码注释)：
### 将游戏坐标系和灯塔AOI坐标系对齐，而后除以灯塔边长(两倍视野内包含的格子数 + 自身坐标格子) static_cast<int>(std::floor(static_cast<float>(游戏X坐标 - 游戏地图左下角原点X坐标) / (2 * "灯塔"视野 + 1)) static_cast<int>(std::floor(static_cast<float>(游戏Y坐标 - 游戏地图左下角原点Y坐标) / (2 * "灯塔"视野 + 1))
灯塔AOI逻辑
对象进入(角色登入、生成怪物)：
- 根据对象坐标计算对象所属灯塔，将对象添加到灯塔的对象列表，若是灯塔上绑定了观察者，则通知观察者有对象进入
- 找出对象视野范围的灯塔，将自身绑定为其观察者，绑定灯塔会将自身现有对象列表发送给对象
对象离开(角色登出、怪物被杀死)：
- 根据对象坐标计算对象所属灯塔，将对象从灯塔的对象列表中移除，若是灯塔上绑定了观察者，则通知观察者有对象离开
- 找出对象视野范围的灯塔，解除其观察者绑定，解除绑定灯塔会将自身现有对象列表发送给对象
对象移动
- 若是对象所属灯塔没变，则不作任何操做
- 若是对象所属灯塔改变，则对旧灯塔执行对象离开逻辑，对新灯塔执行对象进入逻辑，可是要注意的是对视野的处理，先后视野交集内的灯塔不须要执行解绑和绑定操做