19.1 Introduction

? RVO算法以及衍生算法，如HRVO和ORCA，近年來已經(jīng)成為電子游戲中解決碰撞問題的標準。這是一個了不起的成就：游戲人工智能領(lǐng)域?qū)Υ录夹g(shù)十分謹慎，特別是那些直接從學術(shù)文獻中提取出來的技術(shù)。但是RVO解決了一個業(yè)內(nèi)沒有廣泛共識解決答案的問題。此外，它很容易理解（簡單的幾何推理），易于學習（創(chuàng)造者避開了傳統(tǒng)學術(shù)寫作的晦澀難懂，而且寫得很清楚很好），而且易于實現(xiàn)（創(chuàng)作者免費提供了參考源代碼）。

? 確實的理解它們的工作原理，是十分重要的一件事。這可以通過以下四個步驟來實現(xiàn)：

1. 了解RVO做出的假設(shè)，以及確保它能正常工作所需要的保證（條件）。

2. 認識到這些假設(shè)和保證在實踐中經(jīng)常遭到違反。

3. 弄清楚為什么RVO仍然有效。

4. 把它調(diào)整得更好。

? 在本章的剩余部分，我們將帶你探尋這幾個步驟。我們的目標不是給你一個完美的碰撞避免系統(tǒng)，而是讓你了解VO方法的細微差別，并幫助你迭代開發(fā)一個適合你游戲的避碰系統(tǒng)。不過，首先，簡要介紹RVO和VO方法的歷史。

19.2 History

? VO算法最初是針對可移動機器人開發(fā)出來的，也就是讓現(xiàn)實中的真實物理機器人，在移動時不會互相碰撞。與以前的機器人轉(zhuǎn)向方法相比，VO算法的目的是：

1. 去中心化，每個機器人都有自己的決策，而不是所有的機器人都被一個中央控制器控制。

2. 獨立性，決策完全基于每個機器人對其他機器人位置和速度的觀察。

? 這些特性對游戲開發(fā)人員沒有多大用處，但它們對于理解VO方法的優(yōu)缺點非常重要。VO智能體不顯式地互相通信或協(xié)作。它們之間的合作是一種隨著時間推移而進行的觀察、決策和行動所共同形成的。VO方法避免了多智能體規(guī)劃的困境，而只關(guān)注于單個智能體的行為。但是缺乏協(xié)調(diào)意味著智能體在預(yù)測其他智能體將要執(zhí)行的操作時可能會出錯，從而無法進行適當?shù)暮献鳌?/p>

? 原始的VO方法非常容易遇到這樣的問題，當兩個智能體處在碰撞過程中時，就會發(fā)生速度來回抖動的現(xiàn)象，如圖19.1所示。每個智能體都假設(shè)對方是一個以恒定速度運動的無意識對象，因此當對方改變方向時，會破壞原本的計劃，導致運動方向的反復(fù)變化。

19.2.1 Introducing RVO

? 為了解決抖動問題，RVO算法出現(xiàn)了。這個算法為智能體提供一個決策行為，并假設(shè)另一個智能體也在使用相同的決策行為。在一次碰撞過程中，每個智能體只會朝自己的方向移動一半的距離，并期待其他智能體也會承擔自己的責任朝自己的方向移動另一半距離。本文證明，這將消除錯誤的預(yù)測，并在智能體進入視野后，一步到位地將智能體設(shè)置在最佳無碰撞路徑上。如圖19.2所示。

19.3 Examining RVO’s Guarantees

? 無碰撞運動的證明只適用于一個包含兩個智能體（沒有障礙物）的世界。只有兩個智能體，每個智能體都可以自由選擇最完美的運動速度，而不必躲避其他東西。此外，在世界上沒有其他東西的情況下，每個智能體都可以假定另一個智能體的當前速度也是他們的預(yù)期速度。

? 讓我們加入第三個智能體，看看在圖19.3中會發(fā)生什么。A和B并排向南移動，這時他們看到C向他們走來。

? 此時A會向西面躲避，并認為C會向東躲避。同時B會向東躲避，并認為C會向西躲避。顯然C不能同時做到這兩件事。事實上，這兩件事C都沒有做到，相反它選擇了從A和B的西面進行躲避 （圖中間那種情況）。（對于C來說，躲向東面同樣有效，但是這里假設(shè)它向西走。）

