-本文由 伯樂在線 - xxmen 翻譯，黃利民 校稿。未經(jīng)許可，禁止轉(zhuǎn)載！
英文出處：theory.stanford.edu。歡迎加入翻譯組。
本系列：
- 關(guān)于尋路算法的一些思考（1）：A* 算法介紹
- 關(guān)于尋路算法的一些思考（2）：Heuristics 函數(shù)
- 關(guān)于尋路算法的一些思考（3）：A* 算法的實(shí)現(xiàn)
- 關(guān)于尋路算法的一些思考（4）：A* 算法的變體
- 關(guān)于尋路算法的一些思考（5）：處理移動中的障礙物
- 關(guān)于尋路算法的一些思考（6）：預(yù)先計(jì)算好的路徑的所用空間
- 關(guān)于尋路算法的一些思考（7）：地圖表示
- 關(guān)于尋路算法的一些思考（8）：長期和短期目標(biāo)
- 關(guān)于尋路算法的一些思考（9）：尋路者的移動成本
- 關(guān)于尋路算法的一些思考（10）：最短路徑的用戶體驗(yàn)
- 關(guān)于尋路算法的一些思考（11）：尋路算法的其他應(yīng)用
- 關(guān)于尋路算法的一些思考（12）：AI 技術(shù)
最短路徑的用戶體驗(yàn)
玩家是游戲最重要的部分。你想讓用玩家愉快地玩耍！你不想讓他（她） 認(rèn)為電腦在作弊，或是游戲單位運(yùn)行不正常。
愚蠢的移動
如果尋路算法運(yùn)行不正常，用戶將最后放棄并選擇手動移動單位。避免出現(xiàn)這種情況！在《文明》中，游戲的規(guī)則允許利用鐵路無代價地移動。但是，游戲的導(dǎo)航只能進(jìn)行其他方式的有代價移動。這樣導(dǎo)致玩家拒絕使用游戲?qū)Ш?，而選擇利用鐵路手動移動單位。在《命令與征服》中，游戲單位會被困在U形的陷阱中，玩家將不得不手動引導(dǎo)這些游戲單位。一個愚蠢的游戲?qū)Ш綍辜て鹜婕业牟粷M，導(dǎo)致他們自己手動移動單位，因此請讓你游戲的導(dǎo)航程序更加完善。
聰明的移動
把游戲單元做得太過聰明和做得太過愚蠢一樣會造成不好的后果。如果玩家需要應(yīng)對戰(zhàn)爭迷霧導(dǎo)致的視野受限影響，而游戲?qū)ぢ穯卧芸吹饺貓D，能在玩家毫不知情的時候神秘地知道該去往哪里。這會讓玩家明顯地感到奇怪的事情正在發(fā)生。換句話說，它給出了更好的路徑。一種妥協(xié)的方法是提高在未被探索區(qū)域的移動花費(fèi)。例如，如果你的正常移動花費(fèi)是草地上1，森林中3，山地7，在未被探索區(qū)域就應(yīng)該設(shè)置對應(yīng)的不同花費(fèi)：草地為5，森林為6，山地為7。這樣游戲單元會把山地和草地納入考慮，但只是一個提示，不會過度考慮。提高穿越未被探索地區(qū)的移動代價，將會使尋路程序傾向于盡可能停留在已被探索的區(qū)域中。你可能也想為偵察單元提供一個相反的策略：它們應(yīng)偏愛未被探索的區(qū)域。
盡量使你的尋路單元在太過愚蠢和太過聰明之間保持平衡。你的目標(biāo)應(yīng)該是使游戲?qū)ぢ穯卧屯婕铱赡艿囊苿有袨橄嗥ヅ洹?/p>
多線程
你可以使用多線程來改善玩家體驗(yàn)。當(dāng)有一個游戲單位需要一條路徑時，允許它開始向著目標(biāo)位置直線移動，同時向?qū)ぢ逢?duì)列添加一個請求。在另一個（優(yōu)先級較低）的線程中，把請求從隊(duì)列中去除并進(jìn)行路徑尋找。該游戲單位會立即開始移動，因此玩家不會疑惑是不是出現(xiàn)了問題，你也不會有過高的CPU負(fù)載（會拖慢游戲的其余部分）在進(jìn)行路徑計(jì)算的時候。
多單元
如果你的游戲允許多個單位構(gòu)成組一起移動，請?jiān)囍屢苿涌雌饋砀佑腥ぁＤ憧梢哉业揭粭l路徑讓它們都沿著路徑移動，然后讓它們單獨(dú)沿著路徑移動，但這會導(dǎo)致這些單位中的一條直線或者單位會穿過其它單位前進(jìn)。因此，稍微區(qū)分一下路徑它們就能平行地移動了。另外，還可以選取一個“領(lǐng)導(dǎo)”單元來沿著路徑移動，同時讓其它單元執(zhí)行單獨(dú)編寫的“跟隨”行為。這個跟隨行為可以非常簡單，只要向著“領(lǐng)導(dǎo)”所處的方向前進(jìn)，同時停留在一段距離之外，或者它就像鳥類成群結(jié)隊(duì)飛行。
多路徑點(diǎn)
即使給定了最優(yōu)的路徑，玩家可能會偏愛其它不同的路徑。你應(yīng)該允許玩家在路徑上標(biāo)記路徑點(diǎn)：玩家可以點(diǎn)擊通向目的地的路徑上二到三個路徑點(diǎn)，而不是簡單地點(diǎn)擊目的地。（很多實(shí)時策略游戲使用shift-點(diǎn)擊來完成這項(xiàng)操作。）你當(dāng)前有了三到四條較短的路徑來進(jìn)行計(jì)算，同時你節(jié)省了一些時間。玩家對于整體的路徑安排同樣擁有部分的控制權(quán)，例如，你的游戲?qū)Ш秸业搅艘粭l通向西部山地的路徑，但出于安全考慮，玩家希望停留在東部山地（靠近友軍防御塔）。
在單位移動程序中的主要改變是，你將擁有一個目的地的列表，而不是一個單一的目的地。首先尋找一條到達(dá)第一個目的地的路徑，當(dāng)你到達(dá)時，從列表中刪除它然后繼續(xù)尋找到達(dá)下一目的地的路徑。這種做法可以降低游戲過程中的延時并且提高系統(tǒng)的吞吐量。
