同步在網(wǎng)絡(luò)游戲中是非常重要的，它保證了每個玩家在屏幕上看到的東西大體是一樣的。其實呢，解決同步問題的最簡單的方法就是把每個玩家的動作都向其他玩家 廣播一遍，這里其實就存在兩個問題：1，向哪些玩家廣播，廣播哪些消息。2，如果網(wǎng)絡(luò)延遲怎么辦。

事實上呢，第一個問題是個非常簡單的問題，不過之所以我 提出這個問題來，是提醒大家在設(shè)計自己的消息結(jié)構(gòu)的時候，需要把這個因素考慮進(jìn)去。而對于第二個問題，則是一個挺麻煩的問題，大家可以來看這么個例子： 比如有一個玩家A向服務(wù)器發(fā)了條指令，說我現(xiàn)在在P1點，要去P2點。指令發(fā)出的時間是T0，服務(wù)器收到指令的時間是T1，然后向周圍的玩家 廣播這條消息，消息的內(nèi)容是“玩家A從P1到P2”有一個在A附近的玩家B，收到服務(wù)器的這則廣播的消息的時間是T2，然后開始在客戶端上畫圖，A從P1 到P2點。這個時候就存在一個不同步的問題，玩家A和玩家B的屏幕上顯示的畫面相差了T2-T1的時間。這個時候怎么辦呢？ 有個解決 方案，我給它取名叫 預(yù)測拉扯，雖然有些怪異了點，不過基本上大家也能從字面上來理解它的意思。

要解決這個問題，首先要定義一個值叫：預(yù)測誤差。然后需要在服務(wù)器端每個玩家連 接的類里面加一項屬性，叫TimeModified，然后在玩家登陸的時候，對客戶端的時間和服務(wù)器的時間進(jìn)行比較，得出來的差值保存在 TimeModified里面。還是上面的那個例子，服務(wù)器廣播消息的時候，就根據(jù)要廣播對象的TimeModified，計算出一個客戶端的 CurrentTime，然后在消息頭里面包含這個CurrentTime，然后再進(jìn)行廣播。并且同時在玩家A的客戶端本地建立一個隊列，保存該條消息， 只到獲得服務(wù)器驗證就從未被驗證的消息隊列里面將該消息刪除，如果驗證失敗，則會被拉扯回P1點。然后當(dāng)玩家B收到了服務(wù)器發(fā)過來的消息“玩家A從P1到 P2”這個時候就檢查消息里面服務(wù)器發(fā)出的時間和本地時間做比較，如果大于定義的預(yù)測誤差，就算出在T2這個時間，玩家A的屏幕上走到的地點P3，然后把 玩家B屏幕上的玩家A直接拉扯到P3，再繼續(xù)走下去，這樣就能保證同步。

更進(jìn)一步，為了保證客戶端運行起來更加smooth，我并不推薦直接把玩家拉扯過 去，而是算出P3偏后的一點P4，然后用(P4-P1)/T(P4-P3)來算出一個很快的速度S，然后讓玩家A用速度S快速移動到P4，這樣的處理方法 是比較合理的，這種解決方案的原形在國際上被稱為（Full plesiochronous），當(dāng)然，該原形被我篡改了很多來適應(yīng)網(wǎng)絡(luò)游戲的同步，所以而變成所謂的：預(yù)測拉扯。 另外一個解決方 案，我給它取名叫 驗證同步，聽名字也知道，大體的意思就是每條指令在經(jīng)過服務(wù)器驗證通過了以后再執(zhí)行動作。具體的思路如下：首先也需要在每個玩家連接類型里面定義一個 TimeModified，然后在客戶端響應(yīng)玩家鼠標(biāo)行走的同時，客戶端并不會先行走動，而是發(fā)一條走路的指令給服務(wù)器，然后等待服務(wù)器的驗證。服務(wù)器接 受到這條消息以后，進(jìn)行邏輯層的驗證，然后計算出需要廣播的范圍，包括玩家A在內(nèi)，根據(jù)各個客戶端不同的TimeModified生成不同的消息頭，開始 廣播，這個時候這個玩家的走路信息就是完全同步的了。

這個方法的優(yōu)點是能保證各個客戶端之間絕對的同步，缺點是當(dāng)網(wǎng)絡(luò)延遲比較大的時候，玩家的客戶端的行 為會變得比較不流暢，給玩家?guī)砗懿凰母杏X。該種解決方案的原形在國際上被稱為（Hierarchical master-slave synchronization），80年代以后被廣泛應(yīng)用于網(wǎng)絡(luò)的各個領(lǐng)域。

