?“游戲單位尋路是一件玩家很少注意到的事情，直到它不能正常工作，然后這個小問題就變成了一個引發(fā)憤怒、世界末日一般的問題?！?/p>

? ? ? ? ? ?---- Patrick Wyatt

一、什么是群體尋路

? 群體尋路通常被描述為在復(fù)雜地形中的多單位集體運動模型，其難點主要是在大規(guī)模的尋路中如何在維持各單位相對獨立性的同時，維護(hù)群體的完整性。

? 大規(guī)模的部隊移動是許多游戲必須面對的一個挑戰(zhàn)，特別是在RTS游戲中，經(jīng)常需要面對幾十上百個單位移動到同一地點的問題。這里面主要需要克服兩個困難：

1. 如何尋路？是整個部隊作為一個整體進(jìn)行尋路，還是各單位獨立尋路？

2. 如何避碰？面對可能導(dǎo)致尋路失敗的單位碰撞、障礙物碰撞，要如何避免？

除此之外，一個尋路系統(tǒng)可能還需要滿足以下幾個要求：

1. 高性能，RTS游戲中的地圖較為復(fù)雜，需要處理的情況更多

2. 拓展性，為游戲其他系統(tǒng)和模塊留足設(shè)計空間

3. 易編輯，方便高層級的Level Design

4. 真實自然，能避開障礙物找到最優(yōu)路線

5. 動態(tài)避碰，當(dāng)?shù)匦伟l(fā)生改變，或者突然出現(xiàn)其他單位的時候，不至于尋路失敗

二、其他游戲的群體尋路

? 尋路系統(tǒng)在業(yè)內(nèi)已經(jīng)有許多比較成熟的解決方案，從早期的基于規(guī)則的方案到近些年的基于算法的方法，下面將簡單的介紹一下。

1. 命令與征服(1995) :單位生成的路徑只考慮從A點到B點的距離，忽略任何障礙物。這使得單位在移動時彼此重疊，在目的地才重新分開。

1. 所有單位每次都會計算一次最短路徑

2. 如果兩個單位在同一條導(dǎo)航路徑上相遇，則會多次改變運動方向，以躲避其他單位

3. 群體尋路時，單位是互相重疊的，只有在抵達(dá)目的地后才會散開

2. 魔獸爭霸1&2 : 地圖是以Tile為基礎(chǔ)設(shè)計的，因此使用A*算法來尋找最優(yōu)路徑，但經(jīng)常會遇到建筑物多占用了額外的Tile，導(dǎo)致尋路有瑕疵的問題。

1. 群體尋路時，若導(dǎo)航路徑上出現(xiàn)了新建筑或其他障礙物，則會導(dǎo)致導(dǎo)航路徑失效

2. 若在移動時，單位撞到了其他東西，則會向左走或向右走，若一段時間后還沒找到就放棄

3. 若在移動時，單位遭受到攻擊（或其他事件）則會離開原有的導(dǎo)航路徑，執(zhí)行其他AI行為

4. 單位之間經(jīng)常發(fā)生碰撞，導(dǎo)致尋路失敗，兩個單位都無法移動

3. 星際爭霸1：該作沿用了魔獸爭霸的引擎，但畫面表現(xiàn)形式又與其不同，因此開發(fā)人員編寫了大量的規(guī)則和設(shè)計了巨大的狀態(tài)機(jī)來實現(xiàn)尋路系統(tǒng)，導(dǎo)致尋路系統(tǒng)性能急劇下降。

1. 群體尋路時，單位探測到前方路徑上有其他單位，會暫時停止移動，等待其他單位移動過去，再繼續(xù)沿著原來的路徑移動。這能有效避免碰撞發(fā)生，但會浪費大量時間

2. 由于星際爭霸1是基于魔獸爭霸引擎開發(fā)的，因此其他方面基本與魔獸爭霸相同

4. 星際爭霸2：使用了 Flocking System with Flow Fields 技術(shù)來實現(xiàn)群體尋路系統(tǒng)，通過計算每個單位的流場來驅(qū)動單位移動，并通過 Flocking Module 來控制單位進(jìn)行避障。

1. 群體尋路時，所有單位不會發(fā)生碰撞，不會發(fā)生重疊，不會突然的停頓

2. 多個群體互相穿插運動時，也能很流暢的進(jìn)行避障，且維持一定的陣型，尋路結(jié)束后，所有群體完整性不會被破壞

三、群體尋路是如何實現(xiàn)的

