網(wǎng)游同步算法之導(dǎo)航推測（Dead Reckoning）算法：

　　在了解該算法前，我們先來談?wù)勗撍惴ǖ囊恍┍尘百Y料。大家都知道，在網(wǎng)絡(luò)傳輸?shù)臅r候，延遲現(xiàn)象是很普遍的，而在基于Server/Client結(jié)構(gòu)下的網(wǎng)絡(luò)游戲的同步也就成了很頭疼的問題，在保證客戶端響應(yīng)用戶本地指令流暢的情況下，沒法有效的保證的同步的及時性。同樣，在軍方也有類似的事情發(fā)生，即使是同一LAN里面的機器，也會因為傳輸?shù)难舆t，導(dǎo)致一些運算的失誤，介于此，美國國防部投入了大量的資金用于研究一種比較的好的方案來解決分布式系統(tǒng)中的延遲問題，特別是一個叫分布式模擬運動（Distributed Interactive Simulation）的系統(tǒng)，這套系統(tǒng)呢，其中就提出了一套號稱是Latency Hiding & Bandwidth Reduction的方案，命名為Dead Reckoning。呵呵，來頭很大吧，恩，那么我們下面就來看看這套系統(tǒng)的一些觀點，以及我們?nèi)绾伟阉\用到我們的網(wǎng)絡(luò)游戲的同步中。

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

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

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

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

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

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

　　該方法結(jié)合我在《網(wǎng)絡(luò)游戲的同步》一文中提出的綜合同步法的構(gòu)架可以基本上解決掉網(wǎng)絡(luò)游戲中走路同步的問題。相關(guān)問題歡迎大家一起討論。

有關(guān)導(dǎo)航推測算法（Dead Reckoning）中的平滑處理：

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

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

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

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

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

　　最后一種方法叫：立方體抖動（Cubic Splines），這個東東比較復(fù)雜，它需要四個坐標信息作為它的參數(shù)來進行運算，第一個參數(shù)Pos1是OriginB，第二個參數(shù)Pos2是OriginB在模擬運行一秒以后的位置，第三個參數(shù)Pos3是到達_TargetB前一秒的位置，第四個參數(shù)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的取值會比較容易獲得，根據(jù)OriginB配合當(dāng)前的速度和方向可以獲得，然而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按照開始所規(guī)定的方法獲得。

至此，關(guān)于導(dǎo)航推測的算法大致介紹完畢。

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