網游同步算法之導航推測（Dead Reckoning）算法：

　　在了解該算法前，我們先來談談該算法的一些背景資料。大家都知道，在網絡傳輸的時候，延遲現象是很普遍的，而在基于Server/Client結構下的網絡游戲的同步也就成了很頭疼的問題，在保證客戶端響應用戶本地指令流暢的情況下，沒法有效的保證的同步的及時性。同樣，在軍方也有類似的事情發生，即使是同一LAN里面的機器，也會因為傳輸的延遲，導致一些運算的失誤，介于此，美國國防部投入了大量的資金用于研究一種比較的好的方案來解決分布式系統中的延遲問題，特別是一個叫分布式模擬運動（Distributed Interactive Simulation）的系統，這套系統呢，其中就提出了一套號稱是Latency Hiding & Bandwidth Reduction的方案，命名為Dead Reckoning。呵呵，來頭很大吧，恩，那么我們下面就來看看這套系統的一些觀點，以及我們如何把它運用到我們的網絡游戲的同步中。

　　首先，這套同步方案是基于我那篇《網絡游戲的同步》一文中的Mutual Synchronization同步方案的，也就是說，它并不是Server/Client結構的，而是基于客戶端之間的同步的。下面我們先來說一些本文中將用到的名詞概念：
　　網狀網絡：客戶端之間構成的網絡
　　節點：網狀網絡中的每個客戶端
　　極限誤差：進行同步的時候可能產生的誤差的極值

　　恩，在探討其原理的之前，我們先來看看我們需要一個什么樣的環境。首先，需要一個網狀網絡，網狀網絡如何構成呢？當有新節點進入的時候，通知該網絡里面的所有節點，各節點為該客戶端在本地創建一個副本，登出的時候，則通知所有節點銷毀本地關于該節點的副本。然后每個節點該保存一些什么數據呢？首先有一個很重要的包需要保存，叫做協議數據包（PDU Protocol Data Unit），PDU包含節點的一些相關的運動信息，比如當前位置，速度，運動方向，或者還有加速度等一些信息。除PDU之外，還有其他信息需要保存，比如說節點客戶端人物的HP，MP之類的。然后，保證每個節點在最少8秒之內要向其它節點廣播一次PDU信息。最后，設置一個極限誤差值。到此，其環境就算搭建完成了。下面，我們就來看看相關的具體算法：

　　假設在節點A有一個小人（路人甲），開始跑路了，這個時候，就像所有的節點廣播一次他的PDU信息，包括：速度（S），方向（O），加速度（A）。那么所有的節點就開始模擬路人甲的運動軌跡和路線，包括節點A本身（這點很重要），同時，路人甲在某某玩家的控制下，會不時的改變一下方向，讓其跑路的路線變得不是那么正規。在跑路的過程中，節點A有一個值在不停的記錄著其真實坐標和在后臺模擬運動的坐標的差值，當差值大于極限誤差的時候，則計算出當前的速度S，方向O和速度A（算法將在后面介紹），并廣播給網絡中其他所有節點。其他節點在收到這條消息之后呢，就可以用一些很平滑的移動把路人甲拉扯過去，然后重新調整模擬跑路的數據，讓其繼續在后臺模擬跑路。

　　很顯然，如果極限誤差定義得大了，其他節點看到的偏差就會過大，如果極限偏差定義得小了，網絡帶寬就會增大。如果定義這個極限誤差，就該根據各種數據的重要性來設計了。如果是回合制的網絡游戲，那么在走路上把極限誤差定義得大些無所謂，可以減少帶寬。但是如果是及時打斗的網絡游戲，那么就得把極限誤差定義得小一些，否則會出現某人看到某人老遠把自己給砍死的情況。

　　Dead Reckoning的主要算法有9種，但是只有兩種是解決主要問題的，其他的基本上只是針對不同的坐標系的一些不同的算法，這里就不一一介紹了。好，那么我們下面來看傳說中的最主要的兩種算法：
　　　　第一：目標點 = 原點 + 速度 * 時間差
　　　　第二：目標點 = 原點 + 速度 * 時間差 + 1/2 * 加速度 * 時間差
呵呵，傳說中的算法都是很經典的，雖然我們早在初中物理的時候就學過。

　　該算法的好處呢，正如它開始所說的，Latency Hiding & Bandwidth Reduction，從原則上解決了網絡延遲導致的不同步的問題，并且有效的減少了帶寬，不好的地方就是該算法基本上只能使用于移動中的同步，當然，移動的同步是網絡游戲中同步的最大的問題。

　　該方法結合我在《網絡游戲的同步》一文中提出的綜合同步法的構架可以基本上解決掉網絡游戲中走路同步的問題。相關問題歡迎大家一起討論。

有關導航推測算法（Dead Reckoning）中的平滑處理：