最后一種解決方案是一種理想化的解決方案，在國際上被 稱為Mutual synchronization，是一種對未來網(wǎng)絡(luò)的前景的良好預(yù)測出來的解決方案。這里之所以要提這個方案，并不是說我們已經(jīng)完全的實現(xiàn)了這種方案，而 只是在網(wǎng)絡(luò)游戲領(lǐng)域的某些方面應(yīng)用到這種方案的某些思想。我對該種方案取名為：半服務(wù)器同步。大體的設(shè)計思路如下： 首先客戶端需要在 登陸世界的時候建立很多張廣播列表，這些列表在客戶端后臺和服務(wù)器要進(jìn)行不及時同步，之所以要建立多張列表，是因為要廣播的類型是不止一種的，比如說有 local message,有remote message,還有g(shù)lobal message 等等，這些列表都需要在客戶端登陸的時候根據(jù)服務(wù)器發(fā)過來的消息建立好。在建立列表的同時，還需要獲得每個列表中廣播對象的TimeModified，并 且要維護(hù)一張完整的用戶狀態(tài)列表在后臺，也是不及時的和服務(wù)器進(jìn)行同步，根據(jù)本地的用戶狀態(tài)表，可以做到一部分決策由客戶端自己來決定，當(dāng)客戶端發(fā)送這部 分決策的時候，則直接將最終決策發(fā)送到各個廣播列表里面的客戶端，并對其時間進(jìn)行校對，保證每個客戶端在收到的消息的時間是和根據(jù)本地時間進(jìn)行校對過的。 那么再采用預(yù)測拉扯中提到過的計算提前量，提高速度行走過去的方法，將會使同步變得非常的smooth。該方案的優(yōu)點是不通過服務(wù)器，客戶端自己之間進(jìn)行 同步，大大的降低了由于網(wǎng)絡(luò)延遲而帶來的誤差，并且由于大部分決策都可以由客戶端來做，也大大的降低了服務(wù)器的資源。由此帶來的弊端就是由于消息和決策權(quán) 都放在客戶端本地，所以給外掛提供了很大的可乘之機。

綜合以上三種關(guān)于網(wǎng)絡(luò)同步派系的優(yōu)缺點，綜合出一套關(guān)于網(wǎng)絡(luò)游戲傳輸同步的較完整的解決方案，我稱它為綜合同步法（colligate synchronization）。大體設(shè)計思路如下： 首先將服務(wù)器需要同步的所有消息從劃分一個優(yōu)先等級，然后按照3/4的比例劃分出重要消息和非重要消息，對于非重要消息，把決策權(quán)放在客戶端，在客戶端邏輯上建立相關(guān)的決策機構(gòu)和各種消息緩存區(qū)，以及相關(guān)的消息緩存區(qū)管理機構(gòu)，如下圖所示： 上圖簡單說明了對于非重要消息，客戶端的大體處理流程，其中有一個客戶端被動行為值得大家注意，其中包括對服務(wù)器發(fā)過來的某些驗證代碼做返回，來確保消 息緩存中的消息和服務(wù)器端是一致的，從而有效的防止外掛來篡改本地消息緩存。其中的消息來源是包括本地的客戶端響應(yīng)玩家的消息以及遠(yuǎn)程服務(wù)器傳遞過來的消 息。