? 在早期的RTS游戲中，主要以A*算法進(jìn)行尋路，并基于規(guī)則進(jìn)行避障。這種設(shè)計的缺點在于需要耗費大量的計算資源在尋路中，并需要編寫大量的規(guī)則來實現(xiàn)動態(tài)避碰的效果。

?Tile-based algorithm A* (A-Star)

由于尋路算法A*只考慮地形（修改后的A*也可以考慮游戲?qū)ο螅?，它必須由一組規(guī)則來補(bǔ)充，這些規(guī)則根據(jù)游戲及其需要而變化。例如，在《魔獸爭霸2》中，有一條規(guī)則：如果一個單位撞上了其他單位而不能滑過它們，它將重新尋找一條導(dǎo)航路徑。這在少量單位的情況下工作良好，但是當(dāng)試圖在一條狹窄的通道中移動大量的單位時，一些單位不可避免地會撞到他們前面的單位并試圖重新搜索一條路徑。

? 正如所見，這些規(guī)則非常有限。在某些情況下，他們必須犧牲一些更自然的行為來使整個系統(tǒng)正常運作。真正的最短路徑算法會給游戲帶來極大的麻煩，這是游戲設(shè)計者在選擇算法時必須考慮的一個陷阱。針對基于tile的A*算法在處理群體尋路時的局限性，提出了一種基于流場的群集運動系統(tǒng)（the Flocking System with Flow Fields），使群體尋路系統(tǒng)性能進(jìn)一步的優(yōu)化，在避碰效果上更加的自然。

Flow Fields + Flocking (or Swarm) Behavior

? 游戲《星際爭霸2：自由之翼》和《最高指揮官2》以及大多數(shù)現(xiàn)代RTS游戲都使用帶有流場的群集系統(tǒng)來維持對大部隊的流體控制。在每個單元周圍產(chǎn)生局部動態(tài)流場。在調(diào)整群體運動之前，將群體的流場合并在一起。

Pathfinding technique: Flow Fields

? 流場是另一種尋找路徑的方法，這種方法對含有更多單位的群體更有效。流場是一個網(wǎng)格，其中每個網(wǎng)格正方形都有一個方向向量。這個矢量應(yīng)該指向最有效的到達(dá)目的地的方向，同時避開靜態(tài)障礙物。

Movement behavior: Flocking (or Swarm)

? 群集模型是由人工生命和計算機(jī)圖形學(xué)專家克雷格·雷諾茲（Craig Reynolds）定義的。群，根據(jù)定義，是一群一起巡航的鳥。雷諾茲將一般的模擬群集實體稱為“boids”，創(chuàng)建了boids人工生命模擬（1986）。基本的群集模型由三個簡單的轉(zhuǎn)向行為（分離、對齊和內(nèi)聚）組成，這些行為描述了個體boid如何根據(jù)其附近群體的位置和速度移動。因此，群中的實體（或boids）以大致相同的速度巡航，在沒有嚴(yán)格安排的情況下形成一個有凝聚力的群體。

? 該算法可以找到最少數(shù)量的導(dǎo)航節(jié)點，并允許單位自主控制轉(zhuǎn)向行為順利地繞過障礙物及其鄰居。從邏輯上講，每個單位都有傳感器，當(dāng)與另一個單元碰撞時，它會通知第一個單位轉(zhuǎn)向適當(dāng)?shù)姆较蛞员荛_另一個單位。

四、簡單的架構(gòu)設(shè)計

? 一個簡單的群體尋路系統(tǒng)架構(gòu)，通常可分為兩層結(jié)構(gòu)：

• Pathfinding Module: 以 NavMesh & A* 為主的尋路模塊，獲取群體/單位到目標(biāo)位置的導(dǎo)航路徑

• Group Movement Module: 群體移動模塊，管理所有群體，及群體內(nèi)的所有單位，單位在群體中表現(xiàn)出 Flocking Behavior

? 在群體移動模塊中，可通過設(shè)置規(guī)定一個群體是沿著統(tǒng)一的導(dǎo)航路徑進(jìn)行移動，還是各單位以較為松散的方式進(jìn)行移動（但仍維持在同一個群體中）。

? 并且，在群體移動模塊中，可以使用狀態(tài)機(jī)來管理單位的移動，這樣可以為后續(xù)的設(shè)計留下足夠的空間，方便與其他AI系統(tǒng)進(jìn)行交流。

? 通常，可以用一個Group類來管理群體，刪除/添加單位、設(shè)置陣型、設(shè)置群體目標(biāo)等，還可以含有以下屬性：

• 群體在保持一致的情況下可以移動的最大速度：這是由最慢的單位的速度決定的，或者最慢的單位在一個組中移動得更快一些，或者為了追趕而臨時提高速度。

