前前言

之前未接觸過游戲開發(fā)但又對其感興趣的朋友，可以參與咱們的網(wǎng)易游戲開發(fā)3天集訓(xùn)營，體驗一次激動人心的游戲開發(fā)過程——提出需求、思考原理、實現(xiàn)功能、定位bug、設(shè)計關(guān)卡、更換美術(shù)資源......麻雀雖小五臟俱全。只需添加如下網(wǎng)易小伙伴聯(lián)系方式（注明B站）就能輕松報名：

（本文作者 @沈琰）

前言

最初是因為偶然看到的視頻（注1）?，對其中游戲的演示涉及的技術(shù)產(chǎn)生了興趣：

對于游戲開發(fā)有些了解的人來說，尋路算法應(yīng)該都不會陌生。但對于類似這種RTS類型游戲里集群尋路的實現(xiàn)方法可能就不是太清楚，這次的目的就是探索其背后的思路和實現(xiàn)方法。

向量場

向量場（vector field）,視頻里也稱之為流場（flow field），有些其他的教程里或者會稱為勢場（potential field），這些說的都是一個概念。至于為什么使用向量場作為基礎(chǔ)，可能基于一個很樸素的想法：

先假設(shè)這么一個場景：RTS游戲中的場景里有成百上千的單位，而你大手一框F2A。 如果是基于之前學(xué)習(xí)的尋路方法，不管是A*還是別的其他尋路算法，那么接下來要做的總歸是每個單位要基于目標(biāo)點在地圖上計算并生成一條路徑，成百上千個單位就是成百上千次計算，這還沒有考慮目標(biāo)是一個移動中的單位，路徑還需要實時更新的情況。此時哪怕使用的尋路算法效率再高，基數(shù)的量級就已經(jīng)擺在那里了，總效率肯定高不起來。 使用向量場尋路的邏輯則是：由目標(biāo)點計算出一個覆蓋整個地圖的全局向量場，每個單位只需要根據(jù)當(dāng)時所在位置的向量走就行，在不考慮其他功能的情況下，效率差不多就是O(1)和O(n)的區(qū)別。

簡而言之，對于多目標(biāo)尋路來說，提高效率的方式可能不再是摳尋路算法的細(xì)節(jié)，而是以減少計算次數(shù)這個思路出發(fā)。使用向量場就是這個目的，相當(dāng)于用一種可以復(fù)用的方式保存了路徑，避免重復(fù)計算。

生成向量場

按照教程（注2）的方法，構(gòu)建向量場分三步：

1. 劃分網(wǎng)格

2. 生成熱力圖（Heatmap）

3. 計算向量

現(xiàn)在按照這個步驟來實現(xiàn)。

構(gòu)建網(wǎng)格

這里網(wǎng)格可以是任意規(guī)則形狀的，如四邊形六邊形之類的，取決于需要，關(guān)鍵是世界坐標(biāo)到網(wǎng)格坐標(biāo)的映射轉(zhuǎn)換正確即可。這里使用用普通的矩形網(wǎng)格。

生成熱力圖

所謂熱力圖，即圖中的每一格都表示到目標(biāo)距離的遠(yuǎn)近程度，換句話說就是DistanceMap，或者CostMap。 具體怎么計算距離，則根據(jù)需要來。

以我們現(xiàn)在的目的為例，一般矩形網(wǎng)格尋路只計算上下左右四個方向，而RTS不是戰(zhàn)棋游戲，路使可以斜著走的，所以相鄰節(jié)點要計算八個方向的距離。接下來遍歷一遍所有格子計算到目標(biāo)的距離，這里可以再加上一個梯度顏色字段，讓單元格根據(jù)距離顯示，使得熱力圖這個名字名副其實。

這里使用廣度優(yōu)先搜索算法（BFS）從目標(biāo)點遍歷所有格子，相應(yīng)的，距離值的計算就直接計算實際距離，也叫歐幾里得距離（注3）?，即正方向的距離加?1 ，斜方向的距離加：

矩形網(wǎng)格的八方向BFS比起一般用的四方向要多注意一個地方：視遍歷周圍單元格的方法不同，可能會有方向的距離計算出錯，需要打個“補丁”。 舉個例子,假設(shè)沿著正右邊順時針遍歷格子：

那么繼續(xù)順著這個邏輯遍歷會有兩處計算錯誤，本該算直線距離的位置會算成兩個斜線距離，因此記得對已訪問的單元格重新計算一次距離，取其中的最小值。

向量計算

接下來根據(jù)距離計算每個格子的向量，這里可以變化的點就很多。

簡單點的想法就是向量指向周圍格子里距離最小的那個，這個方法很適合用BFS生成的距離圖，但對于實際情況來說，相當(dāng)于把偏轉(zhuǎn)的傾向特征抹掉了。

