本文由 伯樂在線 - xxmen 翻譯钞速，黃利民 校稿荐虐。未經(jīng)許可踏枣，禁止轉(zhuǎn)載昌屉！
英文出處：theory.stanford.edu。歡迎加入翻譯組茵瀑。
本系列：
- 關(guān)于尋路算法的一些思考（1）：A* 算法介紹
- 關(guān)于尋路算法的一些思考（2）：Heuristics 函數(shù)
- 關(guān)于尋路算法的一些思考（3）：A* 算法的實現(xiàn)
- 關(guān)于尋路算法的一些思考（4）：A* 算法的變體
- 關(guān)于尋路算法的一些思考（5）：處理移動中的障礙物
- 關(guān)于尋路算法的一些思考（6）：預(yù)先計算好的路徑的所用空間
- 關(guān)于尋路算法的一些思考（7）：地圖表示
- 關(guān)于尋路算法的一些思考（8）：長期和短期目標
- 關(guān)于尋路算法的一些思考（9）：尋路者的移動成本
- 關(guān)于尋路算法的一些思考（10）：最短路徑的用戶體驗
- 關(guān)于尋路算法的一些思考（11）：尋路算法的其他應(yīng)用
- 關(guān)于尋路算法的一些思考（12）：AI 技術(shù)
一個尋路算法會計算出一條繞過靜止障礙物的路徑怠益，但如果障礙物會移動呢？當一個單位移動到達某特定點時瘾婿，原來的障礙物可能不在那點了，或者在那點上出現(xiàn)了新的障礙物烤咧。如果路線可以繞過典型的障礙物偏陪，那么只要使用單獨的避障算法來配合你的尋路算法。尋路算法會尋找到期望的路徑煮嫌，并且在沿著路徑的同時繞過障礙物笛谦。但是如果障礙物可以移動，進而導(dǎo)致路徑不停地發(fā)生顯著改變昌阿，就應(yīng)考慮使用尋路算法來避障饥脑。
重新計算路徑
我們希望游戲世界隨著時間改變。一條一段時間之前發(fā)現(xiàn)的路徑懦冰，可能不再是現(xiàn)在的最優(yōu)路徑灶轰。用新的信息更新舊路徑是值得的。下面列出的是一些用來判斷決定是否需要重新計算路徑的標準：
- 每N步一次：這樣保證用來計算路徑的信息不會舊于N步刷钢。
- 當額外的CPU時間可用時：這樣可以實現(xiàn)路徑質(zhì)量的動態(tài)調(diào)整笋颤。即使使用了更多的游戲單位，或者是在一臺較慢的電腦上運行游戲内地，每個游戲單位的CPU使用率都可以降低伴澄。
- 當游戲單位轉(zhuǎn)彎或者通過一個關(guān)鍵路徑點的時候赋除。
- 當游戲單位附近的世界發(fā)生改變的時候。
重新計算路線的主要缺點在于有很多路徑信息被丟棄了非凌。例如举农，如果路徑長100步，并且每十步進行一次重新計算敞嗡，那么路徑的總步數(shù)是100+90+80+70+60+50+40+30+20+10 = 550颁糟。對于一個長M步的路徑，總共大概進行了M^2步計算秸妥。因此滚停，如果你想要得到很多條長路徑，重新計算路線并不是一個好主意粥惧。重復(fù)使用路線信息键畴，而非丟棄，這樣會是更好的辦法突雪。
路徑剪接
當一條路徑需要被重新計算時起惕，意味著世界正在改變。給定一個變化中的世界咏删，地圖上的鄰近部分比遠處的部分更好了解惹想。我們可以遵循一個局部修正策略：找到附近的一條好路徑，并且假定較遠的路徑直到我們靠近它了才需要重新計算督函。我們可以僅僅重新計算路徑的前M步嘀粱，而不是整條路徑：
- 設(shè)p[1]..p[N] 是路徑剩余部分（N步）
- 計算一條從p[1]到p[M]新路徑
- 剪接新路徑到舊路徑中，通過移除p[1]..p[M]然后插入新路徑到這些空位置上辰狡。
因為p[1]和p[M]相距不到M步锋叨，所以新路線不太可能長。不幸的是宛篇，像新路徑又長又不是非常好的情況娃磺，也有可能發(fā)生。上圖展示了這樣一個情況叫倍。原始的紅色路徑是1-2-3-4偷卧，棕色區(qū)域是障礙。如果我們到達2然后發(fā)現(xiàn)從2到3的路徑被阻擋了吆倦，路徑剪接會用綠色的路徑2-5-3來替換2-3听诸，導(dǎo)致這個單位循著路徑1-2-5-3-4移動。我們可以看到這并不是一個好的路徑逼庞，藍色路徑1-2-5-4是更好的選擇蛇更。
不好的路徑經(jīng)常可以通過計算新路徑的長度來判斷。如果它明顯比M長派任，它就可能是不好的路徑砸逊。一個簡單的解決方法，給尋路算法添加一個上限（最大路徑長度）掌逛。如果找不到一條短的路徑师逸，這個算法返回一個錯誤代碼，在這種情況下豆混，使用重新計算路線而不是路線剪接來得到一條像1-2-5-4這樣的路徑篓像。
對于沒有涉及到這類情況的例子，對于一條N步的路徑皿伺，路線剪接會計算2N到3N路徑步數(shù)员辩，取決于一條新路徑進行剪接插入的頻繁程度。這是一個相對低的代價鸵鸥，使得算法能對世界的改變作出反應(yīng)奠滑。意想不到的是，這個花費的代價大小取決于M妒穴，也就是進行剪接的路徑步數(shù)宋税。M控制一個反饋和路徑質(zhì)量的平衡，而不是CPU時間的影響讼油。如果M的值較大杰赛，單位的移動將不會快速地對地圖的改變作出反饋。如果M太小矮台，被剪接的路徑可能太短乏屯，以至于不能得到可以繞過障礙的替換路徑：更不優(yōu)的路徑（例如1-2-5-3-4）可能會被找到，嘗試M的不同取值和不同的剪接標準（例如每隔3/4 M步）瘦赫，來看看怎樣做最適合你的地圖瓶珊。
路徑剪接比重新計算路徑明顯地快了許多，但它對于路徑的重大改變并不能很好地應(yīng)對耸彪。不過很多這種情況可以容易地發(fā)現(xiàn)，并直接使用重新計算路徑來代替路徑剪接忘苛。它同樣有幾個可以調(diào)整的變量蝉娜，比如M和進行新路徑的尋找的時間，所以它可以被調(diào)整為適合不同的情況（即使是在運行的時候）扎唾。但是路徑剪接并不能處理游戲單位需要確定位置進而來互相穿過的情況召川。
監(jiān)視地圖的改變
選擇重新計算全部或部分路徑在特定的時間間隔，是對地圖的改變來觸發(fā)重新計算胸遇。地圖可以分成不同的區(qū)域荧呐，每個游戲單位可以在特定的區(qū)域表現(xiàn)出興趣。（所有包括部分路徑的區(qū)域都可能是感興趣的，或者僅僅是鄰近的包含部分路徑的區(qū)域）無論障礙進入或離開某個區(qū)域倍阐，那個區(qū)域就標記為已經(jīng)改變概疆，然后所有對那個區(qū)域感興趣的游戲單位都會被通知，所以路徑可以在考慮障礙發(fā)生變化這一前提下被重新計算峰搪。
這一技術(shù)有很多可能的變化岔冀。例如，我們可以僅僅在特定的時間間隔通知游戲單位而不是立即通知概耻。并且多次改變可以被組合成一次通知使套，所以不再需要過多的進行重新計算路徑。另一個變化是讓游戲單位來查詢地區(qū)的狀態(tài)鞠柄，而不是讓地區(qū)來通知游戲單位侦高。
監(jiān)視地圖的改變，避免了游戲單位在障礙物沒有發(fā)生變化的時候進行重新計算厌杜，因此當你有很大地區(qū)不會經(jīng)常發(fā)生改變的時候奉呛，可以考慮使用這種方法。
預(yù)測障礙物移動
如果障礙物的移動可以被預(yù)測期奔，那就可以在進行尋路時把未來的障礙物位置納入考慮侧馅。像A這類算法有一個代價函數(shù)，來決定通過地圖上某點的困難程度呐萌。A可以被修改成實時更新到達一點所需要的時間（由當前的路徑長度決定）馁痴，這個時間也可以被傳入代價函數(shù)中。代價函數(shù)就可以把時間納入考慮肺孤，然后就可以使用在那個時刻的障礙物預(yù)測位置罗晕，來決定那個地圖位置是否無法通過。但是這個修改并不完美赠堵，因為它不會考慮在某個點等待障礙物離開路徑的可能性小渊，另外A*并不是設(shè)計用來區(qū)分相同路線上的路徑，而是時間不同的點茫叭。
