大家好，歡迎大家關注我的知乎專欄- 慢慢悠悠小馬車。
- JPS是為了解決A*算法中的路徑對稱和多餘擴充問題，而提出的一種适用于無向歸一化代價栅格地圖的最優路徑搜尋算法，一般速度快于A*。（歸一化代價指沿不同方向的機關步長的代價相同）
- JPS最初是在《Online Graph Pruning for Pathfinding on Grid Maps》提出的。本文隻簡述要點。
- JPS特點在于，有選擇的隻擴充跳點，跳點間的栅格被跳過，不加入OpenList。跳點（Jump Point）就是路徑的轉折點（Turn Point）。
- 計算跳點的過程，是向2個方向擴充，首先是橫平豎直的方向，然後是對角線方向（必須在後）。
- 弄懂這幾個重要概念，就可以了解JPS的算法流程了。以下都是基于比較2種路徑的長度：parent→center→neighbor VS parent→非center→neighbor。
- 自然鄰居：假設中心栅格的8鄰域都不被障礙物占據，剪枝後剩餘的鄰居節點。
- 強迫鄰居：8鄰域中的非自然鄰居，且靠近障礙物。Def1。
- 跳點：滿足Def2中的任一條件即可。
- 是終點。
- 有強迫鄰居。
- 是路徑轉折點。（會得到2個跳點）