? 現(xiàn)在三個智能體都不開心了。A和C由于都向西躲避而將會碰撞在一起。B雖然不會撞到任何東西，但也偏離了預(yù)期速度。這種情況下，對C來說，最好的選擇是一個朝向正北的移動；它認為向東偏移是可行的，因為A向西偏移了，甚至可能會被往復(fù)運動的B所碰撞到。接著，A決定回到預(yù)期速度的正南方向上，并期待C已經(jīng)朝西走了足夠遠的距離。B也會回到原來的方向上，因為它也認為C已經(jīng)走了足夠遠的距離，不會導致碰撞發(fā)生。

? 簡而言之，在兩幀之后，我們回到了原來的問題。RVO解決了的兩個智能體之間的抖動問題又在三個智能體運動當中出現(xiàn)了。換言之，RVO不能保證在上述情況下避免碰撞，因為對智能體之間的可能速度和預(yù)期速度的看法不一致。

? 理論上在真實的場景中，RVO能在上述情況下避免碰撞，讓C安然的通過A和B。但是，我們看到這種情況沒有發(fā)生，那么到底發(fā)生了什么？

? 好吧，其實在兩幀之后，問題還是有些不一樣的。在這兩個幀上，A和B稍微分開了。C已經(jīng)稍微向西移動，現(xiàn)在正朝北偏西的方向移動（如19.3第三個場景）。在以后的幀中，這些細微的偏移會更加明顯地影響到以后的決策。雖然最初有大量的“抖動”隨著速度的變化而變化，但三者最終還是設(shè)法合作了。

? 事實上，你可以爭辯說，這才是合作應(yīng)該的樣子，每個智能體不僅猜測對方的計劃，而且會在這些計劃不成功時作出反應(yīng)。最終，三者同時做出完全兼容的決策，然后堅持這個決策直到安全的通過。

? 至此，通過完美的預(yù)測來實現(xiàn)完美碰撞避免的嘗試已經(jīng)失敗了。那么，RVO在原始VO上有什么收獲嗎？事實證明，有的。在VO算法下模擬這個場景，這三個智能體將振蕩更長時間。很容易就能構(gòu)建出RVO可以實現(xiàn)但VO不能的場景，但RVO的意義遠不止于此。

? 在圖19.4中，讓我們看一個場景，其中B向北走向A。但是，我們假設(shè)A出現(xiàn)故障，處于停頓狀態(tài)，而不是執(zhí)行正確的回避。

? 這是B完美應(yīng)用VO算法的場景，也許你期待著RVO算法在此種情況下失效，但事實上它仍然很好的完成了工作，實現(xiàn)了AB之間的碰撞避免，即使A出了故障沒有工作。在第一幀，B發(fā)現(xiàn)了A，因此朝自己的方向移動了一半的距離。在第二幀，B又發(fā)現(xiàn)了A，因此又朝自己的方向移動了一半的距離。在接下來的時間里，B不斷重復(fù)執(zhí)行上述決策，直到通過A。在原來的設(shè)計里，B是期待A也同時承擔躲避的責任，但即使A沒有這樣做，B還是能很好的處理這種情況。

? RVO的神奇之處在于，它能在緊急避碰情況和正常避碰情況之間取得平衡。RVO算法下的智能體面對碰撞時會偏離一段距離，但不會太多。不像VO算法會由于偏離太多導致超過預(yù)期速度而需要修正。此外，即使它偏移的距離較短，也仍然是為了彌補未來幀的差異。這種魔力并不是RVO所獨有的：所謂的梯度方法，例如尋找函數(shù)極小值的梯度下降算法，以及類似的技術(shù)，使用乘數(shù)來避免超出目標。

19.4 States, Solutions, and Sidedness

? 任何梯度法的目標都是收斂到一個局部最優(yōu)狀態(tài)，在此狀態(tài)下無法進行進一步的改進。為了避免碰撞，智能體通?？雌饋硐袷窃讵M小的空間中擠過去的。再近一點，它們就會相撞；再遠一些，它們就會浪費時間。

