JPS尋路算法是啥？
JPS全稱是：jump point search，這個算法實際上是對A* 尋路算法的一個改進(jìn)，A* 算法在擴(kuò)展節(jié)點時會把節(jié)點所有鄰居都考慮進(jìn)去，這樣openlist中點的數(shù)量會很多，搜索效率較慢。
那么JPS多做了啥事呢？
在一次尋路過程中主動尋找障礙，通過障礙的位置計算出：經(jīng)過障礙代價最小的一些關(guān)鍵位置，并將這些位置中代價最小的點作為下一次尋路過程的起點。

【參考文章：傳送門】
【這里有演示動畫：傳送門】

先介紹幾個概念：
1.強(qiáng)迫鄰居：
就是指某個節(jié)點（x）上下左右有障礙，在由某方向經(jīng)過這個節(jié)點的時候，如果有方向的分量垂直于障礙的方向，則在障礙一側(cè)的斜向點就是節(jié)點（x）的強(qiáng)迫鄰居

如上圖所示，有兩個要素：
a.帶有搜索方向（剪頭）
b.帶有障礙（上下左右都行）

private Dir HaveStrictNeigh(Vector2 cur, Dir dir)
{
    bool c1, c2;
    switch (dir)
    {
        case Dir.Left:
            c1 = !IsValidPos(MoveDir(cur, Dir.Up)) && IsValidPos(MoveDir(cur, Dir.UpLeft))&& IsValidPos(MoveDir(cur, Dir.Left));
            c2 = !IsValidPos(MoveDir(cur, Dir.Down)) && IsValidPos(MoveDir(cur, Dir.DownLeft))&& IsValidPos(MoveDir(cur, Dir.Left));
            if (c1 && c2)
            {
                return Dir.Left;
            }
            else if (c1)
                return Dir.UpLeft;
            else if (c2)
            {
                return Dir.DownLeft;
            }
            break;
                   
        case Dir.Up:

2.跳點
跳點需要滿足下面三個條件之一：
a.節(jié)點是尋路的起點/終點
b.節(jié)點至少有一個強(qiáng)迫鄰居
c.如果父節(jié)點在斜方向（意味著這是斜向搜索），節(jié)點的水平或垂直方向上有滿足條件a，b的點

舉個例子：

黃色節(jié)點的父節(jié)點是在斜方向，其對應(yīng)分解成向上和向右兩個方向，因為在右方向發(fā)現(xiàn)一個藍(lán)色跳點，因此黃色節(jié)點也應(yīng)被判斷為跳點
（黃色點為起點，藍(lán)色點為跳點）

尋路流程：
1.openlist取一個權(quán)值最低的節(jié)點，然后開始搜索
2.搜索時先進(jìn)行 直線搜索（上下左右四個方向搜索，直到出現(xiàn)跳點或者到邊界），
3.再進(jìn)行 斜向搜索（四個斜方向搜索，只前進(jìn)一步），如果有跳點就加入openlist，知道當(dāng)前方向完成搜索。
4.如果斜方向沒有出現(xiàn)跳點或者到邊界，就用進(jìn)一步的斜點，在直線搜索+斜向搜索，直到所有方向都完成
5.從openlist權(quán)值最低的節(jié)點進(jìn)行搜索，直到openlist為空或者找到重點

和A相比，優(yōu)缺點：*
1.使用JPS算法比A更快（絕大部分地圖），內(nèi)存占用更小，因為openlist少了很多節(jié)點（最差的情況和A一樣，最差的是每個障礙都不連續(xù)，中間都有縫隙，這樣所有地方都是跳點了）
2.只適用于網(wǎng)格節(jié)點類型，不支持Navmesh或者路徑點尋路方式

附上一張對比圖：