影子跟随算法
動作類游戲如何在高延遲下實現同步？不同的客戶端網絡情況，如何實現延遲補償？十年前開始關注該問題，轉眼十年已過，看到大家還在問這類問題，舊文一篇，略作補充（關于游戲同步相關問題還可以見我寫于2005年的另外兩篇文章，幀鎖定算法?和?網游同步法則）：
影子跟隨算法由普通DR（dead reckoning）算法發展而來，我將其稱為“影子跟隨”意再表示算法同步策略的主要思想：
1． 屏幕上現實的實體（entity）只是不停的追逐它的“影子”（shadow）。
2． 服務器向各客戶端發送各個影子的狀態改變（坐標，方向，速度，時間）。
3． 各個客戶端收到以后按照當前重新插值修正影子狀態。
4． 影子狀態是跳變的，但實體追趕影子是連續的，故整個過程是平滑的。
圖1?算法演示
前面的1號終端控制紅色飛船P1向左飛，并把自己的狀態時時告訴服務器
后面的2號終端上接收到飛船P1的影子S1的狀態（向左移動），并讓P1的實體追趕S1
網絡性能指標一：帶寬，限制了實時游戲的人數容量
網絡性能指標二：延時，決定了實時游戲的最低反應時間
?
使用該算法可以容易的開發出一款馬里奧賽車，或者Counter Strike，詳細說明見后：
?
算法比較：
?
1． 幀間同步：不同客戶端每幀顯示相同的內容，鍵盤/時鐘數據傳到服務器，服務器確認后所有終端做出響應，多用于局域網游戲，比如紅警（需要等待客戶端），街霸II的網絡版（360），網速要求高，復雜度低。參考以及 LockStep和TimeWrap算法，以及我2007年舊文?幀鎖定算法。
2． 插值同步：不同客戶端顯示不同步，但是狀態同步，常見的Dead Reckoning（或叫導航插值），效果好，但復雜度高。常見于競速類游戲和 FPS游戲。
?
算法定義：
?
1． 時間：以貞為單位（FPS=10），一開始由服務器告訴向所有客戶端，每5分鐘同步。
2． 玩家：每個玩家控制自己的實體，并在每貞將狀態改變告知服務器。
3． 狀態：狀態數據 = 實體ID + 坐標 + 方向 + 速度 + 時間（貞）。
4． 插值：收到新狀態包后將根據其運動方向與時間，根據現有時間計算當前的新狀態。
5． 跟隨：實體不停的追蹤自己的影子，追上后與影子保持狀態同步。
?
相位滯后：可選參數，實體與影子保持一定距離同步，相當于保持一定車距，這樣在控制者突然停止的時候，不容易因為網絡延遲跑過了又被拉回來。
慣性移動：可選參數，開始移動或者停止或者改變方向都有加速度，這樣就不需相位滯后了。
?
每次服務器向各個客戶端同步時間的時候，由于延遲，所有客戶端的時間都是慢于服務器的，這沒有關系，只要大家在一定誤差范圍內以相同的速度增加，就完全沒有問題。
圖2 IDC網絡響應
?
在公網平均130ms的Latency下，是不存在“完全的”的同步情況。如何通過消除/隱藏延時，將用戶帶入快速的交互式實時游戲中，體驗完美的互動娛樂呢？
讓所有的用戶屏幕上面表現出完全不同的表象是完全沒有問題的；
把這些完全不同表象完全柔和在一個統一的邏輯中也是完全沒有問題的。
需要根據具體情況，分清楚哪些我們可以努力，哪些我們不值得努力，弄明白實時游戲中同步問題關鍵之所在，巧妙的化解與規避游戲，最終在適合普遍用戶網絡環境中(200ms)，實現實時快速互動游戲。
?
案例解析：Counter Strike
?
實現CS的話，首先我們需要給人物移動加上慣性，比如靜止狀態突然開始移動，那么需要0.5-1秒的加速過程，而移動中突然停止也需要0.5-1秒的減速過程，這樣就實現了無差別同步，不需要相位滯后來避免拉扯影響用戶感。
同時開槍射擊采用客戶端判斷，也就是說如果我看見你在墻前面，開槍射中，那么我向服務器發送“我擊中你了”，這時有可能真實的你在墻后，那么表現出來的就是我看見我打中你了（減不減血由服務段判斷），而你沒有看見我，覺得我穿墻打中你了。
圖3?CS的同步邏輯
關鍵狀態進行緩存，不然如果別人向前連續跳五次，每次取得狀態都取到最高點的話，別人客戶端上的影子和跟隨的實體會奇怪的持續的飛在天上，所以需要將起跳和落地這兩個關鍵狀態緩存，實體追趕時只有追上的第一個狀態（一號影子）才能追逐第二個狀態（二號影子）。
由此可以在完全時間同步的情況下平滑的跑動、跳躍，開槍射擊采用客戶端判斷后手感得到提高，唯一需要擔心的就是外掛，外掛多是實時游戲的代價，只能通過Cheating Death等工具防止了。
?
案例解析：馬里奧賽車
?
用該算法實現馬里奧賽車是很簡單的，影子和實體都使用慣性，由于賽車慣性很大，不容易有突變的狀態更新，所以效果會比FPS游戲更好。
玩家碰到道具后，馬上在屏幕上隱藏該道具的顯示并通知服務器，由服務器決斷道具屬誰，由于剛碰到道具就隱藏所以不會有碰到道具卻在一段時間內無法取得延遲現象。
游戲道具系統實現也很容易，比如那個將當前第一名炸毀的道具，它的描述是：原角色+對象角色+約定發生時間。既然知道對象是誰，什么時間發生，那就更本不需要怎么同步了，所有客戶端和服務器在該時間讓炸彈爆炸就得了，這種手法類似即時戰略游戲。
游戲還有一類道具是可以發射的烏龜殼，這個東西屬于有彈道的發射物，類似Quake里面的某些武器，需要作一些同步處理，基本特性是服務器判斷起決定作用，客戶端同步判斷，如果客戶端與服務器都判斷集中，那就集中；如果客戶端判斷集中而服務器判斷沒有集中，那會看到該角色似乎被打了一下，但很快又恢復了速度向前沖。
由于賽車本身就具備慣性比較大的特點，因此同步效果是比較好的，可以在更大的延遲情況下表現得和FPS差不多（比如300ms效果相當于FPS的200ms）。
?
非可靠包：
?
該“影子跟隨算法”支持非可靠傳輸協議，如果使用非可靠傳輸，那么我們按照特定頻率（如每秒10次）定時發送狀態更新，因為協議中每個更新包出了位置外還有速度、方向和時間，甚至還能加速加速度，因此我們丟一個包沒有關系，可以根據后來的包重新計算插值。只有關鍵狀態更新時才需要可靠傳輸，這就避免了TCP中丟包時RTO指數增長造成的延遲了。
?
負面情況：
?
該算法缺點就是無法向“幀間同步”算法那樣，每次發送按鍵給服務器，服務器處理后再反饋結果，在局域網中（平均延遲<5ms），這樣的效果相當于單機游戲一樣即時，游戲性也能很復雜。然而在Internet中（平均延遲130ms，設計基準200ms，每秒最多發送10個數據包）該算法卻不能像單機游戲那樣有復雜的場景互動，有類似格斗游戲的即時的動作判定。
許多策劃在設計實時動作游戲時很多設計我們都難以實現，這樣因為策劃不容易明白哪些我們能做，哪些我們不能做。即便程序員精通同步理論，策劃也經常碰壁。
當多數設計被程序員回復“無法實現”后，策劃只有采取一種消極設計（砍掉很多有意思的互動元素），于是網絡游戲的表現力到今天還是差單機游戲一大截。
這些問題也并不能因為“影子跟隨算法”的提出而得到改進，大于100ms的判定時間，都很難做到即時。
最后，該算法編碼復雜度比其他同步策略高，因為服務器需要計算一份影子數據，各個客戶端需要計算一份影子數據，還需要計算實體追趕，而這三種計算都需要在同樣的時鐘下保持一致，這就增加了編碼與調試的復雜度。
?
總結話題：
?
Internet特點是“高帶寬，高延遲”，可以說從本質上Internet就不是為了游戲而設計的。故此Internet絕對意義的同步是不存在的?！坝白痈S算法”的核心思想有幾個：時鐘同步，客戶端先行，平滑追趕。通過這三個特性，我們能夠在近似時間同步的情況下，模擬各種物體的移動過程，而使用該算法的前提是設計者需要根據各個游戲的特性研究不同的優化技巧，策略因游戲而變。
比如發送狀態更新包時，不需要每次都發送，而可以只發送改變的狀態。什么時候我們覺得改變了？就是當客戶端實體與自己的影子之間的誤差大于某特定數值時我們才發送更新包，這樣雖然玩家在原地做左右搖擺的小幅度移動，只要沒有超出范圍，都不需要發送新的狀態更新，其他玩家機器上看起來，它是站著不動的。
比如當發現某客戶端5秒鐘沒有相應了，那么就將該人物的影子凍結住，永遠不要為了等待某個數據而不讓游戲進行下去。
本算法需要客戶端與服務器維護相同的時鐘，當每5分鐘同步的時候，直接根據服務器的時鐘替換當前時鐘就行了，不需要重新計算所有影子的位置，因為后續的狀態數據將會馬上刷新這些狀態。更不需要將測量到的PING值考慮進去，該算法與PING具體值無關。
當發現策劃案子不可行時，尋找近似替代方案，比如減少“一次性的”“決定性的”事件發生，比如延長導彈在空中飛行的時間，比如將敵人加入HP分多次打死，而不是以及斃命，等等，都是大家可以發揮想象的地方。
轉載于:https://www.cnblogs.com/huwenya/p/10599205.html
總結
- 上一篇： mac环境变量
- 下一篇： 微信小程序设置启动图时出现滚动条