寻路算法用途众多，也有多种实现。在MMOPRG游戏中是不可或缺的技术。算是基础的核心技术了。这里就不介绍寻路算法的发展史了，只介绍比较流行高效的跳点寻路算法JPS。
总结如下：
算法的基础逻辑：
JPS 又名跳点搜索算法（Jump Point Search），是基于 Grid 格子的寻路算法。
定义一、强迫邻居（forced neighbour）：
如果节点 y 是 x 的邻居，并且节点 y 的邻居有不可达的格子，并且从 parent(x)、x、y 的路径长度比其他任何从 parent(x)到 y 且不经过 x 的路径短，则 y 为 x 的强迫邻居，x 为 y 的跳点。
定义二，跳点（jump point）
1）如果点 y 是起点或目标点，则 y 是跳点
2）如果 y 有强迫邻居则 y 是跳点
3）如果 parent(y)到 y 是对角线移动，并且 y 经过水平或垂直方向移动可以到达跳点，则 y 是跳点
总结，附近有障碍才有强迫邻居，有强迫邻居就是跳点，跳点可以改变当前的方向。
规则一：
搜索跳点的过程中，如果直线方向、对角线方向都可以移动，则首先在直线方向搜索跳点，再在对角线方向搜索跳点。
规则二：
（1）如果从 parent(x)到 x 是 直线移动，y 是 x 的邻居，若有从 parent(x)到 y 的路径不经过 x 且路径长度小于或等于从 parent(x)经过 x 到 y 的路径，则走到 x 后下一个点不会走到 y。
（2）如果从 parent(x)到 x 是对角线移动，y 是 x 的邻居，若有从 parent(x)到 y 的路径不经过 x 且路径长度小于从 parent(x)经过 x 到 y 的路径，则走到 x 后下一个点不会走到 y。
规则三：
只有跳点才会加入 openset，因为跳点会改变行走方向（非跳点不会改变行走方向），最后寻找出来的路径点也都是跳点。
寻路具体流程如下：
一，若 current 当前方向是直线方向：
（1）如果 current 左后方不可走且左方可走（即左方是强迫邻居），则沿 current 左前方和左方寻找不在 closedset 的跳点。
（2）如果 current 当前方向可走，则沿 current 当前方向寻找不在 closedset 的跳点。
（3）如果 current 右后方不可走且右方可走（右方是强迫邻居），则沿 current 右前方和右方寻找不在 closedset 的跳点。
二，若 current 当前方向为对角线方向：
（1）如果 current 当前方向的水平分量可走（例如 current 当前为东北方向，则水平分量为东，垂直分量为北），则沿 current 当前方向的水平分量寻找不在 closedset 的跳点。
（2）如果 current 当前方向可走，则沿 current 当前方向寻找不在 closedset 的跳点。
（3）如果 current 当前方向的垂直分量可走（例如 current 当前为东北方向，则水平分量为东，垂直分量为北），则沿 current 当前方向的垂直分量寻找不在 closedset 的跳点。
算法描述如下
路径权值：F=G+H
其中，G为起点经过其他点到当前点的代价和，H为到目标点的代价，F为当前点的与起点终点间价值的和。假设，直线方向的格子的单位消耗为10，对角方向的单位消耗为14。
定义一个openset，用于存储和搜索当前F最小值的格子。
定义一个closedset，用于标记已经处理过的格子，以防止重复搜索。
算法图解如下
伪代码如下
def 获取NeighborList(current)
if current是起点
返回当前点九宫格内的非障碍点
elseif current与父节点是对角向
判断并添加相对位置右方的邻居点
判断并添加相对位置下方的邻居点
判断并添加相对位置对角的邻居点
判断并添加相对位置左下角的强迫邻居
判断并添加相对位置左上角的强迫邻居
elseif current与其父节点是水平
判断并添加相对位置右方的邻居点
判断并添加相对位置上方的强迫邻居
判断并添加相对位置下方的强迫邻居
elseif current与父节点是垂直
判断并添加相对位置下方的邻居点
判断并添加相对位置左方的强迫邻居
判断并添加相对位置右方方的强迫邻居
def 递归寻找JumpPoint(target，current，direction)
if target是终点
返回终点
if direction是对角向
if target存在强迫邻居
返回target
if （递归寻找JumpPoint(target：横向+1，target, 横向）结果不为空
返回target
if （递归寻找JumpPoint（target：纵向+1，target，纵向）结果不为空
返回target
elseif direction横向
if 上下方有强迫邻居
返回target
elseif direction纵向
if 左右方有强迫邻居
返回target
返回 递归寻找JumpPoint（target下一个点，target，direction）
def 寻路最优路径
起点加进openset中
While（openset.Count > 0）:
从openset中取出F值最小的点并设置为Current
如果Current是终点 寻路结束 返回
把Current加进closedset
NeighborList = 获取NeighborList（当前点）
for NeighborList
JumpPoint = 递归寻找JumpPoint（Neighbor,Current，Current到Neighbor朝向）
if JumpPoint不在closedset中
计算并设置Current与JumpPoint的G值
计算并设置Current与JumpPoint的H值
计算并设置JumpPoint的F值
将Current设置为JumpPoint的父节点
如果Neighbor在openset中
计算Current的G与该Neighbor的G值
如果G值比该Neighbor的G值小
将Current为该Neighbor的父节点
更新Neighbor的GF值
若不在
计算并设置Current与Neighbor的G值
计算并设置Current与Neighbor的H值
计算并设置Neighbor的F值
将Current设置为Neighbor的父节点
如上，为个人对JPS基础算法的总结。
另外，以上JPS还可以进一步优化，如JPS+ 。感兴趣的可参考如下大佬博客
参考与引用
JPS/JPS+ 寻路算法 - KillerAery - 博客园 (cnblogs.com)
JPS（Jump Point Search）寻路及实现代码分析_青鸿生的博客-CSDN博客_jps寻路
PathFinding.js (qiao.github.io)
Jump Point Search(JPS)算法总结与实现（附Demo) - 知乎 (zhihu.com)