? 不過，RVO并不完全是一種梯度方法。在普通梯度法中，您有盡可能多的步驟來收斂到一個最佳值；您只受處理時間的限制。但是在標準的VO方法中，每次迭代后，智能體都會沿著它們選擇的速度移動。因此，當RVO模擬的“狀態(tài)”是所有智能體的瞬時位置和速度時，“解決方案”是智能體隨時間的全部軌跡。

? 不過，在我看來，有一種更明顯、更有用的方式來思考避碰問題的“解決方案”：Sidedness。兩個相互靠近的智能體可以向左躲閃，也可以向右躲閃；任何一種方式都是潛在的解決方案。如果這兩個方案沒有沖突，那么其中一個可能是更好的解決方案，因為可以更快的抵達目標；但兩者都是穩(wěn)定的：一旦走上其中一條軌道，除非形勢發(fā)生變化，否則智能體不會改變主意。

? 可以從三個方面來定義 Sidedness。所有這些方面都涉及到“最接近”這個概念。假設(shè)有兩個智能體，它們現(xiàn)在的運動軌跡使它們逐漸相互靠近，算出在未來中使A和B最接近的那個時間點（它們之間必須有縫隙），并計算從A的中心到B的中心的向量。

? 第一個概念是絕對的：如果這個向量是朝東的，那么A會從B的西面通過，B會從A的東面通過。用這種方法計算的Sidedness在A的計算和B的計算之間總是對稱的。

? 第二個概念是相對于現(xiàn)時速度的：如果這個最接近向量繞著A相對B的速度離開，則A從左側(cè)通過B，類似地，如果向量向右離開，A從右側(cè)通過B。此計算同樣是對稱的：兩者都將向左偏移，或者都將向右偏移。

? 第三個概念是相對于A的理想速度而言，緊靠最接近向量。這種表述最符合我們對“可通過的一側(cè)”的直覺。但是，在A和B的當前速度與所需速度不同的情況下，這可能會不一致。結(jié)果，Sidedness作為協(xié)調(diào)工具通常使用前兩種表述之一。

19.5 ORCA

? 繼承了原始RVO算法（實現(xiàn)ORCA的參考庫稱為RVO2）的ORCA算法（van den Berg等，2011）以這種sidedness概念為中心。但是，ORCA不太關(guān)注穩(wěn)定性，而更關(guān)注最優(yōu)性。 回顧圖19.3中的三個智能體回避場景，一個主要問題是智能體雙方對避讓策略的看法不一致。

? 如果一個智能體打算從左邊通過，而另一個人則打算從右邊通過，那么沖突是不可避免的。由于ORCA保留了其他VO方法的獨立性，去中心化設(shè)計，因此無法解決同向碰撞問題。取而代之的是，ORCA強迫智能體維持其當前的通行路線。 兩個不在一個精確定義的碰撞路線上的智能體一直在確定可通行路線，即使在它們的路線上沒有足夠的間距來避免碰撞。ORCA以擴大間距的方式來避免碰撞，同時維持行進路線。

?ORCA背后的一個隱含假設(shè)是，當智能體首次遇到對方時，“原始”可通行路線就恰好是可行的。值得注意的是，這種假設(shè)通常是正確的，特別是在沒有靜止障礙物的情況下。當ORCA求解成功時，它將產(chǎn)生一個可靠的合理的最佳碰撞避免路線，并且消除了速度抖動。

? 問題在于ORCA常常求解失敗。盡管一個RVO智能體生成的一組碰撞速度是一個無限錐（排除了大量的潛在速度），但是一個ORCA智能體生成的一組碰撞速度是一個無限的半空間（排除了大約一半）。少部分靠得過近的智能體很容易就排除掉所有速度。實際上，圖19.3的三個智能體問題就可以做到這點。C的行進路線在A的右邊B的左邊；A使C無法向左移動，B使C無法向右移動，并且AB都使C無法直線移動，甚至讓C無法停止或向后移動。ORCA通過解決線性約束來滿足這一要求，這會產(chǎn)生一個能最大化最小通過距離的速度。