• 群體的質(zhì)心：群體的參考點。

• 群體首領(lǐng)：為群體尋路并決定整個群體走哪條路線的單位。群

• 體陣型：群體中的所有單位以“首領(lǐng)”為中心，維持一定的相對位置

? 一個Units結(jié)構(gòu)體來存儲單位的信息，包括位置、群體信息、陣型信息和各種狀態(tài)等，其中尋路運動狀態(tài)為：

• Wait for path：如果單位有一個有效的目標(biāo)，則會向?qū)ぢ纺K請求一條路徑。

• Follow path：單位從路徑的一個航路點移動到下一個航路點。此狀態(tài)還管理單元的碰撞預(yù)測和避免。

• Goal reached：當(dāng)單位達(dá)到目標(biāo)時，它將進(jìn)入此狀態(tài)。

• Increase waypoint：當(dāng)單位到達(dá)下一個地標(biāo)時，該狀態(tài)用路徑的下一個航路點更新下一個地點。

五、動態(tài)避碰系統(tǒng)

? 解決了群體尋路、單位移動的問題后，還有一個非常重要的問題需要考慮，那就是動態(tài)避碰。一個實用、高性能的動避碰系統(tǒng)可以為游戲體驗增色不少。

? 沒有動態(tài)避碰，單位經(jīng)常會發(fā)生尋路中發(fā)生碰撞導(dǎo)致尋路失敗的情況。通常避碰系統(tǒng)有以下幾種：

• 物理碰撞：當(dāng)單位發(fā)生碰撞時，通過規(guī)則讓單位實現(xiàn)避讓的效果

• 速度避免：在速度空間中計算各單位的實時速度，從中選出在不會導(dǎo)致碰撞發(fā)生的速度，如RVO、ORCA算法

• 群集行為：利用類鳥群算法來模擬群體運動，實現(xiàn)碰撞避免效果

? 當(dāng)然，大多數(shù)情況下只依靠一種算法是很難實現(xiàn)出完美的、自然的避碰效果的。在實際開發(fā)中，通常需要結(jié)合尋路系統(tǒng)和地圖情況來進(jìn)行大量的修改優(yōu)化，比如導(dǎo)航節(jié)點失效問題，運動抖動問題等。

六、總結(jié)

? 游戲中角色的尋路和移動，對玩家來說是同呼吸一樣自然的事情，直到它出現(xiàn)問題。游戲體驗是在一個又一個的微小細(xì)節(jié)當(dāng)中建立起來的。大到一次技能的釋放是否準(zhǔn)確，小到角色的一個轉(zhuǎn)身。玩家總能在設(shè)計者意想不到的地方發(fā)現(xiàn)瑕疵，進(jìn)而產(chǎn)生不滿。對RTS游戲（或涉及到大量單位集體運動的類型）來說，如何實現(xiàn)一個高性能、易擴(kuò)展又自然的群體尋路系統(tǒng)是一件重要又具有挑戰(zhàn)的任務(wù)。從頂層的導(dǎo)航系統(tǒng)，到底層的移動模塊、動態(tài)避碰系統(tǒng)，都需要設(shè)計者和開發(fā)人員花費大量的時間和精力去打磨。

? 本文也只是簡單的介紹了群體尋路系統(tǒng)的一些簡單、通用的設(shè)計，若讀者想要將其用到自己的游戲項目中，還需要閱讀更多的資料，進(jìn)行大量的設(shè)計和測試才行。

七、參考

https://sandruski.github.io/RTS-Group-Movement/

https://zsummer.github.io/2019/06/08/2019-06-08-rvo/

https://gameinstitute.qq.com/community/detail/102644

Reciprocal Collision Avoidance for Multiple Car-like Robots

https://zhuanlan.zhihu.com/p/78873379

https://www.gdcvault.com/play/1021986/Forced-Based-Anticipatory-Collision-Avoidance

https://www.gameres.com/487419.html

https://zhuanlan.zhihu.com/p/88155091

https://wuzhiwei.net/group-path-movement/

https://blog.csdn.net/a1047120490/article/details/105108701

https://indienova.com/indie-game-development/path-finding-algorithm-in-rts/

https://www.shuzhiduo.com/A/q4zVLlvl5K/

http://www.red3d.com/cwr/steer/gdc99/

https://www.gamasutra.com/view/feature/3314/coordinated_unit_movement.php?print=1

Tested Pathfinding

https://github.com/tomascarreras1000/Research-Project-Group-Movement/tree/master/docs