關于尋路算法的一些思考（9）：尋路者的移動成本

本文由 伯樂在線 - 土豆粉ss 翻譯，黃利民 校稿。未經(jīng)許可，禁止轉載！
英文出處：theory.stanford.edu。歡迎加入翻譯組。

本系列：

尋路者的移動成本

當使用尋路算法的時候，你可能想把地圖空間當做一種不單是用通暢或阻礙來表達的東西。通常地圖空間會有更多的已知信息，比如通過那片區(qū)域的移動難度。比如，沼澤和高山可能比草地和沙漠更難通過。使用算法，比如A*，你可以把給信息編碼代入成本函數(shù)中。下面列出了一些計算移動成本的想法，也許會派上用場。

海拔

高海拔（比如高山）比低海拔有更高的移動成本。當使用成本函數(shù)計算的時候，只要可能移動單元會試圖一直停留在低洼的地方。例如，如果你的起始點和終點都在高地，移動單元可能會先下山，移動一段時間后再次登山。

爬山移動

相對于高海拔有一個高的成本，爬山成本也很高。這就避免了上面描述的奇怪狀況。使用這種成本函數(shù)，移動單元就會盡量避免爬山尋路。面對同樣的情況，移動單元也會避免尋路時最后還要爬山；在整個移動過程中，單元能始終保持在一個高的海拔區(qū)間。使用這種成本函數(shù)有益于士兵（soldiers）這樣的下山容易上山難的單元。

上下山移動

一些單元，比如坦克（tanks），上下山都很困難。你可以設置一個比較高的成本下山，然后一個更高的成本上山。這個單元就會盡力避免改變移動時的海拔。

地形

不同的地形，可以設置不同的移動成本。

森林、高山和山丘

可以使用不同的地形類型來代替使用海拔的概念。比如在游戲《文明》（civilization）中，每個地形都有一個和它相關的移動成本。這種移動成本表可以適用于所有的單元，或者每一個單元類型都有匹配它的不同的移動成本。比如solider在森林中移動可能沒有任何困難，但是tanks在森林中移動就很艱難。改變地形的時候設置移動成本是個很好的辦法，從草地到高山會比從山丘到高山成本高，從山丘到高山移動又比高山之間移動成本高。

道路

在很多游戲里，道路的原始目的就是讓移動變得可能或者更簡單。在選擇好移動成本函數(shù)后，可以加一條道路來修正它。一個可能的辦法就是用成本除一個常數(shù)(比如2)；另外的辦法是設置一個表示沿著道路移動的成本常量。

我強烈的建議不要設道路移動成本為零。這會給尋路算法比如A*帶來麻煩，因為它可能會算出這樣的一種路徑，即從一點到另一點間沿著一條彎曲的道路行進，其實沒有指向任何目的地。這樣算法不得不搜索一個很大的區(qū)域，確保沒有這樣的路存在。注意在Civilization的游戲中，鐵路移動成本是零，但是當使用”auto-goto”函數(shù)的時候，鐵路的移動成本就不是零了。這就是游戲使用了尋路算法的證據(jù)。

墻壁或其它障礙

無需既檢查移動成本又要檢查尋路算法里的路障，用移動成本一個計算就可以了。只要給你的路障設置一個非常高的移動成本即可。 (在A*算法里)當展開節(jié)點的時候，檢查成本是否太高；如果是的話，就放棄這個節(jié)點吧。

有坡度的地形

你也許想在任何山丘中的移動設置較高的成本，來代替使用上山和下山。這樣做，需要計算全部地勢的斜度（通過觀察行進路徑的當前位置和它相連部分的最大高度差），使用這個來作為移動的成本。地勢陡峭的陸地成本高，地勢比較平緩的成本低。這種方法和上下山移動方法計算成本不同，因為它關注的是陡峭的地勢，而之前的方法關注的是在一個陡峭的方向上移動的單元。特別是，如果你正在一個山丘上，而且可以向左或向右移動而不用向上或向下，那么上下山方法會認為這種情況成本低，而這個方法會認為成本高（因為地形本身陡峭，即便不用上下山的移動）。

根據(jù)地形陡峭判斷成本的方法可能對于單元的移動來說不是很合理，但是你可以使用尋路算法不只是尋找單元的路徑。我會使用它來尋找道路，管道，橋梁等等。如果你想在平地上建設這些項目，尋找一條道路或者管道的路線時，你可以考慮這種判斷地勢坡度的方法。參考這部分的應用可以挖掘出更多的想法。

敵對和友好單元

再設置一個修正器可以幫你避免敵人的單元。使用 influence 地圖，你可以監(jiān)視附近有敵人或者友好單元的區(qū)域、或最近有士兵被殺的區(qū)域、或最近剛被探索過的區(qū)域、或是靠近一條逃跑路線的區(qū)域、抑或是最近穿越過區(qū)域（《帝國時代2》里在 influence 尋路中使用了 influence 地圖）。一個influence地圖可能對友好單元有積極的作用，對敵人單元有消極的作用。無論何時你在一個敵對的領域里，通過增加移動成本，你可以改變你的單元離敵人遠一點。

更復雜的是（可能在influence地圖下是不行的）參考可見度。對敵對單元來說你的單元是否可見？換句話說，你的單元是否可遭受攻擊？你的敵對單元有可能向你開火么？

設置信號標（beacon）

如果你的地圖是設計出來的不是自動生成的，你可以添加額外的信息進去。比如，舊的貿易路線經(jīng)常會經(jīng)過一些變成貿易城鎮(zhèn)的特定地點。這些地方就叫beacon，即優(yōu)質路線上的已知地點。與beacon的距離值可以加入移動成本中，這種方法是根據(jù)對beacon的偏好影響尋路結果的。

燈塔、城市、山路和橋梁等都是beacon比較好的選擇。

燃料消耗

注：為了保持狀態(tài)空間比較小，你需要將燃料的價值四舍五入成一個近似的測量單元。不幸的是，這會將讓搜索變得效率低下。

不但需要觀察單元去某些地方所用的時間，你也要考慮它花費掉的燃料。當單元的燃料級別比較低的時候，燃料消耗可能會被賦予更大的權重。

就像上面描述的，為了跟蹤地圖上能源的耗費量，你需要使用狀態(tài)空間。每個狀態(tài)可能是成對的描述：<坐標,燃料>。然而，狀態(tài)空間可能會變得非常大，所以不用普通的A*算法，尋找其他替代方法也是值得考慮的。

我們的另一個選擇是加入有界成本的A算法（A with Bounded Costs (ABC)）使用 ABC 算法，你可以給成本（比如“燃料”）設置一個界限（比如”20加侖”）。

最后編輯于 ：
?著作權歸作者所有,轉載或內容合作請聯(lián)系作者
【社區(qū)內容提示】社區(qū)部分內容疑似由AI輔助生成，瀏覽時請結合常識與多方信息審慎甄別。
平臺聲明：文章內容（如有圖片或視頻亦包括在內）由作者上傳并發(fā)布，文章內容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

相關閱讀更多精彩內容

友情鏈接更多精彩內容