? 同RVO的部分規(guī)避一樣，ORCA的約束松弛具有解決多個幀上復(fù)雜的回避場景的效果。雖然A必須求助于“最壞”的解決方案，但B和C都有合法的速度，這會給A留下更多的空間。事實上，ORCA在一幀內(nèi)就解決了這個問題，因為a的“最差”速度實際上是正北。更一般地說，當兩排朝不同方向前進的智能體相遇時，ORCA的作用是擴大行距，從最外層開始。RVO也這樣做，但ORCA禁止中層在發(fā)生這種情況時采取極端的規(guī)避行動，因此，通過保持原有的可通行路線設(shè)置，從而獲得更簡潔、更優(yōu)的解決方案。

19.6 Cornering

? ORCA在現(xiàn)實世界中表現(xiàn)出更嚴重的問題。在大多數(shù)關(guān)于VO方法的文章中，都假設(shè)每個智能體都有一個預(yù)期的移動方向，要么是恒定的，要么是直接朝向一個固定的目標點。但在大多數(shù)比賽中，行進的方向是通過沿著一條通向目標的路徑來確定的，這條路徑繞著拐角旋轉(zhuǎn)。

? VO方法可以適應(yīng)航向偶爾的變化，沒有太大問題。但在轉(zhuǎn)彎時，智能體的預(yù)期的移動方向每一幀都會改變。

這違反了前面提到的假設(shè)，即每個智能體上一幀的速度是當前幀的預(yù)期速度。RVO智能體在轉(zhuǎn)彎時或?qū)Ω浇闹悄荏w進行反應(yīng)時會出現(xiàn)異常的軌跡，也就是說，當智能體改變通行路線時，會出現(xiàn)一個獨特的“急轉(zhuǎn)彎”現(xiàn)象。

? 但ORCA不允許這樣的“突然”。如前所述，原始的通行路線通常是最理想的路線的近似值，但在拐彎的時候并非如此。ORCA智能體在拐角處通常會移動得更遠一些，遠離期望路線來保持通行路線，或者只是被卡在角落里，不愿意繼續(xù)前進也無法做出其他決策。當所有智能體朝著同一個目標前進時，這種行為有時是可以接受的，因為前端智能體仍然可以繼續(xù)前進，但通常會導致頻繁的死鎖。

19.7 Gradient Methods Revisited

? 我們想從碰撞避免中得到的是讓智能體快速找到一組通行路線，并且理想情況下該解決方案不會偏離最優(yōu)值太多。當出現(xiàn)一個新智能體，或當前智能體改變了決策時，我們希望系統(tǒng)能夠快速適應(yīng)并找到新的解決方案，并使新的解決方案看起來盡可能像舊的解決方案。關(guān)鍵在于權(quán)重。

19.7.1 Modifying Weights

? 在原始的RVO論文中，可以給智能體“賦權(quán)”，只要兩個權(quán)重加起來等于1，并且兩個智能體都同意這些權(quán)重是多少，那么一個智能體可以比另一個智能體多移動幾個百分點或少移動幾個百分點（兩個智能體整體需要移動的總距離）。但是，如果我們將RVO視為一種梯度方法，而不是一個即時的、完美的碰撞解答器，那么，很明顯，沒有什么能強制這種約束。例如，你可以將這兩個權(quán)重都設(shè)置為0.1，使智能體在多數(shù)幀上緩慢地移動?；蛘呖梢詫蓚€權(quán)重都設(shè)置為0.9，使智能體快速閃避，表現(xiàn)出RVO為了避免抖動而做出的設(shè)計（事實上，原始VO可以視作RVO的一個特例，即所有權(quán)重都設(shè)置為1）。

? 如前所述，RVO不完全是一種梯度方法，因為智能體在每次迭代后都會移動。除此之外，如果即將發(fā)生的碰撞還沒有得到解決，每接近一點問題都會更難一些。如果兩個智能體處在碰撞過程中，且他們之間的權(quán)重之和小于1，那么它們每幀的決策都不可能完全解決碰撞問題，并最終使他們發(fā)生碰撞。如果一個算法有恐慌的時候，那么這種情況就是算法恐慌時的樣子。

