由于老版本项目要在wegame上面项目，要把新版本的寻路系统迁移到老版本上。
先开始就是迁移A*算法过来。
我们的寻路需求有以下特点：
1.角色人物是有碰撞体积的，因此是存在动态主档点的。
2.有比较大的地图1000x1000，且阻挡点也相对较多。
3.由于几乎所有地图中不存在孤岛（有例外情况），因此也没有时间限制。
老的A*算法主要解决了以下特异性的问题：
1.终点不可达时，使用连线T探索替换终点。（这里最后用逆正方形搜索法 按半径1-100的正方形搜索最近可达点）
2.由于没有时间限制，且地图较大，独立起了一个线程来算路径，防止阻塞主线程。
3.存储了一个last_node来存储离终点最近的节点，用来反向溯源（这里主要是针对孤岛和不可达的特殊情况，这里会以起点遍历完所有连通节点）。
4.由于根据当前的阻挡点情况计算了起点到终点的路径，当行走过程中走到有动态阻挡点的路径上时会重新寻路。
迁移完成后发现大地图寻路耗时太长，响应太慢了，点击几秒才开始走，影响游戏体验。
使用JPS算法
Jump point search算法，实际上是A*的变体，跳点寻路的优点主要在关键节点的叠代上，我们之后A*算法的叠代每次更新最优节点的临近八节点数据。就算中间没有障碍物，从起点到终点也要把中间的节点依次加入开闭表才能找到终点。
跳点寻路，主要在叠代中进行了剪枝，减少了对称路径，这里的理论知识可以参考
我这里简介点讲就是跳点的搜索原则
一、先水平再斜向
水平方向找到跳点或者障碍停止，一次叠代多步
斜方向每次移动一步
二、跳点规则
1.水平垂直方向
父节点水平方向 如果节点垂直方向临近节点有障碍物，成为跳点。 父节点垂直方向 如果节点水平方向临近节点有障碍物，成为跳点。
2.斜方向
父节点斜向，父节点和该节点的公共邻居节点有障碍物，成为跳点。
3.当斜向探索时，其水平垂直分量上有跳点，那么该斜向探索点也是跳点（这个地方很难理解，因为我看到的所有资料几乎都没有解释这个跳点有什么作用，我最先开始实现的时候也没有加这个跳点。但结果是能找到终点，但是路径存在一些问题，其实这个跳点主要是保证路径的全局最优的，因为这个跳点可能会添加一些靠近终点的中间跳点）
三、跳点的搜寻方向跟父节点相关，没有跳点的情况下，搜索方向如果是水平或垂直则与父节点搜寻方向相同，
斜方向除了加上父节点方向外还要搜索其斜向的水平垂直分量方向。有跳点（跳点规则中的1、2规则）还需要根据情况加上对应的节点方向。
实现后发现JPS在内存和耗时上都有比较大的提升。
注意要点
1.启发函数
这个函数跟叠代速率以及最优路径相关，比较重要。
2.closedset的评估值g到底要不要更新
看情况，如果你是要找一个最优路径，那么要更新closedset的g值以并且递归形式更新子节点值，因为其后继节点可能在openset中，会影响下一个最优节点的选用。
当然一般来讲对于游戏来讲，只要你的启发函数没有大问题，不更新closedset的值影响也不大，就是可能有一些局部没有按最优的路径走，影响也不大。
3.独立线程寻路动态点的加锁，加锁会影响性能。但是实际上远距离的寻路，判断离当前比较远的区域的动态点意义不大，是否只判断离当前节点较近的动态阻挡点更好。
后续跟进问题
引入JPS算法之后长距离的寻路问题解决了，但是短距离的寻路产生了新的问题，游戏组队跟随出现卡顿情况，起初认为是算法问题，后面发现是服务器同步的问题。由于JPS总是倾向先斜向走再十字方向走，跟随时如果队长在十字方向，其他所有的队员在跟随时都会争抢十字方向的位置，导致不同队员向服务器同步位置时会失败，因为队员都是有阻挡点的，JPS算法会导致这种冲突发生的概率变高。
这边最后还是针对短寻路进行了优化，短距离还是使用A*算法，A*算法在短距离寻路的性能消耗也是可接受的，而且冲突的概率不高。
