網絡游戲引擎中同步技術研究綜述
2007-01-01 00:00:00邱航何明耘陳雷霆
計算機應用研究 2007年1期
摘要：由于網絡游戲依托于現有的互聯網技術，網絡傳輸中的延遲、出錯等問題總是不可避免的，因此游戲中狀態的同步便是一個很大的問題。討論了LockStep同步算法、Bucket同步算法、TimeWarp同步算法、基于DR的Bucket同步算法以及客戶端預測等幾種網絡引擎同步技術，并在此基礎上總結出在設計同步策略時應考慮的若干問題。
關鍵詞： 網絡引擎； 同步； 客戶端預測
中圖法分類號：TP311．5文獻標識碼：A
文章編號：1001－3695(2007)01-0014－04
1引言
網絡游戲是近年來得到眾多關注和發展較快的VR應用技術之一。2003年，國家科技部首次將網絡游戲技術納入國家“863”科技發展計劃，這標志著國家對年增長率近三倍、帶動上下游經濟增長超過十倍的網絡游戲產業態度已經明朗化。如今我國的網絡游戲業已經進入了一個發展的高峰期。
隨著技術的發展，網絡游戲已進入了MMOG（Massively Multiplayer Online Game，大型多人在線游戲）時代，游戲規模日益龐大。因此，網絡游戲引擎必須具有極強的網絡處理能力，在固有的網絡延遲、不可避免的丟包以及有限帶寬資源的情況下，能夠對整個游戲世界的狀態在服務器與客戶端之間進行同步，使玩家體驗到更好的游戲效果，并實現玩家之間數據的安全傳輸。由于目前網絡游戲主要依托于互聯網技術，并且現有的多人在線游戲主要采用客戶/服務器模型，網絡傳輸中的延遲、出錯等問題已成為整個游戲的瓶頸，因而對網絡游戲引擎中同步技術的研究在實際應用中具有很重要的意義。本文將著重分析網絡游戲引擎中的各種同步技術，并在此基礎上對同步策略進行總結。
2保守同步算法
保守同步算法是指在保證數據安全、正確時才進行的處理。在網絡游戲中使用的保守同步算法一般有兩種，即LockStep同步和Bucket同步機制。
2．1LockStep同步
LockStep[1~5]同步算法最初用于軍事仿真系統中，是目前保證系統一致性最簡單的技術。正如其名，在所有需要同步的計算機確認當前時間段的計算之前，任何計算機均不準繼續其仿真時鐘，這樣便可以為所有事件提供一個全局的順序。通過這樣的限制，需要同步的計算機在每次執行下一輪計算前都能確保所有計算機的游戲狀態是相同的，因此確保了游戲狀態的一致性。
從同一個游戲狀態開始，其游戲時間分為若干周期。在每一個周期里面，每臺計算機都在自己的游戲世界里接受一個動作以前進一步。在此周期的結尾，每臺計算機都會告訴其他所有的計算機玩家究竟做了一些什么動作。這樣，所有的玩家都知道其他玩家在做什么，因此他們就可以共同得到下一個游戲周期的世界，從而保持同步了。此算法很容易實現，而且其帶寬也相對較低，因為需要傳輸的東西只有用戶的輸入。其帶寬與游戲的狀態也是無關的，這對于實現策略游戲來說是一個很大的優點。
該算法的一個缺點是每秒游戲的周期數是受到往返網絡延遲限制的。在每個游戲周期的結尾，這些計算機都必須至少收到從所有其他計算機發來的一個確認信息，這樣才能繼續得到下一個游戲周期的世界。要保持這些計算機的同步也是相當困難的，必須保證用戶的輸入不會直接影響到游戲，只能間接地通過網絡的代碼來影響游戲。這就確保了所有的游戲都是在處理相同的信息，而且必須時刻遵循這條規則。類似地，還必須對隨機數生成器保持同步。
2．2固定TimeBucket同步[5]
同步問題的產生很大程度上是由于各玩家網絡條件的不同，因而其網絡延遲不同所帶來的。Bucket同步機制正是依據網絡延遲不同這一點來保證游戲狀態的一致性。在固定TimeBucket同步中，引入了同步延遲（Syncdelay）來減少對各玩家延遲的依賴。根據玩家的網絡延遲上限選定一個時間段，而服務器依據此時間段構建一個Bucket，用于存放客戶端的消息。客戶端發送消息時會同時發送一個序號，服務器收到消息后根據序號將消息放入相應序號的Bucket中；而服務器端則為每個用戶維護一個計數器，當服務器收到客戶端發送的第一個數據包時，服務器就每隔選定的時間段將計數器加1，同時根據計數器的值從Bucket中取出消息發送給客戶端。通過這樣的方法就保證了數據包的順序處理。
保守同步算法通常情況下均能保證游戲狀態的一致性，但沒有充分利用并發的概念。采用保守同步算法時會帶來額外的等待，響應速度慢，因而只適合于那些對響應要求不高、節奏較慢的回合制游戲；對于那些對延遲特別敏感的、節奏較快的游戲則完全不能滿足要求。
3樂觀同步算法
樂觀同步算法與保守同步算法相反，在處理數據前并不做任何檢測工作，而是樂觀地認為沒有錯誤發生，直接進行處理，如果后來發現執行了錯誤的操作則進一步更正以保證游戲世界的一致性。樂觀的同步算法主要有TimeWarp、基于DR（Dead Reckoning，航位推測）的Bucket算法以及基于相關和過時的同步策略。
3．1TimeWarp同步
TimeWarp[1，5~10]同步機制已被普遍認為是分布式系統中最重要的樂觀同步協議。在TimeWarp中，各處理節點（如服務器）之間沒有外在的同步，這些節點以不同的速率各自進行本地的仿真時鐘。如圖1所示，處理節點在每個事件執行前會對游戲狀態做個快照（Snapshot），如果收到一個遲到的事件，并且此事件之前的事件已經被處理完畢，即事件收到的順序是打亂的，那么就發起回滾任務，快照和剛執行的事件之間發生的所有事件都要被撤銷。狀態就會回到早先做的快照那里，此快照是沒有按序進行處理的事件之前最新的一個；接著這些被回滾的事件將按序重新執行。進行回滾操作通常包括兩步：①將狀態恢復到遲到事件的時間戳之前的時刻；②取消沒有按序處理的事件所帶來的一切影響。
有兩種方法可以實現對錯誤的狀態參數值進行回滾：①每個處理節點在執行一個事件時存儲整個游戲狀態的快照，這樣當收到一個遲到的事件時，回滾是通過把游戲狀態恢復到這個遲到事件之前的快照來實現的，這種技術通常稱為海量狀態存儲。當游戲事件處理中要修改很多變量時非常適用。②增量狀態存儲。只將游戲事件中改變的狀態參數記錄到日志中，日志中的每個實體對應著一個事件的計算，包含被修改的參數以及修改前的值。這樣當收到一個遲到的事件時，將掃描日志和回滾事件所改變的參數值恢復到此遲到事件之前的值。如果每個游戲事件只修改很小一部分狀態參數，這種方法就顯得非常有效。
為了解決取消已經發送的消息（Unsending Sent Messages），TimeWarp借助Antimessage的使用。一個Antimessage就是一個包含給定事件的原始消息的拷貝，再加上一個用來標志Antimessage的標記。這樣，當回滾發生時，對于回滾事件后所發送的每個消息，均有一個相關的Antimessage來通知其他處理節點。處理節點一旦收到Antimessage就會觸發一個本地回滾，這樣就有可能遞歸產生額外的Antimessage。但在網絡游戲中，此問題還不是很明顯，因為事件的產生一般不會自動引起其他事件的直接產生。
TimeWarp中的檢查點（Checkpoint）過多，消耗很多內存和CPU資源，Quake I[4，7，11]就使用了TimeWarp同步機制，其中每個快照占用1MB~30MB左右的空間。
3．2基于DR的Bucket同步[1]
基于DR的Bucket算法[5，17]則是固定TimeBucket算法的一個樂觀改進。它仍然采用了同步延遲機制，但如果有事件丟失或是晚于期待時間到達時，它不以任何方式檢測游戲的不一致性，也不試圖恢復不一致性，而是采用基于DR推測的方法來處理丟失的事件。MiMaze[6，7，12，13]中采用的就是此種同步機制。其內容具體如下：將時間分成多個固定長度的采樣周期，每個采樣周期對應一個Bucket。在一個采樣周期中，由發送者發送過來的消息接收者都會把它們存放在一個對應的Bucket中，當一個主機要發送更新的全局狀態時，會計算當前Bucket中可用的消息，如圖2所示。沒有同步機制的話，本地t3時刻產生的消息將與另外一個主機t1時刻產生（但是在t2時刻到達，與t3在同一個時間段）的消息一起進行處理。為了與另一個主機上t1時刻的消息同步，Bucket同步機制允許t0時刻的消息被延遲到將在td時刻處理的Bucket d中。
此種同步機制并不試圖檢測不一致性，也不進行相應的恢復機制。主機中一旦特定的Bucket中沒有可用消息，那么就對前一個Bucket中的消息進行航位推測，如只是簡單地再執行一次上一個消息，或者在上幾個消息的基礎上另外推出一個新的消息。可以通過增加同步延遲降低Bucket中的不一致性，但是這樣同時會降低響應度。所以在同步延遲和響應時間上要有一個很好的權衡。一般在消息接收的基礎上計算同步延遲，以決定消息應該存放到哪個Bucket中。MiMaze中的同步延遲是150ms－網絡延遲。換句話說，在絕對時間t產生的消息將在絕對時間t＋100ms的時間段到達接收端，這里假設網絡延遲為100ms，如果網絡延遲大于100ms，消息將被丟棄。Bucket頻率決定了計算新游戲狀態的速率，25fps的頻率對人的視覺來說已經很連貫了，MiMaze中選擇每秒計算25個Bucket。Bucket頻率是接收端的一個參數，它不受網絡參數的影響，降低此頻率的唯一原因只能是本地CPU的限制。
3．3基于相關和過時的同步
基于相關和過時的同步策略[1]是對TimeWarp同步算法的改進，該策略主要用于集群鏡像服務器架構。在此架構中，游戲世界被分為多個子區域，同時游戲服務器（Game Server，GS）也被分成不同的組。每組GS與一個子區域相關聯，負責管理此子區域中的所有玩家以及游戲狀態。
定義1消息產生時間（Message Generation Time，MGT）。消息m的MGT是指由某個GS產生消息m的時間，記為Tg(m)。
定義2消息傳送時間（Message Delivery Time，MDT）。消息m對應于某個GS q的MDT表示m在游戲服務器q的傳送時間，記為Tqd(m)。
每個消息m只有一個Tg(m)，但對于兩個不同的GS，如p和q，對消息m的發送時間一般是不同的，即Tpd(m)≠Tqd(m)。每個消息m，對于任意的一個GS p都有Tg(m)≤Tpd(m)。
定義3游戲時間差（Game Time Difference，GTD）。給定一個接收GS p以及一個消息m，其游戲時間差即為m在p的傳送時間和m的產生時間差值。
GTDp(M)=Tpd(m)-Tg(m)
3．3．1消息相關性
消息的按序處理能夠保證游戲世界的一致性，為了更好地把握消息處理的順序性，在此引入了相關性（Correlated）的概念。
所有相關的消息都要按照嚴格的順序進行處理，不相關的消息可以在不同的GSS上按照不同的順序來處理。這樣對于不存在相關性的消息，一旦到達GS即可進行相應的處理，不需要進行同步。為了實現游戲狀態的一致性，并不需要對所有消息按正確順序進行處理，只需將相關的消息順序處理即可。
3．3．2過時消息
使用消息丟棄策略將游戲過程中不再重要的消息丟掉，這樣并不會影響游戲的正確性，這種消息便稱為過時（Obsolete）消息。這種方法可以減少GS上的計算量，并可加速新到消息的執行。因而，消息丟棄策略可以提高整個游戲世界的交互性。
引入表達式(mi;mi+1…mj-1;mj，S)→S*，表示狀態依次在消息 mi，mi+1，…，mj-1，mj的作用下到達狀態S*。當有(mi;mi+1… mj-1;mj，S)→S*，并且(mi+1…mj-1;mj，S)→S*時，我們就說mj讓mi變得輕度過時。在實際操作中，要判斷一個消息是否過時，就要把GS上所有處理完的消息找出來，這不是一項簡單的工作。為此可以使用輕度過時的簡化版本，即強過時（Strong Obsolescence）。在輕度過時的基礎上，如果mi和mj之間沒有其他相關的消息，那么就說mj讓mi變得強過時。
3．3．3基于相關和過時的同步策略
基于相關和過時的同步策略的具體方法是：一旦收到消息m，首先判斷它有沒有過時，如果已經過時則直接丟棄；否則立即處理此消息。此外，對于與m相關但是沒有按序處理的消息，則進行回滾以修正錯誤，被回滾而且沒有過時的消息再按照正確的順序重新處理；被回滾而且過時的消息直接被丟棄處理，以加快消息處理的速度以及游戲世界的交互性。這種基于相關和過時的同步機制，是在UDP的基礎上使用接收端（Receiverinitiated）發出確認信息的方式，即NACK（Negative ACKnowledgments）信息為沒有過時的消息提供可靠性傳輸。圖3描述了這種同步機制的模型。
如圖3所示，Sender GS上產生的消息或者從客戶端收到的消息m，通過服務send_message發送給Receiver GS，接著將消息m交給GS中相應的組件進行處理。通過過時邏輯和相關邏輯的判斷，對于需要回滾的消息進行回滾操作，然后再根據過時邏輯的判斷結果對這些回滾的消息進行相應的處理。對于沒有收到并且沒有過時的消息，會發送一個NACK給Sender GS，說明沒有收到這些消息，請求重新發送。對于每一個NACK，Sender GS會根據過時邏輯判斷有沒有必要重發此消息，如果沒有過時就重發此消息，否則就發送新的消息。
樂觀同步算法雖然有可能會有不一致的狀態出現，但其響應迅速，可以應用在那些對響應要求比較高的游戲中，如Quake游戲中就采用了樂觀同步算法。
4客戶端預測
在C/S網絡結構中，不同客戶端的網絡延遲是不同的，服務器端在加入同步機制的同時，還要在客戶端對遲到的或者丟失的消息進行相應的預測，并在發現錯誤時能夠及時地糾正，盡可能地使客戶端的游戲狀態保持連貫和一致。
4．1多表法
多表法是一種理想化的解決方案，在國際上被稱為Mutual Synchronization，是一種對未來網絡前景的良好預測而提出來的解決方案。該方法大體的設計思路如下[14]：
首先客戶端需要在登錄游戲時建立多張廣播列表，這些列表在客戶端后臺與服務器之間進行同步。之所以要建立多張列表是因為要廣播的類型不止一種，如Local Message，Remote Message，Global Message等，這些列表都需要在客戶端登錄時根據服務器發過來的消息建立好。在建立列表的同時，還需要獲得每個列表中廣播對象的延遲，并且要在后臺維護一張完整的用戶狀態列表，也要經常性與服務器進行同步，根據本地的用戶狀態表可以做到一部分決策由客戶端自己來決定。當客戶端發送這部分決策時，直接將最終決策發送到各個廣播列表中的客戶端，并對其時間進行校對，以保證每個客戶端收到消息的時間是根據本地時間進行校對過的。
該方案的優點是不通過服務器，客戶端之間能進行同步，大大降低了由于網絡延遲而帶來的誤差，并且由于大部分決策都可以由客戶端來做，也大大降低了服務器的資源。由此帶來的弊端就是由于消息和決策權均放在客戶端本地，所以給外掛提供了很大的可乘之機。
4．2航位推測法[14~17]
對于網絡程序中由互聯網固有的延遲效應帶來的狀態不同步現象，可以采用增加包發送的頻率，通過壓縮方法來減小包的大小，最通用的是航位推測法。
航位推測法是一種導航方法，它被廣泛用于船運、航空和最新的移動機器人方面。本質上，DR是根據物體前一個時刻的位置和它所行走的距離與方向，從而預測出物體下一個時刻位置的方法。
現在的網絡游戲和網絡模擬程序中廣泛使用著Dead Rec￣koning方法，使用這種方法可以減少由于網絡帶寬和網絡延時造成的滯后效應。程序中通常利用這種方法來根據上一次實體狀態預測實體的下一個狀態（如根據噴氣式戰機的當前速度和位置預測戰機的運動軌跡），有些網絡程序利用這種方法來消除實體更新的時間差。
5同步策略總結
同步問題在網絡游戲中至關重要，不過到目前為止，還沒有十分完善的方法來解決該問題。現有的措施主要是采用一些同步算法來減少網絡不同步帶來的影響，這些同步算法大部分是從分布式軍事仿真系統中借鑒過來的。但通過對已有的解決方案的分析，我們可以總結出網絡游戲引擎中，在設計同步策略時應考慮的幾點：
（1）考慮網絡游戲體系結構。網絡游戲是采用C/S，P2P還是分布式體系結構，這是直接關系到選擇同步策略的前提。
（2）考慮同步的范圍。其核心問題是將游戲世界劃分成粒度比較小的區域，這樣可以快速定位需要給哪些區域中的用戶發送同步消息。
（3)考慮同步的內容。將同步的內容進行細分，如不需要同步的屬性（服務器端和客戶端根據本地的配置文件載入）；需要在創建時同步一次，以后不會改變（如玩家的性別）；需要頻繁的同步屬性（如玩家的生命）。
（4)考慮同步的頻率。對于客戶端發出的命令都要即時地發送給服務器或者其他客戶端（在不需要服務器參與管理的情況下）。對于服務器端發送的狀態更新命令可以不用即時發送，而是選擇一個合適的頻率以及對象顯示的細節度進行發送，具體的數值需要由足夠的靈活性來調節。
（5)低網絡延遲。網絡延遲不可避免，如何減少延遲以及延遲發生后如何減少客戶端的視覺感受非常重要，可以考慮采用客戶端預測以及服務器端矯正。
參考文獻：
［1］Stefano Ferretti. Interactivity Maintenance for Event Synchronization in Massive Multiplayer Online Games［R］.Technical Report UBLCS， 2005.3060.
［2］J S Steinman. Scalable Parallel and Distributed Military Simulations Using the Speedes Framework［R］. Technical Report， NASA， Jet Propulsion Laboratory，1995.332.
［3］R M Fujimoto. Parallel and Distribution Simulation Systems［M］.NY：John Wiley Sons，1999.20100.
［4］Dante Treglia.游戲編程精粹［M］.張磊．北京：人民郵電出版社，2003.424485.
［5］Eric Cronin， Anthony R Kurc， Burton Filstrup， et al. An Efficient Synchronization Mechanism for Mirrored Game Architectures［J］. Multimedia Tools andApplications，20-04，23(1)：730.
［6］D R Jefferson. Virtual Time［J］. ACM Transactions on Programming Languages and Systems，1985，7(3)：404425.
［7］L Gautier， C Diot， J Kurose. EndtoEnd Transmission Control Mecha￣nisms for Multiparty Interactive Applications on the Internet［C］. Proc. of IEEE INFOCOM， 1999.14701479.
［8］A Gafni. Rollback Mechanism for Optimistic Distributed Simulation Systems［C］.Proceedings of the SCS Multiconference on Distributed Simulation， 1988.6167.
［9］D West. Optimizing TimeWarp： Lazy Rollback and Lazy Reevaluation［D］. Alberta: Computer Science Department， University of Calgary， 1988.2080.
［10］M Mauve， J Vogel， V Hilt， et al. Locallag and TimeWarp： Providing Consistency for Replicated Continuous Applications［J］. IEEE Transactions on Multimedia， 20-04，6(1)：4757.
［11］S Bonham， D Grossman， W Portnoy， et al. Quake： An Example Multiuser Network ApplicationProblems and Solutions in Distributed Interactive Simulations［EB/OL］. http：//www.cs.washington.edu/homes/grossman/ projects/561projects/quake/，2000.
［12］YowJian Lin， Katherine Guo， Sanjoy Paul. SyncMS：Synchronized Messaging Service for Realtime Multiplayer Distributed Games［C］.Proceedings of the 10th IEEE International Conference on Network Protocols(ICNP)， 2002.155164.
［13］L Gautier， C Diot. MiMaze， a Multiuser Game over the Internet［R］. INRIA Research Report 3248， INRIA Sophia Antipolis， 1997.2030.
［14］四維科技，丁展．Visual C++游戲開發技術與實例［M］.北京：人民郵電出版社，2005.550.
［15］Jesse Aronson. Dead Reckoning：Latency Hiding for Networked Games［EB/OL］. http：//www.gamasutra.com/features/19970919/aronson_01.htm， 1997.
［16］Jesse Aronson. Dead Reckoning：Latency Hiding for Networked Games[A]. Nicholas Van Caldwell. Defeating Lag with Cubic Splines［EB/OL］. http：//www.gamedev.net/reference/articles/article914.asp，2002.
［17］Jesse Aronson. Dead Reckoning：Latency Hiding for Networked Games[A]. Sudhir Aggarwal， Hemant Banavar， Amit Khandelwal， et al. Accuracy in Dead Reckoning Based Distributed Multiplayer Games［C］. Proceedings of ACM SIGCOMM Workshops on NetGames， 20-04.161165.
作者簡介：
邱航（1978），男，四川成都人，助教，碩士，主要研究方向為虛擬現實技術、計算機網絡；何明耘（1972），男，四川人，講師，博士，主要研究方向為虛擬現實技術；陳雷霆（1966），男，重慶人，教授，博士，主要研究方向為虛擬現實技術。
注:本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文