? 不過，低權(quán)重也有其優(yōu)勢。它們傾向于得到更好的解決方案，特別是對于大量的智能體。但我們需要一種方法來應(yīng)對他們逐漸失敗的趨勢。

19.7.2 Substepping

? 回想一下，作為一種機器人控制算法，RVO依賴于一個轉(zhuǎn)向、移動和觀察的循環(huán)。一個機器人不能對另一個機器人作出反應(yīng)，直到另一個機器人真正轉(zhuǎn)向并開始朝另一個方向移動。但有一個好處是即使不移動智能體，我們也可以在每次轉(zhuǎn)向步驟后立即知道所有智能體的速度。我們可以利用這些知識來作弊，在每個動作步驟之間運行RVO的多次迭代。一個RVO子步驟的速度輸出成為下一個子步驟的速度輸入，且位置保持不變。

? 這有很多優(yōu)點，當多組智能體突然遇到彼此時，很可能會有許多幀出現(xiàn)速度抖動的現(xiàn)象，如前面所述。子步驟會讓抖動在速度被呈現(xiàn)給動畫系統(tǒng)之前消失，這會給人一種錯覺，認為所有的智能體都在第一時間做出了一致的選擇。

? 子步驟還可以讓設(shè)置權(quán)重更靈活，權(quán)重總和小于1無法解決碰撞問題，但他們善于找到有效解決辦法的種子。在由許多子步驟組成的步驟中，可以從低權(quán)重開始平滑地尋找有效解決方案，然后將權(quán)重增加到0.5來沿著無碰撞路線融入到該解決方案中。

? 如果你熟悉隨機優(yōu)化方法，你可能會發(fā)現(xiàn)，這種從保守到突然的計劃是違背直覺和倒退的。然而，這里的目標是可靠地收斂到滿足局部最優(yōu)的約束，而不是在保持約束的同時可靠地收斂到全局最優(yōu)。

19.7.3 Time Horizons

? ORCA的轉(zhuǎn)彎問題（卡住而不是改變路線）是當恒定預(yù)期速度的假設(shè)被違反時，VO方法展示出來的一個更大類問題的例子。另一個更簡單的形式可以用一個VO智能體向北移動到一個目標點來演示（后面有一堵墻）。所有向北的速度都被墻壁上的靜態(tài)速度障礙物所阻擋，因此無法到達目標。

? 原始的RVO開源庫不存在這個問題，因為它沒有完全按照論文來實現(xiàn)，并且如果它們超出了最大停止距離就忽略與靜態(tài)障礙物的碰撞。其他RVO實現(xiàn)通過定義最大碰撞時間（TTC）來解決此問題，超過該時間的碰撞將被忽略，這會使智能體在接近障礙物時速度減慢，使其TTC保持在閾值以上。第一種方法假設(shè)未來的決策將停止；第二種方法假設(shè)超過最大TTC的軌跡太不可預(yù)測，不納入考慮。這兩種方法都是合理的，但都是相當武斷的，當智能體最終擠在靜態(tài)障礙物和其他智能體之間時，可能會導致碰撞。

? 無論時在轉(zhuǎn)彎還是接近墻前面的目標，基本的問題是智能體試圖避免在他們永遠無法到達的地點發(fā)生碰撞。轉(zhuǎn)彎智能體將在到達碰撞點之前就會轉(zhuǎn)向，接近目標的智能體會先停下來。

? 那么，一個更正式的方法是計算智能體計劃在其目標處停止或轉(zhuǎn)彎的時間，并避開一定會在這段時間之后發(fā)生的碰撞。時間范圍特定于給定的速度候選。

? 時間范圍在拐彎時有點棘手，因為智能體不打算在在那之后消失不見，而只是稍微轉(zhuǎn)一轉(zhuǎn)。一個正在轉(zhuǎn)彎的智能體的時間范圍接近于零，但不應(yīng)完全忽略碰撞。相反，你可以構(gòu)建一個平面，垂直于智能體的后轉(zhuǎn)彎方向，這個智能體從未打算穿過這個平面。如圖19.6所示，經(jīng)過該平面的碰撞可以被安全的丟棄。

