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

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

基于流場尋路的算法的主要步驟

基于流場尋路的算法主要包含以下三個步驟:

(1) 遍歷游戲地圖種的每個塊，計算出來當前塊到目標的距離,稱為"Heatmap"熱度圖;

(2) 為每個地圖塊，根據(jù)Heatmap生成一個向量場,指定了每個塊到目標的方向 稱為"Vector Field";

(3) 到目的地的每個角色，都共用這個向量場來移動導(dǎo)航到目標點;

生成Heatmap

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

Heatmap生成算法是一種 wavefront 算法。它從值為0的目標開始，然后向外流動以填充整個可遍歷區(qū)域。 wavefront 算法有兩個步驟：

(1)從目標開始，并用0的路徑距離標記它。

(2)獲取每個標記的圖塊的未標記鄰居，并用前一個圖塊的路徑距離+1標記它們。

(3) 標記完所有地圖的塊后，算法結(jié)束。

注: wavefront 算法是在網(wǎng)格上執(zhí)行廣度優(yōu)先搜索，并存儲沿途到達每個塊所需的步驟。這種算法有時也稱為brushfire算法。

Vector Field 生成

現(xiàn)在已經(jīng)計算了從每個塊到目標的路徑距離，我們可以很容易地確定接近目標需要采取的路徑。通常計算一次Vector Filed，然后讓所有要尋路的對象在運行時引用該Vector Filed。

Vector Field 簡單地存儲了一個向量，該向量指向每個地圖塊走向目的地的方向（朝向目標）。這里是向量場的可視化，向量從圖塊的中心沿著最短路徑指向目標,形成了一個流場。（紅色為原點，白色的線為方向，大體趨勢都指向目標點）。

這個向量場里面的每個向量，是通過Heatmap計算出來的，具體的計算Vector向量方式如下:

Vector.x = left_tile.distance - right_tile.distance, 向量x為左邊的塊-右邊的塊;

Vector.y = up_tile.distance - down_tile.distance,向量y為上邊的塊-下面的塊;

每個塊的distance,就是上面Heatmap種計算出來的數(shù)值。

如果當前塊的（左/右/上/下）不可行走(障礙物等)，則使用與當前塊的距離來代替缺少的值。一旦粗略計算了路徑向量，就對其進行歸一化，以避免以后出現(xiàn)不一致。

角色移動導(dǎo)航

現(xiàn)在矢量場已經(jīng)計算出來了，計算探路者的運動就很容易了。假設(shè)vector_field（x，y）返回我們之前在tile（x，y）處計算的向量，并且移動速度大小一直，則計算tile（x，y）處移動速度的偽代碼如下所示：

velocity_vector = vector_field(x, y) * desired_velocity

當我們導(dǎo)航的時候，只要沿著向量方向移動就可以了,很容易就實現(xiàn)了流場移動, 同時多個角色目標尋路的時候，只要計算一次。

如上圖，紫色的點，水平不可以移動，上下兩個塊的距離都是一樣的，這樣就導(dǎo)致了不唯一性，一半這種情況，我們會隨機選著一個方向，這樣導(dǎo)致的結(jié)果可能就是我們選擇的路徑不一定是最短的，所以流場尋路又是基于局部最優(yōu)解的。要解決這樣的問題，還有一個好的方法，就是把塊分小，降低這樣的幾率。

當然把塊分小，計算量也會增大。

好今天的流場尋路的內(nèi)容就分享到這里了

更多教學資料：https://bycwedu.vipwan.cn/promotion_channels/829468798