算法-JPS寻路设计思想

基于A*思想做以下简化：

直线（横纵扩展）

• 没有阻挡情况下，“剪枝”剩1个邻居，往前走。
  

对角线

• 没有阻挡情况下，“剪枝”剩3个邻居，（对3个邻居的处理：先直线后对角线）
  

• eg：
  

定义

• 跳点和强迫邻居
  （1）如果current左后方不可走且左方可走（即左方是强迫邻居），则沿current左前方和左方寻找不在closedset的跳点；
  （2）如果current右后方不可走且右方可走（右方是强迫邻居），则沿current右前方和右方寻找不在closedset的跳点；
  （3）如果parent(y)到y是对角线移动，并且y经过水平或垂直方向移动可以到达跳点，则y是跳点。

补充

• 1，起点没有parent，所以无法剪枝。