? 這并不是一個完美的解決方案，因為智能體仍然沒有考慮到轉(zhuǎn)彎后會發(fā)生的碰撞。而且，智能體并非永遠不會越過它們的轉(zhuǎn)彎平面：有時它們這樣做是為了避免在拐角處發(fā)生碰撞。一個更好的解決方案是由智能體的路線定義的空間中預(yù)測碰撞，而不是世界空間。但是，由于每個智能體都有自己的路徑，在一般情況下，以一種能夠確?？梢缘玫筋A(yù)期結(jié)果的方式來做這件事是很難做到的。

19.8 Progress and Penalties

? 原始的VO算法將避免碰撞視作第一要務(wù)，而沿著預(yù)期方向移動則是次要的，僅當在一組非碰撞且因此有效的軌跡中進行選擇時才起作用。但正如我們所看到的，避免遠距離碰撞并不總是必要的或合理的：在當前步驟和預(yù)計的碰撞之間，會發(fā)生很多事情，特別是當涉及到許多智能體時。

? RVO算法弱化了VO算法的約束，當評選候選速度時只將預(yù)計碰撞視作需要考慮的一個方面，因此讓RVO算法成為一種實用方法。（ORCA不會以同樣的方式弱化其約束：其約束松弛是為了產(chǎn)生至少一個允許的速度，而不允許在非碰撞速度可用的情況下選擇碰撞速度。）

? 候選速度的一個基本作用是用來計算預(yù)期速度和候選速度之間的距離。預(yù)測碰撞被視作懲罰項，降低候選速度的作用，且懲罰項會隨著碰撞越加接近而增加。如果預(yù)測一個候選速度將導致多個碰撞，則可以使用最快發(fā)生的碰撞來確定懲罰，或者每個碰撞可以生成一個單獨的懲罰項；后一種方法傾向于將智能體從人群中推離，從而減少擁塞。

?上面這樣的附加公式是由實用性而不是理論驅(qū)動的：它不能保證避免碰撞，并且增加了用戶指定參數(shù)的數(shù)量，這使得調(diào)整變得更加困難。然而，在實踐中，它比純粹的VO算法在消除擁塞方面更有效，因為它不考慮遙遠的碰撞，使它對近距離的碰撞反應(yīng)更強烈。

19.8.1 Putting Sidedness Back In

? 加法公式不會自動保持側(cè)性（盡管使用了子步驟的方法來幫助）。然而，沒有什么能阻止我們把它作為一個額外的懲罰條款。簡單地計算一下，對于每一個候選速度，它改變了多少個智能體，然后為每個代理添加一個懲罰。側(cè)性變化懲罰項的比例應(yīng)該類似于碰撞懲罰項；因為有時需要將它們應(yīng)用于沒有預(yù)測碰撞的智能體，但是，可以使用最接近時間法代替TTC法。

19.8.2 Progress and Energy Minimization

? 在上面的加法公式中，候選速度的基本作用被計算為與預(yù)期速度的距離。

這不是唯一的選擇：另一個選擇是進展比率。在這個公式中，主要的度量是一個智能體朝著它們的目標前進的速度，計算為候選速度與單位長度的預(yù)期移動方向的點積。與距離指標相比，進展比率鼓勵側(cè)方躲避而不是放緩速度，并傾向于讓智能體更快地達成目標。

? 從人類實際行為的角度來看，進展比率是一種不切實際的效用。想想看，當從一個地方移動到另一個地方時，人類可以選擇短跑，但通常以步行速度移動。生物力學研究人員解釋說，這是一種能量最小化的趨勢：正常的步行步態(tài)通過最大化速度與功率輸出的比率，使人類以最小的能量消耗達到目標。

以非預(yù)期速度移動所浪費的能量的粗略近似值，可由預(yù)期速度和候選速度之間的平方距離計算出來；平方項將其與RVO方法區(qū)分開來。使用此公式進行計算的智能體顯示出類似人類的軌跡，通常稍微減速以避免碰撞，而不是向左或向右轉(zhuǎn)彎。

19.9 Putting It All Together: How to Develop a Practical Collision Avoidance System

