游戏中的寻路算法研究

1)Unity NavMesh研究

思考：毫无疑问，unity中自带的navmesh寻路是比较健全的，无奈在服务器中无法使用，这样子我们没办法做怪的导航，但是可以先体验下都有哪些api，并且可以可视化的看效果。

1)打开导航网格Window->AI->Nagivation基于几何体的环境生成的点击到哪个地方，就发射一条摄像，检测下碰撞。2)OffMeshLink组件: 打开后可以跳过去。3)Unity中重新生成网格数据Navigation:Agents // 数据Bake4)扩展我们不仅仅是为了在Unity中搞，而是要生成到服务器中，实现NPC的导航。5)原理生成多边形NavMesh小块点的信息，边界信息，相邻信息,这样子就可以根据起点和终点去实现了。 Unity是根据AStar算法。 根据点依次移动，就生成了导航。6)障碍物的规避和其它代理物，可以相互避开。 ==》 RVO(考虑到速度)2种方式：一种是改变导航网格的信息，这样子肯定能找到目标, 开启障碍(NavMesh Obstacle的Crave)的。 // 消耗高一种是一直尝试走，查找失败了。7)    NavigationObject点击Mesh Renderers(带有Mesh Renderer脚本的都会列出来)全选勾选Navigation Static，此时就会发现Navigation Area下拉框变为可以选择的点击Scene Filter下的All点击Bake选项卡下的Bake按钮，就会发现生成的导航网格8)体素将场景中的物体，变成一个个小块。

2)优先队列的研究

1)用途:海量定时器：如活动3天后开，避免轮询。取出前面几个:寻路搜索算法:  A*算法2)数据结构：二叉堆。

思考：这个不仅仅是定时器，也为下面的A*学习打基础，毕竟A*是基于权重的，既然是基于权重，那么优先队列中的权重就能用上了。

3)A*算法研究

1.jps // 更极致的格子寻路算法2.AStar较为全能，即可用于三角形，又可格子

4)漏斗算法

5)导出NavMesh到服务器使用

参考资料：

PathFinding.js (qiao.github.io)