這里我的思路參考這個視頻 [注4]?，用卷積核的方式計算周圍每個相鄰格子的權(quán)重。簡單來說就是：生成八根從當(dāng)前格指向相鄰格的標(biāo)準(zhǔn)化向量，如果把指向最短距離格的向量長度視為 1，那么其他方向的向量的長度就是 1/distance，然后把8跟向量加起來再標(biāo)準(zhǔn)化，這樣做的好處是可以充分考慮到各個方向的距離對整體權(quán)重影響，形成的向量場不再那么“直”，而是有一些弧度。

現(xiàn)在看起來好像沒問題，但在把障礙物加進去后問題會變得更復(fù)雜一些。對于障礙物的格子的處理方法和邊界一樣，即在計算向量時不考慮這個方向上的權(quán)重。

先隨機生成一些障礙物運行看看效果，會發(fā)現(xiàn)下面兩個問題：

1.處于對角的障礙物的計算問題。

嚴(yán)格來說這并不是向量計算的問題，因為權(quán)重是按八方向取的均值，所以計算的時候認(rèn)為斜角有路是理所應(yīng)當(dāng)?shù)?，解決的方法應(yīng)該是不允許生成這樣對角排布的障礙，只要發(fā)現(xiàn)斜對角的障礙物相鄰，那么有一邊整體都算障礙物。

2.與目標(biāo)接近同一直線的情況下的障礙物附近的權(quán)重計算問題：

這個問題的解決思路是把與障礙物相鄰的格子的權(quán)重向量單獨計算，不再按照上面的規(guī)則。因為對于與障礙相鄰的格子來說僅僅是不計算障礙物方向的權(quán)重，影響力是不夠的。最直接的辦法是障礙物邊上的單元格，按之前的方法，量直接指向最小周圍最小距離值的單元格，這也就是視頻[注4] 中最后的優(yōu)化組合算法：

進一步優(yōu)化向量計算

到這里還有優(yōu)化空間，現(xiàn)在的目標(biāo)是希望計算出的向量場在遇到障礙物時稍微避開一些，不要貼著障礙物走。

現(xiàn)在網(wǎng)格圖里計算向量的單元格分成兩類：普通的單元格和障礙物旁邊的單元格。思路是這樣：

對于普通單元格，在發(fā)現(xiàn)其中一個方向的相鄰單元格是在障礙物旁邊的話，可以稍微減少一點這個方向的計算權(quán)重。

對于自身就在障礙物邊上的單元格，可以在發(fā)現(xiàn)相鄰單元格是障礙物時考慮這個方向的權(quán)重，給一個較小的反向的分量。

移動

向量的計算不可能盡善盡美，總會有些瑕疵，比如指向障礙物之類。但是向量的指向并不一定是移動方向，只是在當(dāng)前單元格內(nèi)的傾向于走的方向，換句話說就是力的施加方向。

寫一個簡單的移動腳本，每一幀獲取當(dāng)前腳下單元格的向量作為加速度方向參與速度計算，然后根據(jù)當(dāng)前的速度移動，為防止穿墻，給移動角色加上剛體并在障礙物上加上碰撞盒，效果如圖：

單個的角色移動問題不大，由于向量是作為加速度計算，所以移動軌跡會比較平滑。但直接多角色移動的效果并不好，由于碰撞的存在會使得移動顯得很生硬，但這就不是繼續(xù)優(yōu)化向量計算能解決的問題了。限于篇幅，具體的群體移動邏輯放在下一篇文章。

結(jié)束

現(xiàn)在回過頭從整體來看向量場尋路的優(yōu)缺點：

優(yōu)點是多目標(biāo)尋路時比較節(jié)省計算資源，從這個角度來說，向量場尋路更適合的游戲類型是塔防游戲，只用一次計算就能整場復(fù)用尋路。

缺點則是在地圖比較大的時候，每一次更新向量場信息都要全局更新，會有較高的性能熱點。不過在實際的游戲中會用諸如分塊的方法優(yōu)化這個缺點。

下一期文章我們來研究一下轉(zhuǎn)向行為（steering behaviors），讓向量場導(dǎo)航顯得更生動擬真。

工程地址：https://pan.baidu.com/s/1FbZ5mtE-g9Bfz4pjtQhp9A?pwd=bfdx

注1 ：https://v.youku.com/v_show/id_XMTU0ODM4Njk2.html

注2：https://gamedevelopment.tutsplus.com/tutorials/understanding-goal-based-vector-field-pathfinding--gamedev-9007

注3：https://baike.baidu.com/item/%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%97%E5%BA%A6%E9%87%8F?fromtitle=%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%97%E8%B7%9D%E7%A6%BB&fromid=2701459

注4：https://www.youtube.com/watch?v=ZJZu3zLMYAc