游戏寻路方案

Grid

将游戏原始地图分割成网格，数据结构表现为二维数组，用0和1分别标识格子是否可走，没有地图的高度信息，因此比较适合2d地图，例如战棋类游戏

• 优点：容易动态修改地图的某个格子是否可走。算法可以多选，A*和JPS都支持
• 缺点：内存占用比较大，格子越小寻路的精确越高，同时占用的内存也会更大

2d地图寻路：

• 首先在地图中每0.5的间隔生成二维数据的高度图（不允许有多个高度），然后在地编工具中美术把地图的可走块标记出来，根据标记的点把它周围的格子广度遍历找出所有能走的点，其它就是不可走，将高度图二维数据结合二次处理后再次导出
• 服务器遍历高度图的每一个格子，对比它上下左右四个格子的高度差，当高度差都不超过阈值时标志该格子为可走，否则不可走，由此得出一个可走图，用可走图来做寻路

多层寻路网格：

• 多层寻路网格需要把所有可行走的区域分成多个层级，每一层都有自己的网格数据，也可以包含当前层的楼梯部分的数据，例如二层的寻路网格数据可以包含一到二层的楼梯部分的数据，也将楼梯部分的数据单独拆分出来成为一个独立的层级
• 寻路时只关心当前层的数据，以及当前层上一层与下一层的数据，当要跨越层级寻路时，首先确定目前所在层级，目的地的层级，按次序一层层往上走或者往下寻路，比如目的地是二楼，所在的起点是一楼，那么由一楼层级开始，从起点寻路到楼梯层的入口点，进入楼梯层后，从楼梯层数据中找到与二层楼衔接的入口点并寻路，最后到达二层楼并向目的地寻路
• 层级网格数据需要对层级之间的入口区域做记录，比如第一层某个矩形为第一层与第二层的衔接，只要进入这个范围就认为切换了层级，角色身上的层级标记也相应地变化，此时索引到的寻路网格数据也变成了当前层的数据

优化：

• 因为网格是以一个格子为单位，因此会以红色那条路线移动，实际上当AB中间不存在障碍物时，应该以黑色的路线移动会更自然，因此在寻路前先判断两点之间是否有障碍物，若两点之间无障碍则无需寻路。
  • 根据两点坐标的方向向量，如果是垂直方向，则往目标y轴逐个格子判断是否可走，如果是水平方向，则往目标x轴逐个格子判断是否可走。
  • 如果是斜向，则根据直线斜率公式y=kx+b；计算得到偏移值b和斜率k，遍历两点坐标之间的所有格子，根据k值边界过滤，并判断直线和矩形的关系。
    • 直线与矩形相交：判断相交的格子是否可走，如果相邻的两个格子都不可走，则被夹在中间的格子也应该不可走
    • 直线在矩形上方：根据k值分别缩小边界
    • 直线在矩形下方：根据k值分别缩小边界

WayPoint

在地图编辑器中直接标记一些路点，路点之间不能存在障碍，寻路只能在这些已知的路线进行，因此比较适合NPC固定路线移动。

• 优点：占用极少的内存和计算消耗
• 缺点：每张地图都需要人工去编辑复杂的路点，工作量大。

Recastnavigation 源码

导航网格是由多个poly组成，同一个poly中的两点在忽略高度的情况下是可以直达的，而两点位于不同的poly，则利用导航网格配合A*算法得到经过的poly，再算出具体路径，同时引入了地图高度，比较适合3d地图。

• 优点：更为精准表达地图，poly会比grid数量少，占用的内存会少
• 缺点：unity的navmesh可以导出寻路网格，但是和recastnavigation库不完全兼容，因此可以采用第三方插件导出寻路网格第三方插件

地图数据处理

• 服务端加载的源地图数据需要在多线程内共享并且加锁，避免浪费内存。
• 调用主体是lua，so库返回包含源数据指针和副本数据指针的userdata，副本数据指针默认指向源数据。
• 如果需要动态改变地图的格子是否可走，则需要拷贝源地图数据，创建地图数据的副本，并改变副本数据指针的指向，后续的所有操作都基于副本数据，gc时把副本数据清理，源数据常驻。