文末有新版描述
JPS(jump point search)概述
本文的思路受到博客：http://blog.sina.com.cn/s/blog_4a5c75d40102wo5l.html
和論文：http://www.doc88.com/p-6099778647749.html的啟發(fā)和借鑒凰狞。
JPS(jump point search)算法實(shí)際上是對(duì)A尋路算法的一個(gè)改進(jìn)，即在擴(kuò)展搜索節(jié)點(diǎn)時(shí)，提出了更優(yōu)化的策略沛鸵，A在擴(kuò)展節(jié)點(diǎn)時(shí)會(huì)把節(jié)點(diǎn)所有鄰居都考慮進(jìn)去泪勒，這樣openlist中點(diǎn)的數(shù)量會(huì)很多闪盔，搜索效率較慢瑟俭。JPS算法通過(guò)尋找跳點(diǎn)的方式违寞，排除了大量不感興趣的點(diǎn)贞瞒，減少了openlist中搜索的點(diǎn)的數(shù)量，速度大大提高趁曼。
圖例拆解JPS過(guò)程
自然鄰居：如圖所示军浆，紅色塊是自然鄰居。
被迫鄰居：點(diǎn)x的8個(gè)鄰居中有障礙挡闰，n不是x的自然鄰居乒融，且x的父親節(jié)點(diǎn)p(x)經(jīng)過(guò)x到達(dá)n的距離代價(jià)比不經(jīng)過(guò)x到達(dá)的n的任意路徑的距離代價(jià)小，則稱n是x的被迫鄰居摄悯。這其中隱含了對(duì)p(x)的描述赞季，最完整的表述應(yīng)該是，n是x在x的父親節(jié)點(diǎn)是p(x)的情況下的被迫鄰居奢驯。見圖示申钩。
跳點(diǎn)：基于點(diǎn)x(當(dāng)前點(diǎn)為x)，且搜索方向?yàn)閐(斜向或水平或垂直)叨橱，點(diǎn)y滿足一下三個(gè)條件之一，那么y就是跳點(diǎn)断盛。
a.節(jié)點(diǎn)y是終點(diǎn)罗洗，那么節(jié)點(diǎn)y是跳點(diǎn)。
b.節(jié)點(diǎn)y至少有一個(gè)被迫鄰居钢猛，那么節(jié)點(diǎn)y是跳點(diǎn)伙菜。
c.如果d是斜向搜索，如果節(jié)點(diǎn)y的水平或垂直方向上有滿足條件a命迈，b的點(diǎn)贩绕，那么節(jié)點(diǎn)y是跳點(diǎn)。注：節(jié)點(diǎn)y的水平或垂直方向是斜向向量的拆解壶愤，比如向量d=(1,1)淑倾，那么水平方向則是(1,0)，并不會(huì)往左搜索征椒，只會(huì)看右邊娇哆，如果向量d=(-1,-1)，那么水平方向是(-1,0)，只會(huì)搜索左邊碍讨，不看右邊治力，其他同理。
紅色塊為自然鄰居勃黍，黑色塊為障礙物宵统，綠色塊為被迫鄰居
水平(垂直)搜索：如圖右邊部分描述，點(diǎn)1和4如果經(jīng)過(guò)x到達(dá)覆获，還不如從點(diǎn)p(x)到達(dá)马澈，所以不用考慮點(diǎn)1,4，同理繼續(xù)向右搜索時(shí)锻梳，點(diǎn)2,5和點(diǎn)3,6箭券，都是類似的情況，直到遇到黑色的障礙疑枯，沒有發(fā)現(xiàn)感興趣的點(diǎn)辩块，x處水平方向搜索完成，垂直方向搜索類似荆永。如圖左邊部分描述废亭，在點(diǎn)x處向右搜索至點(diǎn)y時(shí)，點(diǎn)y有一個(gè)強(qiáng)迫鄰居(點(diǎn)7)具钥，因此y是從點(diǎn)x處沿水平方向搜索的一個(gè)跳點(diǎn)豆村，需要將y加入到openlist中。水平搜索結(jié)束骂删。
對(duì)角搜索：斜向搜索時(shí)掌动，需要先在當(dāng)前點(diǎn)的水平和垂直方向搜索一下，看能否找到感興趣的點(diǎn)宁玫，如果找到粗恢，則將當(dāng)前點(diǎn)加到openlist，結(jié)束斜向搜索欧瘪，如果找不到眷射，則繼續(xù)斜向多走一步，繼續(xù)佛掖，直到找到感興趣的點(diǎn)或者斜向方向遇到障礙妖碉。
一條完整路線的搜索過(guò)程：
搜索算法：
Algorithm 1 Identify Successors
Require: x:current node, s:start, g:goal
1: successor(x) <- empty
2: neighbours(x) <- prune(x, neighbours(x))
3: for all n in neighbours(x) do
4:__n <- jump(x, direction(x,n),s,g)
5:__add n to successor(x)
6:return successor(x)
Algorithm 2 Function Jump
Require: x:initial node, d:direction, s:start, g:goal
1: n <- step(x, d)
2: if n is an obstacle or is outside the grid then
3:__return null
4: if n = g then
5: return n
6: if exists n' belongs to neighbours(n) s.t. n' is forced then
7:__return n
8: if d is diagonal then
9: __for i in {1,2} do
10: ____if jump(n,di,s,g) is not null then return n
11: return jump(n,d,s,g)
A*與JPS對(duì)比
下面兩張對(duì)比圖猛拴，摘自上面的論文，可以看出蚀狰，JPS算法實(shí)在優(yōu)秀愉昆。
代碼
2020-5-15 重寫版本
- 強(qiáng)迫鄰居（被迫鄰居）定義
上圖中紅色塊為節(jié)點(diǎn)x，基于前節(jié)點(diǎn)為P(x)的情況下的自然鄰居節(jié)點(diǎn)麻蹋。而被迫鄰居則是圖中綠色的方塊（其對(duì)稱情況未畫出）跛溉。x被迫鄰居包含三層隱藏含義：首先被迫鄰居的位置是基于P(x)、x扮授、阻擋塊的相對(duì)關(guān)系定的芳室，如第三個(gè)圖所示，如果第三個(gè)圖中刹勃，P(x)的位置在節(jié)點(diǎn)6的位置堪侯，那么綠色方塊就不是x的被迫鄰居了。其次荔仁，被迫鄰居一點(diǎn)是考察非自然鄰居的節(jié)點(diǎn)伍宦。最后被迫鄰居一定是P(x)經(jīng)過(guò)x到達(dá)才能取得最短路徑的點(diǎn)。
注意：接下來(lái)的討論都基于一個(gè)前提：斜向可以通過(guò)乏梁，即如上圖4中次洼，P(x)和x可以直達(dá)，x和綠色塊可以直達(dá)遇骑。
有些算法或者游戲?qū)嵺`中卖毁，這種斜向穿過(guò)是不允許的，如P(x)->x落萎，這好比人物穿過(guò)了墻角亥啦，在游戲內(nèi)是不可以接受的，應(yīng)該走P(x)->6->x练链。
跳點(diǎn)定義
滿足如下條件的點(diǎn)視為跳點(diǎn)：
i. 節(jié)點(diǎn)y是起點(diǎn)或終點(diǎn)翔脱。
ii. 節(jié)點(diǎn)y在當(dāng)前搜索方向的前提下，有強(qiáng)迫鄰居兑宇。
iii. 當(dāng)前搜索方向是斜向碍侦，且在y節(jié)點(diǎn)處粱坤，經(jīng)過(guò)該斜向的水平分量或垂直分量方向移動(dòng)可以找到跳點(diǎn)隶糕，那么當(dāng)前節(jié)點(diǎn)y是跳點(diǎn)。搜索規(guī)則
i. 在搜索時(shí)站玄，如果直線和斜向都能通過(guò)枚驻，先在直線方向搜索跳點(diǎn)，然后在斜向上搜索跳點(diǎn)株旷。
ii. n是x的鄰居再登，若有從P(x)到n且不經(jīng)過(guò)x的路徑尔邓，且該路徑小于等于從P(x)經(jīng)過(guò)x到達(dá)n的路徑的長(zhǎng)度，那么走到x后下一個(gè)節(jié)點(diǎn)不會(huì)走到n锉矢。
iii. 只有跳點(diǎn)才會(huì)被加入openlist里梯嗽，最后找出來(lái)的最短路徑也是由跳點(diǎn)組成。
一次完整的搜索過(guò)程
起點(diǎn)S沽损，終點(diǎn)T灯节，黑色塊為阻擋黃色塊為跳點(diǎn)，紅色箭頭是搜索方向绵估，但是沒有找到跳點(diǎn)炎疆，綠色箭頭表示找到跳點(diǎn)。橫坐標(biāo)A-N国裳，縱坐標(biāo)1-10形入。
起始位置S，將A10加入openlist里缝左，開始算法流程亿遂。
從openlist里取出代價(jià)最小的節(jié)點(diǎn)(現(xiàn)在為S)，當(dāng)前節(jié)點(diǎn)沒有方向盒使，所以需要搜索8個(gè)方向崩掘，只有右上方B9點(diǎn)是跳點(diǎn)。因?yàn)楦鶕?jù)跳點(diǎn)定義iii少办，斜向搜索時(shí)苞慢，需要在兩個(gè)分量方向查找跳點(diǎn)，右方是墻壁英妓，略過(guò)挽放，上方B8點(diǎn)有強(qiáng)迫鄰居點(diǎn)C7，所以B8是跳點(diǎn)（根據(jù)跳點(diǎn)定義ii）蔓纠，所以B9是跳點(diǎn)辑畦。將B9加入openlist里。A10處理完后腿倚，將其從openlist中移除纯出，加入closelist里。
從openlist中取出B9點(diǎn)敷燎，該點(diǎn)的父親是S暂筝，所以搜索方向?yàn)橛倚鄙希枰谟倚鄙嫌补幔曳交澜螅戏剿阉魈c(diǎn)，只有B8滿足要求饭豹，將B8加入openlist鸵赖。處理完B9點(diǎn)將其移到closelist务漩。
從openlist取出B8點(diǎn)，該點(diǎn)搜索方向?yàn)樯纤剩珺8有被鄰居C7點(diǎn)饵骨，在斜上方搜索跳點(diǎn)，可以看出D8是C7的被迫鄰居茫打，所以C7是跳點(diǎn)宏悦，B8處繼續(xù)向上搜索結(jié)束。
從openlist中取出C7點(diǎn)包吝。需要搜索右上饼煞，右，上三個(gè)方向诗越。水平搜索時(shí)發(fā)現(xiàn)被迫鄰居D8砖瞧，加入openlist。右上搜索時(shí)發(fā)現(xiàn)跳點(diǎn)G3（因其在上方搜索時(shí)發(fā)現(xiàn)具有被迫鄰居節(jié)點(diǎn)的G2）嚷狞，將G3加入openlist块促。C7點(diǎn)處理結(jié)束。
取出G3點(diǎn)（為啥是G3床未，而不是D8點(diǎn)呢竭翠，因?yàn)閺目偞鷥r(jià)來(lái)說(shuō)G3比D8更小，總代價(jià)=已經(jīng)走過(guò)的距離 + 估值薇搁，估值可采用曼哈頓距離或者高斯距離）斋扰，需要搜索右上，右啃洋，上三個(gè)方向传货。向上搜索到跳點(diǎn)G2。
其余點(diǎn)路徑在圖上標(biāo)注宏娄，就不再重復(fù)了问裕。
實(shí)作中的搜索流程
(1) 若current方向是直線
i. 如果current左后方不可走且左方可走，則沿current左前方和左方尋找跳點(diǎn)孵坚。
ii. 如果current當(dāng)前方向可走粮宛，則沿current方向?qū)ふ姨c(diǎn)。
iii. 如果current右后方不可走且右方可走卖宠，則沿current右前方和右方尋找跳點(diǎn)巍杈。
(2) 若current方向是斜線
i. 如果當(dāng)前方向的水平分量可走，則沿current方向的水平分量方向?qū)ふ姨c(diǎn)逗堵。
ii. 如果當(dāng)前方向可走秉氧，沿current方向?qū)ふ姨c(diǎn)眷昆。
iii. 如果當(dāng)前方向的垂直分量可走蜒秤，則沿current方向的垂直分量方向?qū)ふ姨c(diǎn)汁咏。
上述算法流程是建立在斜向不可穿過(guò)阻擋基礎(chǔ)上。
