同步在網絡游戲中是非常重要的，它保證了每個玩家在屏幕上看到的東西大體是一樣的。其實呢，解決同步問題的最簡單的方法就是把每個玩家的動作都向其他玩家廣播一遍，這里其實就存在兩個問題：1，向哪些玩家廣播，廣播哪些消息。2，如果網絡延遲怎么辦。事實上呢，第一個問題是個非常簡單的問題，不過之所以我提出這個問題來，是提醒大家在設計自己的消息結構的時候，需要把這個因素考慮進去。而對于第二個問題，則是一個挺麻煩的問題，大家可以來看這么個例子：
比如有一個玩家A向服務器發了條指令，說我現在在P1點，要去P2點。指令發出的時間是T0，服務器收到指令的時間是T1，然后向周圍的玩家廣播這條消息，消息的內容是“玩家A從P1到P2”有一個在A附近的玩家B，收到服務器的這則廣播的消息的時間是T2，然后開始在客戶端上畫圖，A從P1到P2點。這個時候就存在一個不同步的問題，玩家A和玩家B的屏幕上顯示的畫面相差了T2-T1的時間。這個時候怎么辦呢？
有個解決方案，我給它取名叫 預測拉扯，雖然有些怪異了點，不過基本上大家也能從字面上來理解它的意思。要解決這個問題，首先要定義一個值叫：預測誤差。然后需要在服務器端每個玩家連接的類里面加一項屬性，叫TimeModified，然后在玩家登陸的時候，對客戶端的時間和服務器的時間進行比較，得出來的差值保存在TimeModified里面。還是上面的那個例子，服務器廣播消息的時候，就根據要廣播對象的TimeModified，計算出一個客戶端的CurrentTime，然后在消息頭里面包含這個CurrentTime，然后再進行廣播。并且同時在玩家A的客戶端本地建立一個隊列，保存該條消息，只到獲得服務器驗證就從未被驗證的消息隊列里面將該消息刪除，如果驗證失敗，則會被拉扯回P1點。然后當玩家B收到了服務器發過來的消息“玩家A從P1到P2”這個時候就檢查消息里面服務器發出的時間和本地時間做比較，如果大于定義的預測誤差，就算出在T2這個時間，玩家A的屏幕上走到的地點P3，然后把玩家B屏幕上的玩家A直接拉扯到P3，再繼續走下去，這樣就能保證同步。更進一步，為了保證客戶端運行起來更加smooth，我并不推薦直接把玩家拉扯過去，而是算出P3偏后的一點P4，然后用(P4-P1)/T(P4-P3)來算出一個很快的速度S，然后讓玩家A用速度S快速移動到P4，這樣的處理方法是比較合理的，這種解決方案的原形在國際上被稱為（Full plesiochronous），當然，該原形被我篡改了很多來適應網絡游戲的同步，所以而變成所謂的：預測拉扯。
另外一個解決方案，我給它取名叫 驗證同步，聽名字也知道，大體的意思就是每條指令在經過服務器驗證通過了以后再執行動作。具體的思路如下：首先也需要在每個玩家連接類型里面定義一個TimeModified，然后在客戶端響應玩家鼠標行走的同時，客戶端并不會先行走動，而是發一條走路的指令給服務器，然后等待服務器的驗證。服務器接受到這條消息以后，進行邏輯層的驗證，然后計算出需要廣播的范圍，包括玩家A在內，根據各個客戶端不同的TimeModified生成不同的消息頭，開始廣播，這個時候這個玩家的走路信息就是完全同步的了。這個方法的優點是能保證各個客戶端之間絕對的同步，缺點是當網絡延遲比較大的時候，玩家的客戶端的行為會變得比較不流暢，給玩家帶來很不爽的感覺。該種解決方案的原形在國際上被稱為（Hierarchical master-slave synchronization），80年代以后被廣泛應用于網絡的各個領域。
最后一種解決方案是一種理想化的解決方案，在國際上被稱為Mutual synchronization，是一種對未來網絡的前景的良好預測出來的解決方案。這里之所以要提這個方案，并不是說我們已經完全的實現了這種方案，而只是在網絡游戲領域的某些方面應用到這種方案的某些思想。我對該種方案取名為：半服務器同步。大體的設計思路如下：
首先客戶端需要在登陸世界的時候建立很多張廣播列表，這些列表在客戶端后臺和服務器要進行不及時同步，之所以要建立多張列表，是因為要廣播的類型是不止一種的，比如說有local message,有remote message,還有global message 等等，這些列表都需要在客戶端登陸的時候根據服務器發過來的消息建立好。在建立列表的同時，還需要獲得每個列表中廣播對象的TimeModified，并且要維護一張完整的用戶狀態列表在后臺，也是不及時的和服務器進行同步，根據本地的用戶狀態表，可以做到一部分決策由客戶端自己來決定，當客戶端發送這部分決策的時候，則直接將最終決策發送到各個廣播列表里面的客戶端，并對其時間進行校對，保證每個客戶端在收到的消息的時間是和根據本地時間進行校對過的。那么再采用預測拉扯中提到過的計算提前量，提高速度行走過去的方法，將會使同步變得非常的smooth。該方案的優點是不通過服務器，客戶端自己之間進行同步，大大的降低了由于網絡延遲而帶來的誤差，并且由于大部分決策都可以由客戶端來做，也大大的降低了服務器的資源。由此帶來的弊端就是由于消息和決策權都放在客戶端本地，所以給外掛提供了很大的可乘之機。
綜合以上三種關于網絡同步派系的優缺點，綜合出一套關于網絡游戲傳輸同步的較完整的解決方案，我稱它為綜合同步法（colligate synchronization）。大體設計思路如下：
首先將服務器需要同步的所有消息從劃分一個優先等級，然后按照3/4的比例劃分出重要消息和非重要消息，對于非重要消息，把決策權放在客戶端，在客戶端邏輯上建立相關的決策機構和各種消息緩存區，以及相關的消息緩存區管理機構，如下圖所示：
上圖簡單說明了對于非重要消息，客戶端的大體處理流程，其中有一個客戶端被動行為值得大家注意，其中包括對服務器發過來的某些驗證代碼做返回，來確保消息緩存中的消息和服務器端是一致的，從而有效的防止外掛來篡改本地消息緩存。其中的消息來源是包括本地的客戶端響應玩家的消息以及遠程服務器傳遞過來的消息。
對于重要消息，比如說戰斗或者是某些牽扯到玩家一些比較敏感數據的操作，則采用另外一套方案，該方案首先需要在服務器和客戶端之間建立一套Ping System，然后服務器保存和用戶的及時的ping值，當ping比較小的時候，響應玩家消息的同時先不進行動作，而是先把該消息反饋給服務器，并且阻塞，服務器收到該消息，進行邏輯驗證之后向所有該詳細廣播的有效對象進行廣播（包括消息發起者），然后客戶端收到該消息的驗證，才開始執行動作。而當ping比較大的時候，客戶端響應玩家消息的同時立刻進行動作，并且同時把該消息反饋給服務器，值得注意的是這個時候還需要在本地建立一個無驗證消息的隊列，把該消息入隊，執行動作的同時等待服務器的驗證，還需要保存當前狀態。服務器收到客戶端的請求后，進行邏輯驗證，并把消息反饋到各個客戶端，帶上各個客戶端校對過的本地時間。如果驗證通過不過，則通知消息發起者，該消息驗證失敗，然后客戶端自動把已經在進行中的動作取消，恢復原來狀態。如果驗證通過，則廣播到的各個客戶端根據從服務器獲得校對時間進行對其進行拉扯，保證在該行為完成之前完成同步。
至此，一個比較成熟的網絡游戲的同步機制已經初步建立起來了，接下來的邏輯代碼就根據各自不同的游戲風格以及側重點來寫了。
同步是網絡游戲最重要的問題，如何同步也牽扯到各個方面的問題，比如說游戲的規模，游戲的類型以及各種各樣的方面，對于規模比較大的游戲，在同步方面可以下很多的工夫，把消息分得十分的細膩，對于不同的消息采用不同的同步機制，而對于規模比較小的游戲，則可以采用大體上一樣的同步機制，究竟怎么樣同步，沒有個定式，是需要根據自己的不同情況來做出不同的同步決策的
網游同步算法之導航推測（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》
本文來自CSDN博客，轉載請標明出處：http://blog.csdn.net/wind520/archive/2009/02/17/3898948.aspx
posted @
2009-09-07 16:22 暗夜教父 閱讀(222) |
評論 (0) |
編輯 收藏稍微深入研究過一點 java 的同學，恐怕都知道什么叫做 “反編譯” 。也就是說，隨便拿一個 class 文件，找一個 jad 來，所有的 “智慧結晶” 就全都 “真相大白” 了，跟原先的 source code 相比，區別只是沒有注釋而已。
對于開源軟件開發者來說，這本是無所謂的事，但對于商業開發者而言，這簡直就是噩夢。在 java 的世界，道高一尺魔高一丈(及其反復迭代)的結果是，這件事最終演變得比較詭異，以至于專門誕生了一個名叫 “代碼混淆” 的產業。在我上一次關注的時候，這個領域的最新進展是可以 “混淆” 程序執行的流程，以至于正常的人類閱讀反編譯出來的源碼，將會導致嚴重的腦殘。不過，傳說又出了個叫做 “流程優化器” 的東東……(這個故事未完待續)。
其實，這件事困擾的不僅只是 java ，幾乎所有 “有源代碼” 的程序都有這個煩惱。比如，飽受折磨的還有 php, asp 以及 .net。不知道有沒有高人能從 “機器碼” 反編譯出 C 和 C++ 的源程序呢，反正我挺好奇的。不過，話說回來， “沒有源代碼” 的程序，恐怕還真的沒有。保護源代碼，在我們現如今 “處處是山寨，遍地是豺狼” 的產業現狀之下，似乎仍然是個不得不認真對待的事情。
在源代碼保護的問題上，Erlang 的表現又會如何？今天體驗了一把，應該說，設計得很細致，至于說這樣的設計是否能夠完全杜絕源代碼的泄露，這個問題恐怕仍然需要留給 “專家” 們去研究。好吧，口水就噴到這里，下面上干貨。
目前這個階段，對 Erlang 源代碼的保護，主要是在 debug_info 上做手腳，因為，在 debug_info 里面有完整的源代碼，可以極其輕松的從中 “找回” 源碼(兩個語句而已，在官方文檔之中都有例子)。
先看如何從 Erlang 的 beam 文件獲取源代碼。象這樣的一個簡單程序：
-module(a).
-export([test/0]).
test() ->
io:format("source code.~n", []).
帶 debug_info 編譯，并運行之。
$ erlc +debug_info a.erl
$ erl -s a test -s c q -noshell
source code.
$
我們可以這樣還原它的源碼：
$ erl
1> {ok,{_,[{abstract_code,{_,AC}}]}} = beam_lib:chunks(code:which(a), abstract_code]).
{ok,{a,[{abstract_code,
{raw_abstract_v1,
[{attribute,1,file,{"./a.erl",1}},
{attribute,1,module,a},
{attribute,3,export,[{test,0}]},
{function,5,test,0,
[{clause,5,[],[],[{call,6,{remote,...},[...]}]}]},
{eof,7}]}}]}}
2> io:fwrite("~s~n", [erl_prettypr:format(erl_syntax:form_list(AC))]).
-file("./a.erl", 1).
-module(a).
-export([test/0]).
test() -> io:format("source code.~n", []).
ok
3>
看，和源碼幾乎完全一致。
那么，如果我們編譯的時候不帶 debug_info 呢？是的，完全可以。不過，如果你想要在這樣的 beam 上執行 debugger 或者 xref 之類的動作，那么，沒有 debug_info 就做不了。天知道我們會不會有需要做 “現場調試” 的時候呢。有沒有既保留 debug_info 又阻止其他人通過 debug_info 來得到源碼的辦法呢？有，那就是——加密 debug_info 。
首先建立一個 ~/.erlang.crypt 文件，內容如下：
$ cat ~/.erlang.crypt
[{debug_info, des3_cbc, [], "my_source_code_secret_key"}].
這里的 “my_source_code_secret_key” 就被用來生成對 debug_info 加密的密鑰。用 encrypt_debug_info 參數編譯，并運行之。
$ erlc +encrypt_debug_info a.erl
$ erl -s a test -s c q -noshell
source code.
現在拿掉 ~/.erlang.crypt (模擬生產機環境)，看看能否正常運行。
$ mv ~/.erlang.crypt ~/.erlang.old.crypt
$ erl -s a test -s c q -noshell
source code.
運行沒問題。此時，是否還能還原源碼呢。
$ erl
1> beam_lib:chunks(code:which(a), [abstract_code]).
{error,beam_lib,
{key_missing_or_invalid,"./a.beam",abstract_code}}
這正是我們想要的。
比如說，假如某日我們需要在這臺生產機上做 “現場調試”，那就再加上 ~/.erlang.crypt 文件。作為驗證，我們再執行一次還原源碼的操作。
$ mv ~/.erlang.old.crypt ~/.erlang.crypt
$ erl
1> {ok,{_,[{abstract_code,{_,AC}}]}} = beam_lib:chunks(code:which(a), abstract_code]).
{ok,{a,[{abstract_code,
{raw_abstract_v1,
[{attribute,1,file,{"./a.erl",1}},
{attribute,1,module,a},
{attribute,3,export,[{test,0}]},
{function,5,test,0,
[{clause,5,[],[],[{call,6,{remote,...},[...]}]}]},
{eof,7}]}}]}}
2> io:fwrite("~s~n", [erl_prettypr:format(erl_syntax:form_list(AC))]).
-file("./a.erl", 1).
-module(a).
-export([test/0]).
test() -> io:format("source code.~n", []).
ok
3>
看 debug_info 還原出來了。
我們藏在 debug_info 中的源碼是被 des3_cbc 算法保護起來的，有興趣的童鞋可以去 wiki 百科了解它的加密強度，解開它的關鍵是 ~/.erlang.crypt 文件，只要它不泄露，那么在生產環境下，我們的代碼就仍然是安全的，也就是說，就算這臺機器被黑掉了，也還原不出源碼(如果我說錯了，請糾正我)，而且只要你持有 .erlang.crypt 文件，(在需要的時候)仍然可以進行調試。
實驗之前，確實沒想到 Erlang 還設計了這么一個機制，挺細致的。需要說明的是，上述方案是對 beam 中的 debug_info 進行了加密，從而阻止其他人從中獲取源碼，至于是否還有其他的還原源碼的可能，目前還不是很清楚。比如，理論上，是否有可能通過 beam 之中的 op code 反編譯出原始的 source code 呢？對于這個話題，如果有童鞋知道，請不吝賜教。
posted @
2009-09-07 16:18 暗夜教父 閱讀(707) |
評論 (0) |
編輯 收藏