對于重要消息，比如說戰(zhàn)斗或者是某些牽扯到玩家一些比較敏感數(shù)據(jù)的操作，則采用另外一套方案，該方案首先需要在服務(wù)器和客戶端之 間建立一套Ping System，然后服務(wù)器保存和用戶的及時的ping值，當(dāng)ping比較小的時候，響應(yīng)玩家消息的同時先不進(jìn)行動作，而是先把該消息反饋給服務(wù)器，并且阻 塞，服務(wù)器收到該消息，進(jìn)行邏輯驗證之后向所有該詳細(xì)廣播的有效對象進(jìn)行廣播（包括消息發(fā)起者），然后客戶端收到該消息的驗證，才開始執(zhí)行動作。而當(dāng) ping比較大的時候，客戶端響應(yīng)玩家消息的同時立刻進(jìn)行動作，并且同時把該消息反饋給服務(wù)器，值得注意的是這個時候還需要在本地建立一個無驗證消息的隊 列，把該消息入隊，執(zhí)行動作的同時等待服務(wù)器的驗證，還需要保存當(dāng)前狀態(tài)。服務(wù)器收到客戶端的請求后，進(jìn)行邏輯驗證，并把消息反饋到各個客戶端，帶上各個 客戶端校對過的本地時間。如果驗證通過不過，則通知消息發(fā)起者，該消息驗證失敗，然后客戶端自動把已經(jīng)在進(jìn)行中的動作取消，恢復(fù)原來狀態(tài)。如果驗證通過， 則廣播到的各個客戶端根據(jù)從服務(wù)器獲得校對時間進(jìn)行對其進(jìn)行拉扯，保證在該行為完成之前完成同步。 至此，一個比較成熟的網(wǎng)絡(luò)游戲的同步機制已經(jīng)初步建立起來了，接下來的邏輯代碼就根據(jù)各自不同的游戲風(fēng)格以及側(cè)重點來寫了。 同步是網(wǎng)絡(luò)游戲最重要的問題，如何同步也牽扯到各個方面的問題，比如說游戲的規(guī)模，游戲的類型以及各種各樣的方面，對于規(guī)模比較大的游戲，在同步方面可 以下很多的工夫，把消息分得十分的細(xì)膩，對于不同的消息采用不同的同步機制，而對于規(guī)模比較小的游戲，則可以采用大體上一樣的同步機制，究竟怎么樣同步， 沒有個定式，是需要根據(jù)自己的不同情況來做出不同的同步?jīng)Q策的 網(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ò)中的每個客戶端極限誤差：進(jìn)行同步的時候可能產(chǎn)生的誤差的極值 恩，在探討其原理的之前，我們先來看看我們需要一個什么樣的環(huán)境。首先，需要一個網(wǎng)狀網(wǎng)絡(luò)，網(wǎng)狀網(wǎng)絡(luò)如何構(gòu)成呢？當(dāng)有新節(jié)點進(jìn)入的時候，通知該網(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有一個值在不停的記錄著其真實坐標(biāo)和在后臺模擬 運動的坐標(biāo)的差值，當(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)某人看到某人老遠(yuǎn)把自己給砍死的情況。 Dead Reckoning的主要算法有9種，但是只有兩種是解決主要問題的，其他的基本上只是針對不同的坐標(biāo)系的一些不同的算法，這里就不一一介紹了。好，那么我們下面來看傳說中的最主要的兩種算法：第一：目標(biāo)點 = 原點 + 速度 * 時間差第二：目標(biāo)點 = 原點 + 速度 * 時間差 + 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的模擬運動的坐標(biāo)不一致時，怎么樣在A的屏幕上把B拽到新的PDU包 所描敘的點上面去呢，上文中只提了用“很平滑的移動”把B“拉扯”過去，那么實際中應(yīng)該怎么操作呢？這里介紹四種方法。 第一種方法，我取名叫直接拉扯法，大家聽名字也知道，就是直接把B硬生生的拽到新的PDU包所描敘的坐標(biāo)上去，該方法的好處是：簡單。壞處是：看了以下三種方法之后你就不會用這種方法了。 第二種方法，叫直線行走（Linear），即讓B從它的當(dāng)前坐標(biāo)走直線到新的PDU包所描敘的坐標(biāo)，行走速度用上文中所介紹的經(jīng)典算法：目標(biāo)點 = 原點 + 速度 * 時間差 + 1/2 * 加速度 * 時間差算出：首先算出從當(dāng)前坐標(biāo)到PDU包中描敘的坐標(biāo)所需要的時間： T = Dest( TargetB – OriginB ) / Speed 然后根據(jù)新PDU包中所描敘的坐標(biāo)信息模擬計算出在時間T之后，按照新的PDU包中的運動信息所應(yīng)該達(dá)到的位置： _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ù)雜，它需要四個坐標(biāo)信息作為它的參數(shù)來進(jìn)行運算，第一個參數(shù)Pos1是OriginB，第二個參數(shù)Pos2是 OriginB在模擬運行一秒以后的位置，第三個參數(shù)Pos3是到達(dá)_TargetB前一秒的位置，第四個參數(shù)pos4是_TargetB的位置。 Struct pos { Coordinate X; Coordinate Y; } Pos1 = OriginB Pos2 = OriginB + V Pos3 = _TargetB – V Pos4 = _TargetB 運動軌跡中(x, y)的坐標(biāo)。 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到達(dá)，那么我們定義它為NewPackage。 Pos3 = NewPackage.X + NewPackage.Y * t + 1/2 * NewPackage.a * t^2 Pos4 = Pos3 – (NewPackage.V + NewPackage.a * t) 如果沒有NewPackage的情況下,則Pos3和Pos4按照開始所規(guī)定的方法獲得。

本文來自CSDN博客，轉(zhuǎn)載請標(biāo)明出處：http://blog.csdn.net/wolfcoder/archive/2009/02/16/3897672.aspx