　　根據我上篇文章所介紹的，在節點A收到節點B新的PDU包時，如果和A本地的關于B的模擬運動的坐標不一致時，怎么樣在A的屏幕上把B拽到新的PDU包所描敘的點上面去呢，上文中只提了用“很平滑的移動”把B“拉扯”過去，那么實際中應該怎么操作呢？這里介紹四種方法。

　　第一種方法，我取名叫直接拉扯法，大家聽名字也知道，就是直接把B硬生生的拽到新的PDU包所描敘的坐標上去，該方法的好處是：簡單。壞處是：看了以下三種方法之后你就不會用這種方法了。

　　第二種方法，叫直線行走（Linear），即讓B從它的當前坐標走直線到新的PDU包所描敘的坐標，行走速度用上文中所介紹的經典算法：
　　　　目標點 = 原點 + 速度 * 時間差 + 1/2 * 加速度 * 時間差算出：
　　首先算出從當前坐標到PDU包中描敘的坐標所需要的時間：
　　　　T = Dest( TargetB – OriginB ) / Speed
　　然后根據新PDU包中所描敘的坐標信息模擬計算出在時間T之后，按照新的PDU包中的運動信息所應該達到的位置：
　　　　_TargetB = NewPDU.Speed * T
　　然后根據當前模擬行動中的B和_TargetB的距離配合時間T算出一個修正過的速度_S：
　　　　_S = Dest( _TargetB – OriginB ) / T
　　然后在畫面上讓B以速度_S走直線到Target_B，并且在走到之后調整其速度，方向，加速度等信息為新的PDU包中所描敘的。

　　這種方法呢，非常的土，會讓物體在畫面上移動起來變得非常的不現實，經常會出現很生硬的拐角，而且對于經常要修改的速度_S，在玩家A的畫面上，玩家B的行動會變得非常的詭異。其好處是：比第一種方法要好。

　　第三種方法，叫二次方程行走（Quadratic），該方法的原理呢，就是在直線行走的過程中，加入二次方程來計算一條曲線路徑，讓Dest( _TargetB – OriginB )的過程是一條曲線，而不是一條直線，恩，具體的實現方法，就是在Linear方法的計算中，設定一個二次方程，在Dest函數計算距離的時候根據設定的二次方程來計算，這樣一來，可以使B在玩家A屏幕上的移動變得比較的有人性化一些。但是該方法的考慮也是不周全的，僅僅只考慮了TargetB到_TargetB的方向，而沒有考慮新的PDU包中的方向描敘，那么從_TargetB開始模擬行走的時候，仍然是會出現比較生硬的拐角，那么下面提出的最終解決方案，將徹底解決這個問題。

　　最后一種方法叫：立方體抖動（Cubic Splines），這個東東比較復雜，它需要四個坐標信息作為它的參數來進行運算，第一個參數Pos1是OriginB，第二個參數Pos2是OriginB在模擬運行一秒以后的位置，第三個參數Pos3是到達_TargetB前一秒的位置，第四個參數pos4是_TargetB的位置。

Struct pos {
    Coordinate X;
    Coordinate Y;
}

　　　Pos1 = OriginB
　　　Pos2 = OriginB + V
　　　Pos3 = _TargetB – V
　　　Pos4 = _TargetB
運動軌跡中(x, y)的坐標。
　　　x = At^3 + Bt^2 + Ct + D
　　　y = Et^3 + Ft^2 + Gt + H
（其中時間t的取值范圍為0-1，在Pos1的時候為0，在Pos4的時候為1）

x(0-3)代表Pos1-Pos4中x的值，y(0-3)代表Pos1-Pos4中y的值
　　　A = x3 – 3 * x2 +3 * x1 – x0
　　　B = 3 * x2 – 6 * x1 + 3 * x0
　　　C = 3 * x1 – 3 * x0
　　　D = x0

　　　E = y3 – 3 * y2 +3 * y1 – y0
　　　F = 3 * y2 – 6 * y1 + 3 * y0
　　　G = 3 * y1 – 3 * y0
　　　H = y0

　　上面是公式，那么下面我們來看看如何獲得Pos1-Pos4：首先，Pos1和 Pos2的取值會比較容易獲得，根據OriginB配合當前的速度和方向可以獲得，然而Pos3和Pos4呢，怎么獲得呢？如果在從Pos1到Pos4的過程中有新的PDU到達，那么我們定義它為NewPackage。

　　　Pos3 = NewPackage.X + NewPackage.Y * t + 1/2 * NewPackage.a * t^2
　　　Pos4 = Pos3 – (NewPackage.V + NewPackage.a * t)

如果沒有NewPackage的情況下,則Pos3和Pos4按照開始所規定的方法獲得。

至此，關于導航推測的算法大致介紹完畢。

歡迎討論，聯系作者：QQ 181194   MSN: xiataiyi@hotmail.com
參考文獻《Defeating Lag with Cubic Splines》