? 對基于VO的避碰系統(tǒng)中涉及的所有細微差別、決策和參數(shù)都有透徹的了解，并不能自動讓你有能力做出完美的碰撞避免系統(tǒng)。我們深信，沒有完美的避免碰撞系統(tǒng)，只有一個能很好地配合您的場景、需求和動畫系統(tǒng)的系統(tǒng)。開發(fā)這樣一個系統(tǒng)，就像開發(fā)游戲系統(tǒng)一樣，是一個迭代過程。為了提高流程的有效性，您可以做一些重要的事情：

• 建立一個碰撞避免場景庫，涵蓋系統(tǒng)需要處理的各種情況。這些應(yīng)該包括游戲中可能遇到的所有因素：靜態(tài)障礙、轉(zhuǎn)彎、多組智能體等等。當您遇到系統(tǒng)問題時，請創(chuàng)建新的場景來重現(xiàn)問題，并測試對系統(tǒng)的更改是否已解決這些問題。

• 建立一個碰撞避免算法庫！當你做出改變時——無論是對使用中的基本算法還是參數(shù)的值——保留舊算法，不僅僅是在源代碼控制中，而且是在實際運行代碼中。這將允許您評估您的迭代更改在多大程度上改善了碰撞避免質(zhì)量，并允許您測試解決特定問題的多種方法。通常，以后對系統(tǒng)的調(diào)整會使早期的調(diào)整變得不必要，保留早期版本可以幫助您識別并刪除它們，從而使您的系統(tǒng)盡可能簡單。

• 寫一個框架，針對每個碰撞避免場景自動測試每個避碰算法。這并不像聽起來那么簡單：很難制定標準來確定某個特定算法是否“通過”特定的測試。作為第一步，您可以簡單地檢查一個算法是否最終成功地將所有智能體都帶到它們的目標，而不會在路上發(fā)生碰撞。您可以比較兩種算法，以確定哪種算法能更快地讓智能體到達目標，但請記住，在游戲場景中，幾秒鐘的差異并不顯著。不要孤立地測試碰撞避免，這一點很重要：如果碰撞避免輸入到動畫系統(tǒng)中，而不是直接控制代理位置，則必須使動畫系統(tǒng)成為測試臺的一部分，以確保結(jié)果準確。自動測試平臺主要用于快速檢查一個或多個測試場景中的顯著回歸。它還可以用來快速確定一組控制參數(shù)的最佳值。

• 不要過于依賴你的自動化測試工具，需經(jīng)常親自查看測試結(jié)果。一些避免碰撞的算法可能會出現(xiàn)偽像，這些偽像不會顯著影響結(jié)果的客觀最優(yōu)性，但是對于玩家來說，這看起來是不真實的；速度抖動就是一個很好的例子。你可以試著提出一些測試，但是主觀評價是無法替代的。

19.10 Conclusion

? VO算法之所以流行，是因為它將碰撞避免轉(zhuǎn)化為速度空間中的問題，這使得解決問題變得簡單起來。特別是RVO算法提出的讓多個智能體分擔碰撞避免的責任的方法。但是VO算法尤其是RVO算法在實踐中的成功依賴于更微妙的因素，將RVO視為一種純幾何方法，使得利用這些因素并使其最大化變得更加困難。因此，通過多個方面來觀察VO算法是很重要的：作為幾何解析器，作為梯度方法，作為實用方法。這種整體方法并不是一件簡單的事，但碰撞避免并不是一個簡單的問題。理解問題空間的細微差別和解決方案空間的復(fù)雜性是開發(fā)適合您的系統(tǒng)的關(guān)鍵。

References

• van den Berg, J., Guy, S. J., Lin, M., and Manocha, D. 2011. Reciprocal n-body collision avoidance. In Robotics Research. Berlin, Germany: Springer, pp. 3–19.

• van den Berg, J., Lin, M., and Manocha, D. 2008. Reciprocal velocity obstacles for real-time multi-agent navigation. Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), 2008. http://gamma.cs.unc.edu/RVO/icra2008.pdf.

??

文章來源：http://www.gameaipro.com/???

?如侵犯版權(quán)，請聯(lián)系譯者刪除。???

?讀者若需要轉(zhuǎn)載，請注明出處。? ??

若有錯誤，歡迎指正。