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

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

基于流場(chǎng)尋路的算法的主要步驟

基于流場(chǎng)尋路的算法主要包含以下三個(gè)步驟:

(1) 遍歷游戲地圖種的每個(gè)塊，計(jì)算出來(lái)當(dāng)前塊到目標(biāo)的距離,稱為"Heatmap"熱度圖;

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

(3) 到目的地的每個(gè)角色，都共用這個(gè)向量場(chǎng)來(lái)移動(dòng)導(dǎo)航到目標(biāo)點(diǎn);

生成Heatmap

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

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

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

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

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

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

Vector Field 生成

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

Vector Field 簡(jiǎn)單地存儲(chǔ)了一個(gè)向量，該向量指向每個(gè)地圖塊走向目的地的方向（朝向目標(biāo)）。這里是向量場(chǎng)的可視化，向量從圖塊的中心沿著最短路徑指向目標(biāo),形成了一個(gè)流場(chǎng)。（紅色為原點(diǎn)，白色的線為方向，大體趨勢(shì)都指向目標(biāo)點(diǎn)）。

這個(gè)向量場(chǎng)里面的每個(gè)向量，是通過(guò)Heatmap計(jì)算出來(lái)的，具體的計(jì)算Vector向量方式如下

每個(gè)塊的distance,就是上面Heatmap種計(jì)算出來(lái)的數(shù)值。

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

角色移動(dòng)導(dǎo)航

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

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

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

當(dāng)然把塊分小，計(jì)算量也會(huì)增大。

流場(chǎng)尋路的內(nèi)容就分享到這里了，我這邊實(shí)現(xiàn)了一個(gè)C++版本的流場(chǎng)尋路的代碼