RTS里面經(jīng)常會有很多角色，群體一起尋路到目的地附近，這種尋路是如何實現(xiàn)的，今天給大家詳細的講解基于流場尋路的算法。在本教程中，我將解釋向量場尋路及其相對于Dijkstra等傳統(tǒng)尋路算法的優(yōu)勢。對Dijkstra算法和勢場的基本理解將有助于理解本文，但不是必需的。

尋路的問題有很多種解決方案，如AStar等, 每種尋路的方案都各有優(yōu)缺點，大部分的尋路，都是角色要從A點走到B點，然后調用尋路算法找出一條路徑出來。通常情況下這樣是不會有問題的，但是對于像RTS這種游戲需要做群體尋路，從A點到B點一群角色走過去，如果每個角色都單獨尋路，這樣性能開銷會比較大，所以今天我們?yōu)榱私鉀Q這個問題，介紹基于流場向量的尋路。它的原理是把目標點的流場計算出來，所有移動的目標共用這個流量場。接下來本文講詳細的介紹流場尋路的核心技術與步驟。(本文是將地圖基于網(wǎng)格來講解的，你也可以用到其它的地方，不限于網(wǎng)格)。

?

生成Heatmap

Heatmap 是指從目標點到地圖上每個圖塊的路徑距離。路徑距離不同于歐幾里德距離，它是通過可穿越地形的最短的兩點之間距離來計算。如下圖，你可以看到從目標點（用紅色標記）到地圖任意的點（用粉色標記）的路徑距離和線性距離之間的差異。不可行走的塊以綠色繪制。如圖，路徑距離（以黃色顯示）為9，而線性距離（以淺藍色顯示）約為4.12。每個圖塊左上角的數(shù)字顯示由Heatmap生成算法計算出的到目標的路徑距離。注意兩點之間可能有一個以上的路徑距離, 我們只算最短的那個距離。經(jīng)過算法第一步，我們把地圖上的每個塊到目的地的最短距離都計算了出來，生成了Heatmap。

好今天的流場尋路的內容就分享到這里了，我這邊實現(xiàn)了一個C++版本的流場尋路的代碼，大家可以參考一下，需要的可以私聊我哦