游戏思考04补充：网络游戏同步算法的理解（参考网易雷火jerish的文章，未完待续7/23，参考文献附尾，物理同步已更新完）
文章目錄
- 一、網(wǎng)絡(luò)同步概念理解
- 二、網(wǎng)絡(luò)架構(gòu)與傳統(tǒng)同步
- 1）網(wǎng)絡(luò)游戲架構(gòu)的發(fā)展
- 2）傳統(tǒng)同步面臨的問題
- 3）參考文獻(xiàn)：
- 三、鎖步同步lockstep（幀同步）
- （三的補(bǔ)充幀同步的前提提要）
- 1）早期的Lockstep(確定性鎖步同步Deterministic Lockstep)
- 2）Bucket Synchronization(樂觀幀鎖定)
- 3）鎖步同步協(xié)議 Lockstep protocol
- （1）Deterministic Lockstep存在的問題：
- （2）鎖步同步協(xié)議 Lockstep protocol對lookahead cheat類型的外掛針對
- （3）主要流程
- （4）鎖同步的缺點
- （5）異步Lockstp的提出（asynchronous Synchronization lockstep）
- 4）RTS中的Lockstep（優(yōu)化版的鎖步協(xié)議[9]）
- 5）Pipelined Lockstep protocol（流水線操作）
- 6）TimeWarp（解決Pipelined Lockstep protocol的狀態(tài)沖突與突發(fā)的高延遲問題）
- 7）Lockstep與"幀"同步
- 8）Lockstep小結(jié)
- 9）參考文獻(xiàn)
- 四、狀態(tài)同步的發(fā)展歷程與基本原理（上）
- 1）.雷神之錘與快照同步 （Quake and Snapshot）
- 2）星際圍攻：部落中的網(wǎng)絡(luò)架構(gòu) （The TRIBES Engine Networking Model）
- 3）客戶端預(yù)測與回滾（Client-side prediction and Rollback）
- 4）事件鎖定與時鐘同步 (Event Locking and Clock Synchronization)
- 5）插值技術(shù)（Interpolation and Extrapolation ）
- ）參考文獻(xiàn)
- 五、狀態(tài)同步的發(fā)展歷程與基本原理（下）
- 6）延遲補(bǔ)償（Lag Compensation）
- 7）跟隨狀態(tài)同步（自譯）（Trailing state synchronization）
- 8）狀態(tài)同步框架的演變
- 9）守望先鋒與ECS架構(gòu)
- 1）守望先鋒的游戲架構(gòu)和網(wǎng)絡(luò)同步的實現(xiàn)方式
- 2）演講內(nèi)容介紹
- 3）守望網(wǎng)絡(luò)同步在gameplay層要解決的問題
- （1）玩家移動
- （2）技能行為
- （3）命中預(yù)測
- 4）為了增強(qiáng)玩家的游戲體驗，游戲還對不同ping的玩家進(jìn)行了邏輯的調(diào)整
- 5）守望先鋒狀態(tài)同步的實現(xiàn)
- 6）拋開面對對象模型，使用了面對數(shù)據(jù)編程-》突破難點：控制System 運作的次序
- 10）狀態(tài)同步歷史發(fā)展總結(jié)（按時間段來）
- 1）前情提要
- 2）在Quake誕生前
- 3）Quake誕生
- 4）現(xiàn)在的狀態(tài)同步到底指什么呢？
- 11）文獻(xiàn)
- 六、物理同步
- 1）概念與理解
- 2）問題與解決方案
- （1）前提
- （2）難點
- （3）首先談?wù)勎锢硪娴牟淮_定性
- （4）即網(wǎng)絡(luò)同步的誤差是如何被物理模擬迅速放大的
- （5）總結(jié)
- 3）參考資料
- 七、優(yōu)化技術(shù)總結(jié)
一、網(wǎng)絡(luò)同步概念理解
- 舉例：
比如說用戶A用他的手機(jī)點擊按鈕注冊了一個QQ賬號，那么他的手機(jī)號等個人信息就會被存儲到服務(wù)器上面，這就是一個數(shù)據(jù)同步的過程。在這個過程中，數(shù)據(jù)由A的手機(jī)流向了QQ的官方服務(wù)器。對于游戲來說，其實原理也是一樣，不過由于游戲中玩家關(guān)注的是游戲的視覺效果，所以我們不僅要同步數(shù)據(jù)，還要同步表現(xiàn)。可以簡單認(rèn)為，網(wǎng)絡(luò)同步 = 數(shù)據(jù)同步+表現(xiàn)同步，數(shù)據(jù)同步是后端操作，而表現(xiàn)同步就是讓前端對后端同步過來的數(shù)據(jù)進(jìn)行進(jìn)一步的處理從而達(dá)到表現(xiàn)上的一致。
不過一般Web服務(wù)器只是單純的從服務(wù)器向客戶端進(jìn)行數(shù)據(jù)同步，不會把其他客戶端的數(shù)據(jù)都發(fā)給你。而在游戲里面，你需要讓N個客戶端的顯示看起來一模一樣（由于網(wǎng)絡(luò)延遲，同一時刻不可能完全一樣），所以需要把其他玩家的一些數(shù)據(jù)也發(fā)給你，不能說A玩家跳了一下，B玩家看到A卻趴下了，那樣游戲就沒法玩了。
高及時性：
然而，前面我們還忽略了一個游戲中非常重要的需求（尤其是在MMO、FPS這種類型的網(wǎng)游中）——那就是實時性。你可以容忍微信點進(jìn)去一個文章要花2秒鐘，但是你不可能接受你的子彈要2秒后才打到敵人。實際上，在各種電子競技里面，0.1秒的延遲就足以讓整個游戲的局勢發(fā)生逆轉(zhuǎn)。像瀏覽器這種頁面顯示都吞吞吐吐的應(yīng)用，如何用他流暢的玩FPS和MOBA呢？（關(guān)于云游戲這里先不談）。可以認(rèn)為 網(wǎng)絡(luò)同步 = 實時的多端數(shù)據(jù)同步+實時的多端表現(xiàn)同步。
二、網(wǎng)絡(luò)架構(gòu)與傳統(tǒng)同步
1）網(wǎng)絡(luò)游戲架構(gòu)的發(fā)展
- P2P架構(gòu)：Packet Server
以某個客戶端為Host主機(jī)（或叫做ListenServer）的CS架構(gòu)），這樣的架構(gòu)不需要單獨都維護(hù)一個服務(wù)器，任何一個客戶端都可以是Sever，能夠比較方便的支持局域網(wǎng)內(nèi)對戰(zhàn)，也能節(jié)省服務(wù)器的運行與開發(fā)成本。不過，雖說也是CS架構(gòu)，如果Host主機(jī)不做任何server端的校驗邏輯，那么其本質(zhì)上還是P2P模型，只不過所有的客戶端可以把消息統(tǒng)一發(fā)送到一個IP，Host再進(jìn)行轉(zhuǎn)發(fā)，這種方式我們稱其為Packet Server。
- 主流架構(gòu)
后來一些游戲團(tuán)隊（比如id software）又對CS架構(gòu)做了進(jìn)一步調(diào)整，先是將大部分的邏輯處理移到服務(wù)器上（服務(wù)器可能是一個獨立的無窗口的后臺程序），客戶端只負(fù)責(zé)渲染。隨后為了對抗網(wǎng)絡(luò)延遲提升客戶端的流暢性，又把一部分邏輯交回給客戶端本地預(yù)執(zhí)行，最終成為很多經(jīng)典游戲和引擎的架構(gòu)方式
- 多點服務(wù)器（鏡像服務(wù)器模型）
這種模型提供了多個服務(wù)器的拷貝，避免單點崩潰影響到所有玩家的問題。類似CDN，玩家還可以選擇就近的服務(wù)器進(jìn)行通信，降低了通信延遲。不過，這種方式增加了服務(wù)器的租用和維護(hù)成本，在后續(xù)的游戲網(wǎng)絡(luò)架構(gòu)中并沒有被大量使用，倒是WEB服務(wù)器廣泛采用這種模型并不斷將其發(fā)揚(yáng)光大。
- 按照業(yè)務(wù)邏輯區(qū)分單獨的服務(wù)器
再后來，游戲服務(wù)器架構(gòu)不斷發(fā)展。游戲存儲負(fù)載和網(wǎng)絡(luò)連接負(fù)載隨后從邏輯服上拆分出來，形成獨立的服務(wù)；玩家數(shù)量增多后，又將游戲拆分成多個平行世界，出現(xiàn)了分服和跨服；游戲邏輯進(jìn)一步復(fù)雜后，又開始按照功能去劃分成網(wǎng)關(guān)服務(wù)器、場景服務(wù)器、非場景服務(wù)器等。我們今天討論的網(wǎng)絡(luò)同步幾乎都是在邏輯服務(wù)器（基本上無法拆分）上進(jìn)行的，所以后續(xù)的這些架構(gòu)方式與網(wǎng)絡(luò)同步的關(guān)系并不是很大，這里就不再贅述
2）傳統(tǒng)同步面臨的問題
- 停等協(xié)議
網(wǎng)絡(luò)游戲剛出現(xiàn)的時候，大部分還屬于弱交互游戲，可以將其簡單理解為一種回合制游戲。這種游戲采用的同步方式與計算機(jī)網(wǎng)絡(luò)中的停等協(xié)議（stop-and-wait-type）非常相似，是一種很自然也很簡單的同步模型。不過由于當(dāng)時網(wǎng)絡(luò)同步并沒有形成體系，所以這種同步方式也沒有名字。在局域網(wǎng)盛行以及玩家數(shù)量較少的條件下，這種同步方式與架構(gòu)都是可行的。
不過隨著游戲的種類和玩法復(fù)雜性的提升，面對的問題也接踵而來。
1）在CS架構(gòu)下邏輯在客戶端執(zhí)行還是在服務(wù)器執(zhí)行？如果邏輯都在服務(wù)器執(zhí)行，那么客戶端的操作都會被發(fā)送到服務(wù)器運算，服務(wù)器計算出結(jié)果后通知客戶端，客戶端拿到結(jié)果后再做表現(xiàn)，這樣的好處是所有的邏輯由服務(wù)器處理和驗證，客戶端無法作弊，但壞處是會造成客戶端的資源被浪費，服務(wù)器運算壓力過大。如果邏輯在各個客戶端執(zhí)行，那么玩家可以在本地計算后再把本地得到的結(jié)果告知服務(wù)器，服務(wù)器只進(jìn)行簡單的轉(zhuǎn)發(fā)，這樣的好處是玩家的本地表現(xiàn)很流暢，但壞處是很容易在本地進(jìn)行作弊。而對于P2P架構(gòu)，反作弊更是一個嚴(yán)重的問題，我連一個權(quán)威服務(wù)器都沒有，根本無法驗證其他客戶端消息的真?zhèn)?#xff0c;怎么知道其他玩家有沒有作弊？
2）我們要發(fā)送什么數(shù)據(jù)來進(jìn)行同步？如果發(fā)送每個對象當(dāng)前的狀態(tài)，那么如果一個游戲里面有大量的角色，就會大規(guī)模的占用網(wǎng)絡(luò)帶寬，造成數(shù)據(jù)擁塞、丟包等等問題。如果發(fā)送玩家指令，那這個指令是要服務(wù)器執(zhí)行還是服務(wù)器轉(zhuǎn)發(fā)？而且對于大型多人在線游戲又沒必要處理所有不相關(guān)的玩家信息，同樣浪費網(wǎng)絡(luò)資源
3）面對日益成熟的計算機(jī)網(wǎng)絡(luò)協(xié)議，我們選擇哪種來進(jìn)行同步？TCP、UDP還是Http？
(這時，游戲開發(fā)者們需要面對“發(fā)什么數(shù)據(jù)”，“在哪計算”，“發(fā)給誰”等細(xì)節(jié)問題，他們開始考慮引入更多的其他相關(guān)領(lǐng)域的技術(shù)（比如計算機(jī)模擬仿真）來解決游戲中的同步問題，網(wǎng)絡(luò)同步概念初見端倪)
未完待續(xù)
3）參考文獻(xiàn)：
[1]WIKI “History of video games”. Available:https://en.wikipedia.org/wiki/History_of_video_games[Accessed: 2020-03-24]
[2]T.A. Funkhouser.”RING: A Client-Server System for Multi-User Virtual Environments“, In Proc. 1995 Available:https://dl.acm.org/doi/pdf/10.1145/199404.199418[Accessed: 2020-03-24]
[3]Eric Cronin, Burton Filstrup Anthony R. Kurc, Sugih Jamin,“An Efficient Synchronization Mechanism for Mirrored Game Architectures”, 2004. Available: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.87.6043&rep=rep1&type=pdf[Accessed:2020-03-24]
三、鎖步同步lockstep（幀同步）
（三的補(bǔ)充幀同步的前提提要）
- 簡介：
最近業(yè)內(nèi)的知名的開發(fā)者，KCP作者——韋易笑老師對國內(nèi)“幀同步”和“狀態(tài)同步”兩個概念的發(fā)展歷史做了說明和解釋，描述了為什么國內(nèi)游戲圈會濫用這兩個詞以及國內(nèi)網(wǎng)絡(luò)同步技術(shù)的發(fā)展簡史
- 幀同步定義：
泛指保證每幀(邏輯幀)輸入一致 - 幀同步實現(xiàn)方法
- 幀同步具體優(yōu)化手段
- 背景介紹
Lockstep就是我們口中常說的“幀同步”。但嚴(yán)格來說，Lockstep并不應(yīng)該翻譯成幀同步，而是——鎖步同步算法。（LockStep由軍事語境引入，用來表示齊步行軍，隊伍中的所有人都執(zhí)行一致的動作步伐）首次引入計算機(jī)領(lǐng)域[4]， - 作用
應(yīng)該是用于計算機(jī)容錯系統(tǒng)，即“使用相同的、冗余的硬件組件在同一時間內(nèi)處理相同的指令，
+目的
從而保持多個CPU、內(nèi)存精確的同步，所以一開始與游戲并沒有任何關(guān)系
1）早期的Lockstep(確定性鎖步同步Deterministic Lockstep)
游戲介紹傳送門
不過，早在1994年，FPS鼻祖Doom就已經(jīng)采用了類似Lockstep的方式進(jìn)行網(wǎng)絡(luò)同步[5]。Doom采用P2P架構(gòu)，每個客戶端本地運行著一個獨立的系統(tǒng)，該系統(tǒng)每0.02秒鐘對玩家的動作 (鼠標(biāo)操作和鍵盤操作，包括前后移動、使用道具、開火等) 采樣一次得到一個 tick command 并發(fā)送給其他所有玩家，每個玩家都緩存來自其他所有玩家的 tick commands，當(dāng)某個玩家收到所有其他玩家的 tick commands 后，他的本地游戲狀態(tài)會推進(jìn)到下一幀。在這里， tick command的采集與游戲的推進(jìn)是相互獨立的。
其實當(dāng)時并沒有Lockstep這個說法，doom的整篇論文里面也沒有出現(xiàn)過這個詞。不過后面概念逐漸清晰后我們會發(fā)現(xiàn)，Doom采用的同步方式就是我們常說的原始版本的Lockstep——“確定性鎖步同步（Deterministic Lockstep）”。
2）Bucket Synchronization(樂觀幀鎖定)
MiMaze介紹傳送門
1999年，Christophe Diot和Laurent Gautier的團(tuán)隊開發(fā)了一款基于互聯(lián)網(wǎng)的頁游——MiMaze，基于傳統(tǒng)的Time Bucket Synchronization[6]他們在發(fā)布的論文里面提出了改進(jìn)后的Bucket Synchronization同步方法[7]。Bucket Synchronization把時間按固定時長劃分為多個Bucket，所有的指令都在Bucket里面執(zhí)行。考慮到網(wǎng)絡(luò)延遲的情況，每個玩家在本地的命令不會立刻執(zhí)行而是會推遲一個時延（該時延的長度約等于網(wǎng)絡(luò)延遲），用來等待其他玩家的Bucket的到來。如果超過延遲沒有到達(dá)，既可以選擇放棄處理，也可以保存起來用于外插值（Extrapolation）或者使用前面的指令重新播放。在這種方式下，每個玩家不需要按照Lockstep的方式嚴(yán)格等待其他玩家的命令在處理，可以根據(jù)網(wǎng)絡(luò)情況順延到后面的bucket再執(zhí)行。Bucket Synchronization可以認(rèn)為是我們常說的“樂觀幀鎖定”
3）鎖步同步協(xié)議 Lockstep protocol
（1）Deterministic Lockstep存在的問題：
1）優(yōu)點：簡單
2）缺點：浮點數(shù)跨平臺的同步問題、玩家數(shù)量增長帶來的帶寬問題以及顯而易見的作弊問題（在P2P架構(gòu)下幾乎沒有任何反作弊能力）
（2）鎖步同步協(xié)議 Lockstep protocol對lookahead cheat類型的外掛針對
1）lookahead cheats定義：比如客戶端A使用了外掛工具，每次都將自己的操作信息推遲發(fā)送，等到看到了別人的決策后再決定執(zhí)行什么（或者假裝網(wǎng)絡(luò)信號不好丟棄第K步的操作，第K+1步再發(fā)送）
2）來源：在2001年，Nathaniel Baughman和Brian Neil Levine在IEEE上發(fā)表了論文，提出鎖步同步協(xié)議 Lockstep protocol [8]來對抗lookahead cheat類型的外掛
（3）主要流程
1）簡介：
這里的Lockstep protocol并不是我們前面提到的Deterministic Lockstep ，相比之前的在第K步（第K個Tick Command間隔）就直接發(fā)送第K+1步的明文操作信息，Lockstep protocol每一步都分兩次發(fā)送信息。
2）大概的流程如下：
①先針對要發(fā)送的明文信息進(jìn)行加密，生成“預(yù)提交單向哈希（secure one-way commitment hash）”并發(fā)送給其他客戶端。
②待本地客戶端接收到所有其他客戶端的第K步預(yù)提交哈希值之后，再發(fā)送自己第K+1步的明文信息
③等到收到所有其他客戶端的第K步明文信息后，本地客戶端會為所有明文信息逐個生成明文哈希并和預(yù)提交的哈希值對比，如果發(fā)現(xiàn)XXX客戶端的明文哈希值和預(yù)提交哈希值不相等，則可以判定該客戶端是外掛。反之，游戲正常向前推進(jìn)。
（4）鎖同步的缺點
缺點：雖然可以對抗外掛，但是很明顯帶來了帶寬以及性能的浪費，而且網(wǎng)絡(luò)條件好的客戶端會時刻受到網(wǎng)絡(luò)差的客戶端的影響。
（5）異步Lockstp的提出（asynchronous Synchronization lockstep）
- 概念
大體的思路是利用玩家角色的SOI（Spheres of Influence，和AOI概念差不多），兩個玩家如果相距很遠(yuǎn)互不影響，就采用本地時鐘向前推進(jìn)（非Lockstep方式同步），如果互相靠近并可能影響到對方就變回到嚴(yán)格的LockStep同步，這里并不保證他們的幀序列是完全一致的。
4）RTS中的Lockstep（優(yōu)化版的鎖步協(xié)議[9]）
- 來源
2001的GDC大會上，“帝國時代”的開發(fā)者M(jìn)ark Terrano和Paul Bettner針對RTS游戲提出了優(yōu)化版的鎖步協(xié)議[9] - 目的：
一是游戲中可能發(fā)生位置變化的角色非常多，必須要合理的減少網(wǎng)絡(luò)同步帶寬，
二是玩家對同步頻率極為敏感，每一秒的疏忽都可能影響局勢。 - 概念
（1）首先保持每一步只同步玩家的操作數(shù)據(jù)，然后對當(dāng)前的所有命令延遲兩幀執(zhí)行的方法來對抗延遲。
（2）具體來說，就是第K步開始檢測到本地命令后會推遲到第K+2步進(jìn)行發(fā)送和執(zhí)行，K+1步收集到的其他客戶端命令會推遲到K+3步去執(zhí)行，每K步執(zhí)行前會去判斷本地是否有前兩步的命令，如果有就繼續(xù)推進(jìn)。
（關(guān)于具體的推進(jìn)策略，論文里面寫的不是很清楚，這里加入了作者自己的判斷）
- 為避免高性能機(jī)器受低性能機(jī)器的影響而變“卡“做的優(yōu)化
（1）“帝國時代”里面每一步（稱為一個turn）的長度是可以調(diào)整的，并且完全與渲染分開處理。每個客戶端會根據(jù)自身的機(jī)器性能與網(wǎng)絡(luò)延遲情況來動態(tài)調(diào)整步長時間，
（2）如果性能優(yōu)良但是延遲高就會拉長每個turn的時間（多出的時間用于正常進(jìn)行多個幀的渲染以及Gameplay的處理，雖然可能有誤差），
（3）如果性能差但是網(wǎng)絡(luò)正常就會把大部分的時間用于每個turn的渲染，在這種條件下每個客戶端相同的turn執(zhí)行的本地時間雖然不同，但是執(zhí)行的內(nèi)容是完全一致的。
5）Pipelined Lockstep protocol（流水線操作）
- 來源
2003年，Ho Lee、Eric Kozlowski等人對Bucket synchronization、Lockstep protocol等協(xié)議進(jìn)一步分析并針對存在的缺點進(jìn)行優(yōu)化，提出了Pipelined Lockstep protocol[10]。 - 起因：
只有當(dāng)前玩家的指令行為不與其他人產(chǎn)生沖突，就可以連續(xù)的發(fā)送的自己的指令而不需要等待其他人的消息。 - 舉例
舉個例子，假如一個游戲只有7個格子，玩家A和B分別站在左右兩邊，每次的指令只能向前移動一格。那么A和B至少可以連續(xù)發(fā)送三個指令信息而不需要等待對面玩家的數(shù)據(jù)到來。 - 題外話
Pipelined Lockstep protocol基于Lockstep protocol，為了防止cheatahead外掛同樣需要提前發(fā)送hash，這種操作同步、不等待超時玩家的確定性鎖步的特性逐漸成為“Lockstep”的標(biāo)準(zhǔn)，被廣泛應(yīng)用于網(wǎng)絡(luò)同步中。
6）TimeWarp（解決Pipelined Lockstep protocol的狀態(tài)沖突與突發(fā)的高延遲問題）
-
來源
TimeWarp原本是指科幻小說中的時間扭曲，其實早在1982年就被D Jefferson等人引入計算機(jī)仿真領(lǐng)域[11]，后續(xù)又被Jeff S. Steinrnan進(jìn)行優(yōu)化和調(diào)整[6][12]。 -
概念
TimeWarp算法基本思路是多個物體同時進(jìn)行模擬，當(dāng)一個物體收到了一個過去某個時刻應(yīng)該執(zhí)行的事件時，他應(yīng)該回滾到那個時刻的狀態(tài)，并且回滾前面所有的行為與狀態(tài)。 -
TimeWarp對于PipleLined的優(yōu)化
前面提到的Pipelined Lockstep protocol可以流暢的處理玩家互相不影響的情況，但是卻沒有很好的解決狀態(tài)沖突與突發(fā)的高延遲問題。參考TimeWrap這種思路，我們可以將本地執(zhí)行過的所有操作指令進(jìn)行保存行成一個快照（Snapshot），本地按照Pipelined Lockstep protocol的規(guī)則進(jìn)行推進(jìn)，如果后期收到了產(chǎn)生沖突的指令，我們可以回滾到?jīng)_突指令的上一個狀態(tài)，然后把沖突后續(xù)執(zhí)行過的事件全部取消并重新將執(zhí)行正確的指令。這樣如果所有玩家之間沒有指令沖突，他們就可以持續(xù)且互不影響的向前推進(jìn)，如果發(fā)生沖突則可以按照回退到發(fā)生沖突前的狀態(tài)并重新模擬，保持各個端的狀態(tài)一致。
7）Lockstep與"幀"同步
-
關(guān)于幀
前面提到了那么多l(xiāng)ockstep的算法，但好像沒有一個算法使用到“幀”這個概念。其實“幀同步”屬于一個翻譯上的失誤，寬泛一點來講“幀同步”是指包含各種變形算法的Lockstep，嚴(yán)格來講就是指最基本的Deterministic Lockstep。我猜測國內(nèi)在引入這個概念的時候已經(jīng)是2000年以后（具體時間沒有考證），lockstep算法已經(jīng)有很多變形，時間幀的概念也早已誕生，所以相關(guān)譯者可能就把“l(fā)ockstep”翻譯成了“幀同步”。當(dāng)然也可能是引入的時候翻譯成了“按幀鎖定同步”，后來被大家以簡化的方式（幀同步）傳遞開來。但不管怎么說，“幀”在實際應(yīng)用中更多的是指畫面渲染的頻率，lockstep里面的“step”概念要更寬泛一些才是。 -
邏輯幀和渲染幀
了解游戲的朋友，都知道游戲是有幀率（FPS）的，每一幀都會運行相當(dāng)復(fù)雜的運算（包括邏輯和渲染），如果運算規(guī)模達(dá)到一定程度就會拉長這一幀的時間，幀率也就會隨之下降。所有影視作品的畫面都是由一張張圖構(gòu)成的，每一個畫面就是一幀，一秒能放多少個畫面，就是有多少幀。在游戲里面，渲染器會不停的向渲染目標(biāo)輸出畫面，并在幀與幀之間游戲處理各種邏輯，邏輯會改變游戲世界對象的行為，這些行為又會影響游戲畫面的變化，這就是游戲的核心框架。早期的lockstep里面渲染和邏輯都是放在一個幀里面去處理的，這樣一旦命令受到網(wǎng)絡(luò)延遲的影響，玩家本地就會卡在一個畫面直到消息的到來。 -
為了解決邏輯幀和渲染幀相互影響的問題
為了解決這個問題，有一些游戲會將邏輯和渲染分開處理（分為邏輯幀和渲染幀），
邏輯幀每隔固定的時間去處理所有邏輯事件。在不是嚴(yán)格鎖幀的情況下，你本地即使沒有收到網(wǎng)絡(luò)數(shù)據(jù)也可以在繼續(xù)執(zhí)行其他的邏輯并維持高頻率的渲染（正在移動的對象不會由于短暫的延遲而靜止不動）。這里面的邏輯幀就是lockstep里面的“Step”，也可以叫做“turn”，“bucket”或者“步”。
8）Lockstep小結(jié)
-
早期幀是采用客戶端內(nèi)在的心跳按一定間隔的心跳前進(jìn)
早期lockstep被廣泛用于局域網(wǎng)游戲內(nèi)（延遲基本可以保持在50ms以內(nèi)），所以這種策略是很有效的。lockstep每個回合的觸發(fā)，并不是由收到網(wǎng)絡(luò)包驅(qū)動，也不是由渲染幀數(shù)驅(qū)動（當(dāng)然渲染幀率穩(wěn)定的話也可以以幀為單位，每N幀一個回合），而是采用客戶端內(nèi)在的時鐘穩(wěn)定按一定間隔（ 比如100ms） 的心跳前進(jìn)。游戲的一開始，玩家在本地進(jìn)行操作，操作指令會被緩存起來。在回合結(jié)束前（網(wǎng)絡(luò)延遲在50ms以內(nèi)），我們會收到所有其他客戶端的指令數(shù)據(jù)，然后和前面緩存的指令一同執(zhí)行并推進(jìn)到下一個回合。如果玩家在一個回合開始到50ms（網(wǎng)絡(luò)延遲的一半）都沒有任何操作，我們可以認(rèn)為玩家發(fā)出了一個Idle指令，打包發(fā)給其他客戶端[13][14]。
-
鎖幀做回放系統(tǒng)容易的問題
換個角度來看，假如一場游戲持續(xù)了20分鐘，不考慮延遲的情況下整場游戲就是12000個回合（所有客戶端都是如此）。現(xiàn)在我們反過去給每個回合添加指令，確保每個回合都收集到所有玩家的指令，那么就可以嚴(yán)格保證所有客戶端每個回合的表現(xiàn)都是一樣的。假如我們再把這些指令都存儲起來，那么就推演出整場比賽，這也是為什么lockstep為什么做回放系統(tǒng)很容易。 -
對于lockstep為什么要發(fā)送指令而不是狀態(tài)的原因
至于lockstep為什么要發(fā)送指令而不是狀態(tài)，其實是與當(dāng)時的網(wǎng)絡(luò)帶寬有關(guān)。很多游戲都有明確的人數(shù)限制（一般不超過10個人），玩家在每個回合能做的操作也有限甚至是不操作，這樣的條件下所有玩家的指令一共也占用不了多少帶寬。如果換成同步每個角色的狀態(tài)數(shù)據(jù)，那么數(shù)據(jù)量可能會膨脹10倍不止。從原則上說，鎖步數(shù)據(jù)既可以是游戲角色的狀態(tài)信息也可以是玩家的操作指令，只不過由于各種原因沒有采取狀態(tài)數(shù)據(jù)罷了。在下一章，我還會對狀態(tài)同步做進(jìn)一步的講解，他與lockstep的發(fā)展是相輔相成的，也不是網(wǎng)上常說的那種對立關(guān)系。
- 當(dāng)鎖幀的時候，網(wǎng)絡(luò)條件較差的客戶端很容易影響其他玩家的體驗的解決辦法
①使用樂觀幀鎖定
②把渲染與同步邏輯拆開，客戶端預(yù)執(zhí)行
③指令流水線化
④操作回滾，關(guān)于回滾還有很多細(xì)節(jié)[16][18] - 鎖幀的客戶端運算結(jié)果誤差導(dǎo)致的問題
其次，lockstep的另一個問題就是很難保證命令一致的情況下，所有客戶端的計算結(jié)果完全一致，只要任何一個回出現(xiàn)了一點點的誤差就可能像蝴蝶效應(yīng)一樣導(dǎo)致兩個客戶端后面的結(jié)果截然不同 - 鎖幀的題外話
這個問題聽起來容易，實際上執(zhí)行起來卻有很多容易被忽略的細(xì)節(jié)，比如RPC的時序，浮點數(shù)計算的偏差，容器排序的不確定性，隨機(jī)數(shù)值計算不統(tǒng)一等等。浮點數(shù)的計算在不同硬件（跨平臺更是如此）上很難保持一致的，可以考慮轉(zhuǎn)換為定點數(shù)，隨機(jī)計算保持各個端的隨機(jī)種子一定也可以解決，但是具體實現(xiàn)起來可能還有很多問題，需要踩坑之后才能真正解決。
9）參考文獻(xiàn)
[1]WIKI “History of video games”. Available:https://en.wikipedia.org/wiki/History_of_video_games[Accessed: 2020-03-24]
[2]T.A. Funkhouser.”RING: A Client-Server System for Multi-User Virtual Environments“, In Proc. 1995 Available:https://dl.acm.org/doi/pdf/10.1145/199404.199418[Accessed: 2020-03-24]
[3]Eric Cronin, Burton Filstrup Anthony R. Kurc, Sugih Jamin,“An Efficient Synchronization Mechanism for Mirrored Game Architectures”, 2004. Available: citeseerx.ist.psu.edu/v[Accessed:2020-03-24]
[4]WIKI “Lockstep (computing)”. Available: https://en.wikipedia.org/wiki/Lockstep_(computing)[Accessed: 2020-03-24]
[5]JMP van Waveren, “The DOOM III Network Architecture” ,2006. Available:http://fabiensanglard.net/doom3_documentation/The-DOOM-III-Network-Architecture.pdf[Accessed: 2020-03-24]
[6]Jeff S. Steinrnan,“BREATHING TIME WARP” May 1993. Available:https://dl.acm.org/doi/pdf/10.1145/174134.158473[Accessed:2020-03-24]
[7]Christophe DIOT, Laurent GAUTIER, “A Distributed Architecture for Multiplayer Interactive Applications on the Internet”, IEEE, 1999. Available: https://www.cs.ubc.ca/~krasic/cpsc538a-2005/papers/diot99distributed.pdf[Accessed: 2020-03-24]
[8]Mark Terrano,Paul Bettner “Network Programming in Age of Empires and Beyond” GDC 2001. Available:https://zoo.cs.yale.edu/classes/cs538/readings/papers/terrano_1500arch.pdf[Accessed: 2020-03-24]
[9]Nathaniel E. Baughman, Brian Neil Levine, “Cheat-Proof Playout for Centralized and Distributed Online Games”, IEEE INFOCOM, 2001. Available: http://forensics.umass.edu/pubs/baughman.infocom01.pdf[Accessed: 2020-03-24]
[10]Ho Lee, Eric Kozlowski, Scott Lenker, Sugih Jamin, “Multiplayer Game Cheating Prevention With Pipelined Lockstep Protocol”, 2002. Available: http://www.ekozlowski.com/assets/multiplayer-game-cheating-prevention.pdf[Accessed: 2020-03-24]
[11]Dacid Jefferson,Henry Sowizral "Fast concurrent simulation using the time wrap mechanism " 1982. Available: https://www.rand.org/content/dam/rand/pubs/notes/2007/N1906.pdf[Accessed: 2020-03-24]
[12]J. S. Steinman, J. W. Wallace, D. Davani, and D. Elizandro. “Scalable distributed military simulations using the SPEEDES object-oriented simulation framework”. In Proc. of Object-Oriented Simulation Conference (OOS’98), pages 3–23, 1998.
其他參考資料：
[13]云風(fēng) “l(fā)ockstep網(wǎng)絡(luò)游戲同步方案” Available:https://blog.codingnow.com/2018/08/lockstep.html
[14]Skywind “再談網(wǎng)游同步技術(shù)” Available: http://www.skywind.me/blog/archives/1343#more-1343
[15]DonaldW “網(wǎng)絡(luò)游戲同步技術(shù)概述” Available:https://zhuanlan.zhihu.com/p/56923109
[16]Gordon “幀同步聯(lián)機(jī)戰(zhàn)斗(預(yù)測，快照，回滾)” Available:
https://zhuanlan.zhihu.com/p/38468615
[17]zhepama "幀同步的相關(guān)問題"Available:http://www.igiven.com/dotnet/lock-step/
[18]kisence"關(guān)于幀同步和網(wǎng)游游戲開發(fā)的一些心得"Available:https://www.kisence.com/2017/11/12/guan-yu-zheng-tong-bu-de-xie-xin-de/
[19]Glenn Fiedler “Deterministic Lockstep” Available:https://gafferongames.com/post/deterministic_lockstep/
[20]Qing Wei Lim “How do multiplayer games sync their state” Available:https://medium.com/@qingweilim/how-do-multiplayer-games-sync-their-state-part-1-ab72d6a54043
[21]treeform "Don’t use Lockstep in RTS games"Available: https://medium.com/@treeform/dont-use-lockstep-in-rts-games-b40f3dd6fddb
[22]Maksym Kurylovych “Lockstep protocol” Available: http://ds.cs.ut.ee/courses/course-files/Report%20-2.pdf
[23] Glenn Fiedler, “What Every Programmer Needs To Know About Game Networking A short history of game networking techniques”, 2010. Available: https://gafferongames.com/post/what_every_programmer_needs_to_know_about_game_networking/
四、狀態(tài)同步的發(fā)展歷程與基本原理（上）
- 背景
在二十年前，相比于使用幀同步（為了方便描述，后續(xù)的文章中以幀同步代替Lockstep）還是狀態(tài)同步，開發(fā)者們更關(guān)心的是網(wǎng)絡(luò)架構(gòu)的實現(xiàn)方式（P2P/CS)。換句話講，在當(dāng)時業(yè)內(nèi)看來，P2P架構(gòu)的同步模型雖然減少了延遲，但由于作弊、跨平臺、難以維護(hù)大型網(wǎng)絡(luò)游戲等問題，人們更希望用CS架構(gòu)來取代P2P。同時，開發(fā)者們雖然可以繼續(xù)在CS架構(gòu)下使用邏輯比較簡潔的幀同步，但有不少開發(fā)者都認(rèn)為剛剛誕生的狀態(tài)同步貌似更符合CS架構(gòu)的同步理念。
- 狀態(tài)同步與幀同步的差異
1）數(shù)據(jù)格式與內(nèi)容
2）邏輯的計算位置
3）是否有權(quán)威服務(wù)器等等
1）.雷神之錘與快照同步 （Quake and Snapshot）
-
快照的含義
快照是一個通用的行業(yè)術(shù)語，即在任何給定時刻記錄設(shè)備的狀態(tài)并在設(shè)備出現(xiàn)故障時進(jìn)行還原。快照技術(shù)常用于計算機(jī)的各種存儲系統(tǒng)，例如邏輯卷管理、數(shù)據(jù)庫、文件系統(tǒng)等。在游戲領(lǐng)域中，快照的含義更像是照片一樣，將當(dāng)前場景所有的信息保存起來。嚴(yán)格來說，快照同步應(yīng)該屬于狀態(tài)同步的前身，雖然思想相似但是具體實現(xiàn)卻有不小的差異。 -
雷神之錘游戲背景
1996年，在doom發(fā)行不久后，Id software就公開了新作——雷神之錘（Quake）。在Quake里他們舍棄了之前的P2P而改用CS架構(gòu)，同時也舍棄了lockstep的同步方式。新的架構(gòu)下，客戶端就是一個純粹的渲染器(稱為Dumb Client)，每一幀玩家所有的操作信息都會被收集并發(fā)送到服務(wù)器，然后服務(wù)器將計算后的結(jié)果壓縮后發(fā)給客戶端來告知他們有哪些角色可以顯示，顯示在什么位置上。
照片講解
上述的這個過程就是我們所說的快照同步，即服務(wù)器每幀接受客戶端的輸入來計算整個世界的狀態(tài)，然后將結(jié)果快照發(fā)送給所有客戶端。Quake這里所謂的快照，就是把整個游戲世界里面所有對象的狀態(tài)做一次臨時保存（他更強(qiáng)調(diào)的是對象的可視化狀態(tài)，比如位置和旋轉(zhuǎn)等）。通過這個快照，我們可以還原出這一刻世界的狀態(tài)應(yīng)該是什么樣子的。
- 與鎖幀的不同
Quake運行時，邏輯幀率與渲染幀率是保持一致的。由于所有的核心邏輯都是在服務(wù)器進(jìn)行，所以也不需要通過鎖步來避免客戶端不同步的問題，只要在收到服務(wù)器消息后執(zhí)行渲染就好了。當(dāng)然，對于性能以及網(wǎng)絡(luò)環(huán)境較差的玩家來說，游戲體驗仍然很糟糕。因為你按下一個按鈕后，可能很長時間都沒有反應(yīng)，當(dāng)收到服務(wù)器的快照消息后，你可能已經(jīng)被網(wǎng)絡(luò)好的玩家擊殺了。
這里借用守望先鋒的GDC分享展示快照同步
2）星際圍攻：部落中的網(wǎng)絡(luò)架構(gòu) （The TRIBES Engine Networking Model）
- Quake和Doom的源碼分享
IdSoftware自2012年以來已經(jīng)陸續(xù)把Quake以及Doom相關(guān)的源碼上傳到了GitHub上面[4]。如果你看過其中Quake的源碼，會發(fā)現(xiàn)整個網(wǎng)絡(luò)的架構(gòu)還是比較簡單清晰的，博主FABIEN SANGLARD就在網(wǎng)上分享了關(guān)于Quake源碼的剖析[5]（還有很多其他項目的源碼剖析）
-
出現(xiàn)的問題
但Quake里面由于客戶端只是一個簡單的渲染器，同步過程中會出現(xiàn)很多明顯的問題，比如延遲過大，客戶端性能浪費，服務(wù)器壓力大等。而其中最明顯的問題就是對帶寬的浪費，對于一個物體和角色比較少的游戲，可以使用快照將整個世界的狀態(tài)都存儲并發(fā)送，但是一旦物體數(shù)量多了起來，帶寬占用就會直線上升。所以，我們希望不要每幀都把整個世界的數(shù)據(jù)都發(fā)過去，而是只發(fā)送那些產(chǎn)生變化的對象數(shù)據(jù)（可以稱為增量快照同步）。更進(jìn)一步的，我們還希望將數(shù)據(jù)拆分的更細(xì)一些，并根據(jù)客戶端的特點來定制發(fā)送不同的數(shù)據(jù)。基于這種思想，《星際部落：圍攻》團(tuán)隊的開發(fā)者們開始對網(wǎng)絡(luò)架構(gòu)進(jìn)行抽象和分層，構(gòu)造出來一套比較完善的"狀態(tài)同步"系統(tǒng)并以此開發(fā)出了Tribe游戲系列。 -
TRIBES ENGINE介紹
The TRIBES Engine可以認(rèn)為是第一個實現(xiàn)狀態(tài)同步的游戲引擎，《星際部落：圍攻》也可以認(rèn)為是第一個比較完美的實現(xiàn)了狀態(tài)同步的游戲。下圖是該引擎的網(wǎng)絡(luò)架構(gòu)[6]：
- 圖片介紹
平臺數(shù)據(jù)包模塊（Platform Packet Module）可以理解成被封裝的Socket模塊，連接管理器（Connection Manager）處理多個客戶端與服務(wù)器的連接，流管理器（Stream Manager）負(fù)責(zé)將具體的數(shù)據(jù)分發(fā)到上面的三個高級管理器。
1）Ghost管理器：負(fù)責(zé)向客戶端發(fā)送需要同步對象的狀態(tài)信息，類似屬性同步。
2）事件管理器：維護(hù)事件隊列，每個事件相當(dāng)于一個的RPC。
3）移動管理器：本質(zhì)上與事件管理器相同，但是由于移動數(shù)據(jù)的需要高頻的捕捉和發(fā)送，所以單獨封裝成一個特殊的管理器。
3）客戶端預(yù)測與回滾（Client-side prediction and Rollback）
- 預(yù)測的出現(xiàn)
《毀滅公爵》是上世紀(jì)90年代一個經(jīng)典的FPS游戲系列，首部作品的發(fā)布時間與Doom幾乎相同，網(wǎng)絡(luò)架構(gòu)也極為相似。在1996年發(fā)布的《毀滅公爵3D》里面，為了提高客戶端的表現(xiàn)與響應(yīng)速度，他放棄了“Dumb客戶端”的方案并首次采用客戶端預(yù)測來進(jìn)行優(yōu)化（這里主要指移動預(yù)測）[7]。即在服務(wù)器確認(rèn)輸入并更新游戲狀態(tài)之前，讓客戶端立即對用戶輸入進(jìn)行本地響應(yīng)。由于這種方式可以大大的降低網(wǎng)絡(luò)延遲所帶來的困擾，很快的Quake也開始參考對網(wǎng)絡(luò)架構(gòu)進(jìn)行的大刀闊斧的修改。在1997年發(fā)布的更新版本QuakeWorld里面[8][9]，Quake添加了對互聯(lián)網(wǎng)對戰(zhàn)的支持以及客戶端預(yù)測等新的內(nèi)容。
-
預(yù)測備注
關(guān)于預(yù)測，其實就是本地先執(zhí)行，所以并不需要什么特別的算法，反倒是預(yù)測后的客戶端與服務(wù)器的同步處理有很多值得優(yōu)化的地方。由于玩家的行為是沒辦法完全預(yù)測的，所以你不知道玩家會在什么時候突然停下或者轉(zhuǎn)彎，所以經(jīng)常會發(fā)生預(yù)測失敗的情況。 -
若客戶端復(fù)測與服務(wù)器不一致
1）
在沒有時間戳的條件下，收到了一條過時的服務(wù)器位置數(shù)據(jù)。你在本地的行為相比服務(wù)器是超前的，假如你在time=10ms的和time=50ms時候分別發(fā)送了一條指令。由于網(wǎng)絡(luò)延遲的存在，當(dāng)你已經(jīng)執(zhí)行完第二個指令的時候才收到服務(wù)器對第一條指令的位置同步。很明顯，我們不應(yīng)該讓過時的服務(wù)器數(shù)據(jù)來糾正你當(dāng)前的邏輯。解決方法就是在每個指令發(fā)出的時候帶上他的時間戳，這樣客戶端收到服務(wù)器反饋的時候就知道他處理的是哪條指令信息。
2）
假如我們在指令里面添加了時間戳的信息，并收到了一條過時的服務(wù)器位置數(shù)據(jù)。在上一篇文章里我們提到了TimeWarp算法，即當(dāng)一個對象收到了一個過去某個時刻應(yīng)該執(zhí)行的事件時，他應(yīng)該回滾到那個時刻的狀態(tài)，并且回滾前面所有的行為與狀態(tài)（包括取消之前行為所產(chǎn)生的事件）。這個時候我們可以用類似的方法在本地進(jìn)行糾正，大體的方案就是把玩家本地預(yù)執(zhí)行的指令都記錄好時間戳并存放到一個MOVE BUFFER列表里（類似一個滑動窗口）。如果服務(wù)器的計算結(jié)果與你本地預(yù)測相同，可以回復(fù)你一個ACKMOVE。如果服務(wù)器發(fā)現(xiàn)你的某個移動位置有問題時，會把該指令的時間戳以及正確的位置打包發(fā)給你。當(dāng)你收到ACKMOVE的時候，你可以把MOVE BUFFER里面的數(shù)據(jù)從表里面移除，而當(dāng)你收到錯誤糾正信息時就需要本地回滾到服務(wù)器指定的位置同時把錯誤時刻后面MOVE BUFFER里面的指令重新執(zhí)行一遍。這里讀者可能會產(chǎn)生一個疑問——為什么不直接拉回？因為這時候他想糾正的是之前的錯誤而不是現(xiàn)在的錯誤，如果簡單的拉回就會讓你覺得被莫名其妙的拉回到以前的一個位置。同時，考慮到已經(jīng)在路上的指令以及后續(xù)你要發(fā)送的預(yù)測指令，會讓服務(wù)器后續(xù)的校驗與糾正變得復(fù)雜且奇怪，具體流程細(xì)節(jié)可以參考下圖。另外，Gabriel Gambetta博主在他的文章中，也對這種情況進(jìn)行了簡單的分析[10]。
(意思還是被拉回去，但是不是拉回去開始的位置，而是拉回去上個包的位置)
- 關(guān)于TimeWarp算法的補(bǔ)充
Timewarp技術(shù)最早出現(xiàn)于仿真模擬中[11]，我們可以認(rèn)為這些仿真程序中采用的是“以事件驅(qū)動的幀同步”。也就是說，給出一個指令，他就會產(chǎn)生并觸發(fā)多個事件，這些事件可能進(jìn)而觸發(fā)更多的事件來驅(qū)動程序，同理取消一個過去發(fā)生的事件也需要產(chǎn)生一個新的取消事件才行。這樣造成的問題就是回滾前面的N個操作，就需要產(chǎn)生N個新的對抗事件，而且這N個事件還需要發(fā)送到所有其他的客戶端執(zhí)行。如果這N個事件又產(chǎn)生了新的事件，那么整個回滾的操作就顯得復(fù)雜了很多。換成前面移動的例子來解釋一下，就是客戶端收到服務(wù)器的糾正后，他會立刻發(fā)送回滾命令告訴（P2P架構(gòu)下）所有其他客戶端，我要取消前面的操作，然后其他客戶端在本地也執(zhí)行回滾。而在如今的CS架構(gòu)狀態(tài)同步的方式下，服務(wù)器可能早就拒絕了客戶端的不合法行為，所以并不需要處理回滾（同理，其他客戶端也是）。所以嚴(yán)格來說，TimeWarp技術(shù)以及優(yōu)化后的BreathTimeWarp技術(shù)[12]都是針對“以事件驅(qū)動的幀同步”，并不能與預(yù)測回滾這套方案完全等價。當(dāng)然，隨著時間的推移，很多概念也變的逐漸寬泛一些，我們平時提到的時間回溯TimeWarp技術(shù)大體上與快照回滾是一個意思的。
4）事件鎖定與時鐘同步 (Event Locking and Clock Synchronization)
-
事件鎖定的出現(xiàn)
1997年，Jim Greer與Zack Booth Simpson在開發(fā)出了他們第一款基于CS架構(gòu)的RTS游戲——”NetStorm：Island at war“。隨后在發(fā)布的文章中又提出了“事件鎖定”這一概念[13]，相比幀同步會受到其他客戶端延遲的影響，事件鎖定是基于事件隊列嚴(yán)格按序執(zhí)行的，客戶端只管發(fā)消息然后等待服務(wù)器的響應(yīng)即可，其他時候本地正常模擬，不需要等待。在目前常見的游戲中，我們很少會聽說到事件鎖定這種同步方式，因為事件鎖定的本質(zhì)就是通過RPC產(chǎn)生事件從而進(jìn)行同步（也就是排除屬性同步的狀態(tài)同步）。事件鎖定在CS架構(gòu)上是非常自然的，相比幀同步，可以定義并發(fā)送更靈活的信息，也不必再擔(dān)心作弊的問題。 -
以時間同步來糾正服務(wù)器對客戶端的不合法操作
不過，由于事件中經(jīng)常會含有時間相關(guān)的信息（比如在X秒進(jìn)行開火）以及服務(wù)器需要對客戶端的不合法操作進(jìn)行糾正，所以我們需要盡可能的保持客戶端與服務(wù)器的時鐘同步。實現(xiàn)時鐘同步最常見且廣泛的方式就是網(wǎng)絡(luò)時間協(xié)議（Network Time Protocol，簡稱NTP）[14]，NTP屬于應(yīng)用層協(xié)議下層采用UDP實現(xiàn)，1979年誕生以來至今仍被應(yīng)用在多個計算機(jī)領(lǐng)域里，包括嵌入式系統(tǒng)時間、通信計費、Windows時間服務(wù)以及部分游戲等。NTP使用了一種樹狀、半分層的網(wǎng)絡(luò)結(jié)構(gòu)來部署時鐘服務(wù)器，每個UDP數(shù)據(jù)包內(nèi)包含多個時間戳以及一些標(biāo)記信息用來多次校驗與分析，
（備注：整個時鐘同步的具體算法涉及到非常多的細(xì)節(jié)，我們這里只考慮他的時鐘同步算法（其他的內(nèi)容請參考?xì)v年的RFC））
-
詳細(xì)講解
假如一個服務(wù)器與客戶端通信，客戶端在t0向服務(wù)器發(fā)送數(shù)據(jù)，服務(wù)器在t1收到數(shù)據(jù)，t2響應(yīng)并回包給客戶端，最后客戶端在t3時間收到了服務(wù)器的數(shù)據(jù)。
二者的時間差為“θ”，假如往返延遲相同，則有
所以可以將“θ”定義為
將往返延遲相加，那么可以得到一個RTT延遲
當(dāng)然，該操作不會只執(zhí)行一次，客戶端會同時請求多個服務(wù)器，然后對結(jié)果進(jìn)行統(tǒng)計分析、過濾，并從最好的三個剩余候選中估算時間差，然后調(diào)整時鐘頻率來逐漸減小偏移。如果我們的系統(tǒng)對精度要求不是非常高，我們還可以使用簡化版的SNTP(Simple Network Time Protocal），時鐘同步算法與NTP是相同的，不過簡化了一些流程。 -
消除高階的流式時間同步：
不過無論是NTP還是SNTP，對于游戲來說都過于復(fù)雜（而且只能用UDP實現(xiàn)）。因此Jim Greer等人提出了“消除高階的流式時間同步”，流程如下：
- 總結(jié)
上述算法精髓在于丟棄和中間值偏差超過一個標(biāo)準(zhǔn)偏差的數(shù)值。其目的是為了去除TCP中重傳的數(shù)據(jù)包。舉例來說，如果通過TCP發(fā)送了10個數(shù)據(jù)包，而且沒有重傳。這時延遲數(shù)據(jù)將集中在延遲的中位數(shù)附近。假如另一個測試中，如果其中第10個數(shù)據(jù)包被重傳了，重傳將導(dǎo)致這次的采樣在延遲柱狀圖中極右端，處于延遲中位數(shù)兩倍的位置。通過直接去掉超出中位數(shù)一個標(biāo)準(zhǔn)偏差的樣例，可以過濾掉因重傳導(dǎo)致的不準(zhǔn)確樣例。（排除網(wǎng)絡(luò)很差重傳頻繁發(fā)生的情況）
5）插值技術(shù)（Interpolation and Extrapolation ）
- 插值法分類
插值技術(shù)在早期的幀同步就被應(yīng)用到游戲里面了。或者說更早的時候就被應(yīng)用到軍事模擬，路徑導(dǎo)航等場景中。插值分為內(nèi)插值[15]（ interpolation ）以及外插值[16]（extrapolation，或者叫外推法）兩種。
1）內(nèi)插法：
內(nèi)插值是一種通過已知的、離散的數(shù)據(jù)點，在范圍內(nèi)推求新數(shù)據(jù)點的方法（重建連續(xù)的數(shù)據(jù)信息），常見于各種信號處理和圖像處理。在這篇文章中，我們指根據(jù)已知的離散點在一定時間內(nèi)按照一定算法去模擬在點間的移動路徑。內(nèi)插值具體的實現(xiàn)方法有很多，如
2）外插法
外插值，指從已知數(shù)據(jù)的離散集合中構(gòu)建超出原始范圍的新數(shù)據(jù)的方法，也可以指根據(jù)過去和現(xiàn)在的發(fā)展趨勢來推斷未來，屬于統(tǒng)計學(xué)上的概念。與外插值還有一個相似的概念稱為DeadReckoning（簡稱DR），即導(dǎo)航推測。DR是一種利用現(xiàn)在物體位置及速度推定未來位置方向的航海技術(shù)，屬于應(yīng)用技術(shù)方向的概念。DR的概念更貼近游戲領(lǐng)域，即給定一個點以及當(dāng)前的方向等信息，推測其之后的移動路徑，外推的算法也有很多種，
在游戲中，一般按照線性外推或勻變速直線運動推測即可。不過，對于比較復(fù)雜的游戲類型，我們也可以采用三次貝塞爾曲線、向心Catmull-Rom曲線等模擬預(yù)測。
總之，無論是內(nèi)插值還是外插值，考慮到運算的復(fù)雜度以及表現(xiàn)要求，游戲中以線性插值、簡單的多項式插值為主。
3）插值法應(yīng)用
早期的lockstep算法中，在一個客戶端在收到下一幀信息前，為了避免本地其他角色靜止卡頓，會采用外插值來推斷其接下來一小段時間的移動路徑[17][18]。普通DR存在一個問題（參考下圖），t0時刻其他客戶端收到了主機(jī)的同步信息預(yù)測向虛線的方向移動，不過主機(jī)客戶端卻開始向紅色路徑方向移動，等其他客戶端在t1時刻收到同步信息后會被突然拉倒t1’的位置，這造成了玩家不好的游戲體驗。為了解決從預(yù)測位置拉扯到真實位置造成的視覺突變，我們會增加一些相應(yīng)的算法來將預(yù)測對象平滑地移動到真實位置。
在狀態(tài)同步中，由于客戶端每次收到的是其他的角色的位置信息，為了避免位置突變，本地會采用內(nèi)插值來從A點過度到B點。插值的目的很簡單，就是為了保證在同步數(shù)據(jù)到來之前讓本地的角色能有流暢的表現(xiàn)。
）參考文獻(xiàn)
[1]"State Synchronization's Role in High Availability" Available:http://etutorials.org/Networking/Check+Point+FireWall/Chapter+13.+High+Availability/State+Synchronization+s+Role+in+High+Availability/[Accessed:2020-07-17] [2]WIKI, "Check Point VPN-1" Available: https://en.wikipedia.org/wiki/Check_Point_VPN-1[Accessed:2020-07-17] [3]Check Point Documentation, "Synchronizing Connections in the Cluster" Available:https://sc1.checkpoint.com/documents/R80.10/WebAdminGuides/EN/CP_R80.10_ClusterXL_AdminGuide/html_frameset.htm?topic=documents/R80.10/WebAdminGuides/EN/CP_R80.10_ClusterXL_AdminGuide/7288[Accessed:2020-07-17] [4]id-Software,"GitHub Game Source Code" Available:https://github.com/id-Software [Accessed:2020-07-17] [5]FABIEN SANGLARD," FABIEN SANGLARD'S WEBSITE With GameSource Code Analysis " Available:https://fabiensanglard.net/ [Accessed:2020-07-17] [6] Mark Frohnmayer, Tim Gift, "The TRIBES Engine Networking Model or How to Make the Internet Rock for Multi player Games", 1998. Available: https://www.gamedevs.org/uploads/tribes-networking-model.pdf[Accessed:2020-07-17] [7]WIKI, "Client-Side Prediction" Available:https://en.wikipedia.org/wiki/Client-side_prediction [Accessed:2020-07-17] [8]id-Software,"The Quake 2 Networking Data Flow" Available:http://www.gamers.org/dEngine/quake2/Q2DP/Q2DP_Network/Q2DP_Network.html#toc4 [Accessed:2020-07-17] [9]WIKI, "QuakeWorld" Available:https://en.wikipedia.org/wiki/QuakeWorld[Accessed:2020-03-24] [10]Gabriel Gambetta," Client-Server Game Architecture" Available:https://www.gabrielgambetta.com/client-side-prediction-server-reconciliation.html[Accessed:2020-07-17] [11]Dacid Jefferson,Henry Sowizral "Fast concurrent simulation using the time wrap mechanism " 1982.Available: https://www.rand.org/content/dam/rand/pubs/notes/2007/N1906.pdf[[Accessed:2020-07-17] [12]M. Damitio S. J. Turner，"Comparing the Breathing Time Buckets Algorithm and the Time Warp Operating System on a Transputer Architecture” January 1999. Available:https://www.researchgate.net/publication/2763616_Comparing_the_Breathing_Time_Buckets_Algorithm_and_the_Time_Warp_Operating_System_on_a_Transputer_Architecture[Accessed:2020-07-17] [13]Jim Greer, Zack Booth Simpson, "Minimizing Latency in RealTine Strategy Games" Game Progamming Gems 3 chapter 5.1, 2001. [14]]WIKI, "Network Time Protocol" Available:https://en.wikipedia.org/wiki/Network_Time_Protocol[Accessed:2020-07-17] [15]WIKI, "Interpolation" Available:https://en.wikipedia.org/wiki/Interpolation[Accessed:2020-07-17] [16]WIKI, "Extrapolation" Available:https://en.wikipedia.org/wiki/Extrapolation[Accessed:2020-07-17] [17]Jesse Aronson, "Dead Reckoning: Latency Hiding for Networked Games" September 19, 1997.Available:https://www.gamasutra.com/view/feature/131638/dead_reckoning_latency_hiding_for_.php[Accessed:2020-07-17] [18]梁白鷗等,“Dead Reckoning技術(shù)在網(wǎng)絡(luò)游戲中的應(yīng)用” 2007.Available:http://www.arocmag.com/getarticle/?aid=2f665567e92cf534[Accessed:2020-07-17]五、狀態(tài)同步的發(fā)展歷程與基本原理（下）
6）延遲補(bǔ)償（Lag Compensation）
- 背景
2001年，Valve的新作《半條命》發(fā)布，打破了傳統(tǒng)FPS游戲玩法。不久之后，其Mod《反恐精英》更是火遍了全球并作為獨立游戲發(fā)布出去。
- 游戲介紹
由于半條命是基于“QuakeII引擎修改的GoldSrc引擎”開發(fā)，所以游戲同樣采用了CS架構(gòu)以及狀態(tài)同步。不過，為了能達(dá)到他們心中理想的效果，半條命在網(wǎng)絡(luò)同步上做出了不小的改動。首先，半條命也采用了客戶端預(yù)測邏輯來保證本地玩家能夠有流暢的手感，同時(1)為了讓客戶端提高預(yù)測準(zhǔn)確率（保證客戶端與服務(wù)器上的代碼邏輯一致），所以半條命里面他們讓客戶端與服務(wù)器執(zhí)行的是同一套代碼。其次，(2)考慮到本地玩家的時間總是領(lǐng)先服務(wù)器，玩家開槍的時間到服務(wù)器執(zhí)行時就一定會被延遲，所以為了盡量減小延遲所帶來的問題，他們提出了一種名為延遲補(bǔ)償?shù)募夹g(shù)。 - 延遲補(bǔ)償?shù)娜秉c
不過，延遲補(bǔ)償并不是一個萬能的優(yōu)化方式，采用與否應(yīng)該由游戲的類型與設(shè)計決定。考慮一個ACT類型的網(wǎng)游，玩家A延遲比較低、玩家B延遲比較高。在A的客戶端上，玩家A在T1時間靠近B，而后立刻執(zhí)行了一個后滾操作，發(fā)送到服務(wù)器。在B的客戶端上，同樣在T1時間發(fā)起進(jìn)攻，然后發(fā)送命令到服務(wù)器。由于A的延遲低，服務(wù)器先收到了A的指令，A開始后滾操作，這時候A已經(jīng)脫離了B的攻擊范圍。然后當(dāng)B的指令到達(dá)服務(wù)器的時候，如果采用延遲補(bǔ)償，就需要把A回滾到之前的位置結(jié)果就是A收到了B的攻擊，這對A來說顯然是不公平的。如果該情況發(fā)生在FPS里面，就不會有很大的問題，因為A根本不知道B什么時候瞄準(zhǔn)的A。
7）跟隨狀態(tài)同步（自譯）（Trailing state synchronization）
- Trailing state Synchronization對Timewrap回滾方式的優(yōu)化
2004年，Eric Cronin等人在傳統(tǒng)的Timewrap的回滾方式上提出了Trailing state synchronization算法[20]（TSS）。在他們看來，TimeWarp需要頻繁的生成游戲快照進(jìn)而占用大量內(nèi)存（每次發(fā)送命令前都要生成一份），而且每次遇到過期信息就立刻回滾并可能產(chǎn)生大量的對沖事件（anti-message）。這種同步方式是不適合Quake這種類型的FPS游戲的。 - Tss算法介紹
1）在TSS算法中，游戲的快照不是隨每個命令產(chǎn)生，而是以某種延遲(比如100ms)間隔為單位對游戲做快照。他事先保存了N個完整的游戲狀態(tài)（快照）以及命令鏈表，讓這N個狀態(tài)以不同的延遲去模擬推進(jìn)。游戲中延遲最低且被采用的狀態(tài)稱為Leading State，其他的稱為Trailing State，每個狀態(tài)都記錄著一個命令鏈表（執(zhí)行的以及未執(zhí)行的），各個狀態(tài)的延遲間隔由開發(fā)者設(shè)定。
2）Leading State向前推進(jìn)的時候會不斷的收到其他端的指令并添加到PendingCommands里面，如果某個命令的執(zhí)行時間小于當(dāng)前已經(jīng)推進(jìn)到的時間（比如圖A CommandB指令在時間225ms才被Leading State執(zhí)行，正常200ms就執(zhí)行完了），就會放在表的最前面立刻執(zhí)行，這時候其實我們已經(jīng)知道這個命令已經(jīng)由于延遲錯過正常執(zhí)行時間，可能要進(jìn)行回滾操作了。但是對于后續(xù)的Trailing State，這些過期Commands是可以被放到正確的位置的。當(dāng)Trailing State執(zhí)行到某個命令且發(fā)現(xiàn)Leading State在對應(yīng)的位置沒有這個命令的話，他就會觸發(fā)回滾（如果該命令對當(dāng)前游戲無影響，其實也可以不回滾），將當(dāng)前Trailing State的狀態(tài)信息拷貝到Leading State里面，然后設(shè)置錯誤命令時間至當(dāng)前本地執(zhí)行時間的所有命令為pending狀態(tài)，觸發(fā)這些狀態(tài)的重新執(zhí)行。
圖A
圖B Trailing State S1檢測沖突并觸發(fā)回滾
-
TSS對于Timewarp的最大優(yōu)勢
TSS相比TimeWarp，最大的優(yōu)勢就是1）大大降低了快照的記錄頻率（由原來的按事件記錄改為按延遲時間分開記錄），同時他2）可以避免由于網(wǎng)絡(luò)延遲造成的連續(xù)多次指令錯誤而不斷回滾的問題（Leading State不負(fù)責(zé)觸發(fā)回滾，Trailing State檢測并觸發(fā)）。 -
TSS的缺點
不過TSS同時維護(hù)了多個游戲世界的快照，也無形中增加了邏輯的復(fù)雜度，在最近幾年的網(wǎng)絡(luò)游戲中也并沒有看到哪個游戲使用了這種同步算法。在我看來，其實我們不必將整個世界的快照都記錄，只要處理好移動的快照同時使用服務(wù)器狀態(tài)同步就可以滿足大部分情況了。
8）狀態(tài)同步框架的演變
- 介紹
在2011年的GDC上，光環(huán)（Halo）項目的網(wǎng)絡(luò)技術(shù)負(fù)責(zé)人David Aldridge就其網(wǎng)絡(luò)同步框架發(fā)表了一次演講。通過視頻[21]，可以看到David同樣借鑒了TribeEngine的網(wǎng)絡(luò)架構(gòu)并在此基礎(chǔ)上進(jìn)行更多細(xì)節(jié)的調(diào)整。 - 2）網(wǎng)絡(luò)圖層
圖片說明：
- 虛幻4的網(wǎng)絡(luò)同步架構(gòu)
2015年，游戲業(yè)內(nèi)著名的商業(yè)引擎——Unreal Engine正式開源，其中內(nèi)置了一套非常完善的網(wǎng)絡(luò)同步架構(gòu)[22]
圖片說明：
虛幻引擎的前身是FPS游戲——“虛幻競技場”。該游戲早在1998年就發(fā)布，當(dāng)時與Quake屬于同類型的競品。虛幻本身也是基于CS架構(gòu)的狀態(tài)同步，不過由于無法查找到當(dāng)時的資料，筆者認(rèn)為一開始可能也是與Quake非常相似的同步架構(gòu)。后來在參考Tribe引擎的基礎(chǔ)上，進(jìn)行調(diào)整和優(yōu)化，形成了如今的Netdriver /Connection /Channel /Uobject的模型，以及RPC和屬性同步兩種同步方式，這已經(jīng)是網(wǎng)絡(luò)同步發(fā)展至今非常典型且完善的狀態(tài)同步方案了（后面要提到的OverWatch與其有很多相似之處）。作為一款游戲引擎，虛幻并沒有將所有常見的同步手段都集成到引擎里面，只是將移動相關(guān)的優(yōu)化方案（包括預(yù)測回滾、插值等）集成到了移動組件里面。其他的諸如延遲補(bǔ)償，客戶端預(yù)測等，他們放到了特定的Demo以及插件（GameplayAbility）當(dāng)中。有興趣的朋友可以去閱讀一些Unreal的源碼，看看最近幾年其網(wǎng)絡(luò)架構(gòu)的發(fā)展變化。更多的細(xì)節(jié)也可以參考文章：“使用虛幻引擎4年，我想再談?wù)勊木W(wǎng)絡(luò)架構(gòu)”[23]
9）守望先鋒與ECS架構(gòu)
1）守望先鋒的游戲架構(gòu)和網(wǎng)絡(luò)同步的實現(xiàn)方式
守望先鋒可以說是近年來將網(wǎng)絡(luò)同步優(yōu)化到極致的FPS游戲，其中涵蓋了我們可以用到的大部分同步優(yōu)化技術(shù)。在2018年的GDC上，來自守望先鋒的Gameplay程序TimFord分享了整個游戲的架構(gòu)以及網(wǎng)絡(luò)同步的實現(xiàn)方式[24]。
2）演講內(nèi)容介紹
雖然OverWatch基于CS架構(gòu)，但是卻同時用到了幀同步（邏輯幀概念）以及狀態(tài)同步包含的多種技術(shù)手段。為了實現(xiàn)確定性，他們固定了更新周期為16毫秒（電競比賽時7毫秒），每個周期稱為一個“命令幀”（等同于Lockstep中的“Turn”、“Bucket”）。在所有與客戶端預(yù)表現(xiàn)和玩家行為有關(guān)的操作不會放在Update而是放在固定周期的UpdateFixed里更新，方便客戶端預(yù)測與回滾。不過，整個游戲同步的核心還是狀態(tài)同步，玩家也并不需要等待其他客戶端的行為
一句話概括：守望先鋒采用的是基于ECS架構(gòu)的帶有預(yù)測回滾的增量狀態(tài)同步
3）守望網(wǎng)絡(luò)同步在gameplay層要解決的問題
（1）玩家移動
客戶端本地會不斷讀取輸入并立刻進(jìn)行角色移動的模擬，他會在客戶端記錄一個緩沖區(qū)來保存歷史的運動軌跡（即運動快照），用于后續(xù)與服務(wù)器糾正數(shù)據(jù)進(jìn)行對比以及回滾。
（2）技能行為
客戶端添加了一個buffer來存儲玩家的輸入操作（帶有命令幀的序號），同時保留歷史的技能快照。一旦服務(wù)器發(fā)現(xiàn)客戶端預(yù)測執(zhí)行失敗，就會讓客戶端先通過快照回滾到錯誤時刻（包括移動和技能），然后把錯誤時刻到當(dāng)前時間的所有輸入都重執(zhí)行一遍
圖片說明：左邊是服務(wù)器通知客戶端被眩暈，右邊是客戶端收到后進(jìn)行回滾
（3）命中預(yù)測
傷害計算在服務(wù)器，但是命中判定是在客戶端處理（所以可能存在一些誤差）。延遲補(bǔ)償技術(shù)也被采用，但是不是在服務(wù)器回滾所有玩家的位置，而是檢測當(dāng)前玩家的準(zhǔn)星與附近敵人的邏輯邊界（bounding volumes）是否有交集，沒有的話不需要回滾
4）為了增強(qiáng)玩家的游戲體驗，游戲還對不同ping的玩家進(jìn)行了邏輯的調(diào)整
（1）一旦PING值超過220毫秒，我們就會延后一些命中效果，也不會再去預(yù)測了，直接等服務(wù)器回包確認(rèn)。
（2）PING為0的時候，對彈道碰撞做了預(yù)測，而擊中點和血條沒有預(yù)測，要等服務(wù)器回包才渲染。
（3）當(dāng)PING達(dá)到300毫秒的時候，碰撞都不預(yù)測了，因為射擊目標(biāo)正在做快讀的外插，他實際上根本沒在這里，這里也用到了前面提到的DR（Dead Reckoning）外推算法(插值推測法)。
5）守望先鋒狀態(tài)同步的實現(xiàn)
狀態(tài)同步是如何實現(xiàn)的。同樣在2018年的GDC上，來自O(shè)verwatch服務(wù)器團(tuán)隊的開發(fā)工程師Phil Orwig分享了有關(guān)回放與同步的相關(guān)技術(shù)細(xì)節(jié)[25]。
- 細(xì)節(jié)
客戶端玩家操作后，這些指令會立刻發(fā)給服務(wù)器，同時本地開始執(zhí)行預(yù)測。隨后，服務(wù)器會將這一幀收到的所有玩家的輸入進(jìn)行處理和計算。在服務(wù)器上，每個對象產(chǎn)生的變化都會被記做一個Delta，并且會持續(xù)累積所有對象狀態(tài)的變化并保存到一個臨時的“每幀臟數(shù)據(jù)集合”(per frame dirty set)里。同時，服務(wù)器會對給每個客戶端（每個Connection）也會維護(hù)一個對應(yīng)的“臟數(shù)據(jù)集合”，這個集合可能保存一些之前沒有發(fā)送出去的信息（如下圖的C1是到客戶端1的，C2是到客戶端2的）。每幀結(jié)束時，所有客戶端對應(yīng)的“臟數(shù)據(jù)集合”會與當(dāng)前臟集合F合并，隨后當(dāng)前臟集合F會被清空。、
同一個Tick的后期，這些對應(yīng)不同客戶端連接的臟集合（C1、C2等）會被序列化并發(fā)送給對應(yīng)的客戶端，同時從臟集合中移除。這里的序列化并不是完全使用原生的狀態(tài)數(shù)據(jù)，而是維護(hù)了一個經(jīng)客戶端確認(rèn)收到的狀態(tài)數(shù)據(jù)的歷史記錄（比如我們服務(wù)器上已經(jīng)記錄了玩家的大部分信息，每次位置變化只序列化位置信息就可以了），這樣我們就可以使用“增量編碼”來改善帶寬模型，即減少帶寬的占用。
通過前面的分析，我們可以了解到整個網(wǎng)絡(luò)同步的邏輯是很復(fù)雜的，細(xì)節(jié)也非常多。所以，我們也需要考慮是否能從底層和框架上做一些調(diào)整和優(yōu)化。在守望先鋒里面，他們并沒有采用常見的面向?qū)ο竽Ｐ?#xff08;OOP），而是使用了數(shù)據(jù)與操作行為分離的ECS架構(gòu)[26]。Entity代表一個空的實體、Component代表一個只包含數(shù)據(jù)的組件、System代表一個處理數(shù)據(jù)的系統(tǒng)。在這個架構(gòu)下，我們將面向?qū)ο缶幊剔D(zhuǎn)為面向數(shù)據(jù)編程，游戲的不同模塊可以劃分成不同的系統(tǒng)，每個模塊只關(guān)心自己需要的數(shù)據(jù)（Component），這種模式下可以方便我們處理快照與回滾的邏輯。ECS系統(tǒng)看起來有著緩存友好、邏輯解耦等優(yōu)點，但是操作起來問題也不少，其中最難處理的一個問題就是如何控制System 運作的次序。
6）拋開面對對象模型，使用了面對數(shù)據(jù)編程-》突破難點：控制System 運作的次序
圖片說明：最后，簡單說一下底層的一些優(yōu)化。
10）狀態(tài)同步歷史發(fā)展總結(jié)（按時間段來）
1）前情提要
“狀態(tài)同步”同步的是對象的狀態(tài)信息，如角色的位置、生命值等。
2）在Quake誕生前
- 背景
其實也存在直接傳輸游戲?qū)ο鬆顟B(tài)的游戲，但是那時候游戲都比較簡單，相關(guān)的概念也并不清晰。當(dāng)時的架構(gòu)模型以P2P為主，考慮搭配帶寬限制等原因，軍事模擬、FPS等游戲都采用了“Lockstep”的方式進(jìn)行同步。 - 問題
由于作弊問題日益嚴(yán)重、確定性實現(xiàn)困難重重等因素，CS架構(gòu)逐漸代替P2P走向主流
3）Quake誕生
- 背景
CS架構(gòu)逐漸代替P2P走向主流。我們也發(fā)現(xiàn)似乎所有的游戲狀態(tài)信息都可以保存在服務(wù)器上，客戶端只需要接受服務(wù)器同步過來的狀態(tài)并渲染就可以了。按照這種思路，Quake誕生了，他拋棄了Doom的架構(gòu)并帶著狀態(tài)同步的方式進(jìn)入我們的視野。這時候的狀態(tài)同步還只是簡單的快照同步 - 缺點
每次同步前服務(wù)器都需要把整個游戲世界的狀態(tài)信息打包發(fā)送給客戶端，快照同步太浪費帶寬了，不同的玩家在一段時間內(nèi)只能在很小的范圍內(nèi)活動，根本沒有必要知道整個世界的狀態(tài)。同時，每次發(fā)送的快照都與之前的快照有相當(dāng)多重復(fù)的內(nèi)容，確實過于奢侈 - 題外話
此，星際圍城：部落的開發(fā)團(tuán)隊構(gòu)建出了一個比較完善的狀態(tài)同步系統(tǒng)，用于對同步信息進(jìn)行分類和過濾。后來，光環(huán)、虛幻競技場、守望先鋒、Doom等游戲都在Tribe Engine的基礎(chǔ)上不斷完善狀態(tài)同步，形成了如今的架構(gòu)模型
4）現(xiàn)在的狀態(tài)同步到底指什么呢？
目前的狀態(tài)同步多用于CS架構(gòu)，客戶端通過RPC向服務(wù)器發(fā)送指令信息，服務(wù)器通過屬性同步（增量狀態(tài)同步）向客戶端發(fā)送各個對象的狀態(tài)信息。我們可以采用預(yù)測回滾、延遲補(bǔ)償、插值等優(yōu)化方式，甚至也可以采用“命令幀”的方式對同步做限制。不過在這個過程中，傳遞的內(nèi)容以狀態(tài)信息（即計算后的結(jié)果）為主，收到信息的另一端只需要和解同步過來的狀態(tài)即可，不需要在本地通過處理其他端的Input信息來進(jìn)行持續(xù)的模擬。
最后，再次拿出虛幻引擎的網(wǎng)絡(luò)同步模型來展示當(dāng)今的狀態(tài)同步。
11）文獻(xiàn)
[19]Yahn W. Bernier,"Latency Compensating Methods in Client/Server In-game Protocol Design and Optimization" 2001.Available: https://developer.valvesoftware.com/wiki/Latency_Compensating_Methods_in_Client/Server_In-game_Protocol_Design_and_Optimization[Accessed:2020-07-17] [20]Eric Cronin, Burton Filstrup Anthony R. Kurc, Sugih Jamin,"An Efficient Synchronization Mechanism for Mirrored Game Architectures", 2004. Available: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.87.6043&rep=rep1&type=pdf[Accessed:2020-07-17] [21]David Aldridge, "I Shot You First: Networking the Gameplay of HALO: REACH", GDC, 2011. Available: https://www.bilibili.com/video/BV1Vt4y127op[Accessed:2020-07-17] [22]Epic Games, " UnrealEngine: Networking and Multiplayer". Available: https://docs.unrealengine.com/en-US/Gameplay/Networking/Overview/index.html[Accessed:2020-07-17] [23]Jerish, "使用虛幻引擎4年，我想再談?wù)勊木W(wǎng)絡(luò)架構(gòu)".Available: https://zhuanlan.zhihu.com/p/105040792[Accessed:2020-07-17] [24]Timothy Ford," 'Overwatch' Gameplay Architecture and Netcode", GDC, 2018. Available: https://www.bilibili.com/video/av44410490[Accessed:2020-07-17]（翻譯鏈接：https://gameinstitute.qq.com/community/detail/114516） [25]Philip Orwig," Replay Technology in 'Overwatch': Kill Cam, Gameplay, and Highlights", GDC, 2018. Available: https://www.bilibili.com/video/BV1aA41147bY[Accessed:2020-07-17]（翻譯鏈接：https://gameinstitute.qq.com/community/detail/115186） [26]WIKI,“Entity component system”.Available: https://en.wikipedia.org/wiki/Entity_component_system[Accessed:2020-07-17]六、物理同步
1）概念與理解
- 什么是物理同步
所謂“物理同步”，字面上講就是“帶有物理狀態(tài)對象的網(wǎng)絡(luò)同步”，嚴(yán)格上來說它并不是一個標(biāo)準(zhǔn)的技術(shù)名詞，而是大家約定俗成的一個概念。按照我的個人理解，可以進(jìn)一步解釋為“在較為復(fù)雜的物理模擬環(huán)境或有物理引擎參與計算的游戲里，如何對持有物理狀態(tài)信息的對象做網(wǎng)絡(luò)同步”。在英文中，我們可以使用Replicate physics simulated objects 或者Networked physics來表示類似的概念。
不過，考慮到并不是所有物理現(xiàn)象都交給物理引擎處理，而且有物理引擎參與的網(wǎng)游也并不一定需要對同步做任何處理，所以我們常說的物理同步更多的是指在網(wǎng)絡(luò)游戲中，如果玩家的位置或者與玩家交互對象的位置需要經(jīng)過物理引擎的模擬處理來得到結(jié)果，那么其中涉及到網(wǎng)絡(luò)同步技術(shù)就可以稱為物理同步!（這里的物理模擬一般指整個對象完全交給物理引擎去計算碰撞、位置、約束等，很多情況下可以等價為對Ragdoll的模擬）
備注：物理一詞涉及的范圍非常廣，在游戲里面應(yīng)用的場景也很多，但是并不一定需要進(jìn)行網(wǎng)絡(luò)同步，比如簡單的拋物線運動，射線檢測，與玩法無關(guān)的場景破碎等。
- 背景
早在上世紀(jì)70年代，就誕生了許多圍繞物理特性產(chǎn)生玩法的游戲，不過由于當(dāng)時計算機(jī)系統(tǒng)算力有限，涉及到的物理計算都非常簡單（比如乒乓球游戲中小球的移動模擬[1]）。隨著計算機(jī)性能的飛速提升，開發(fā)者們考慮將環(huán)境中的所有對象都交由統(tǒng)一的物理模塊驅(qū)動，由此慢慢的催生出了通用的物理引擎[2]。很快的，各個游戲開發(fā)商逐漸將物理引擎集成進(jìn)來，將更多更復(fù)雜的物理模擬過程應(yīng)用到游戲中，制作出了諸如極品飛車、FIFA、NBA、憤怒的小鳥等圍繞物理特性進(jìn)行玩法設(shè)計的游戲。另一方面，隨著計算機(jī)網(wǎng)絡(luò)的發(fā)展，游戲中的網(wǎng)絡(luò)同步技術(shù)愈加成熟，網(wǎng)絡(luò)游戲的品質(zhì)也不斷向單機(jī)游戲靠攏，我們也得以將傳統(tǒng)的單機(jī)游戲拓展成多人游戲。物理模擬作為提升游戲趣味性的一大技術(shù)也自然逐漸被納入其中，物理同步變得重要起來。
2）問題與解決方案
（1）前提
正如所前面解釋的那樣，物理同步并不是一種特殊的同步方式，而是在物理引擎和網(wǎng)絡(luò)同步技術(shù)共同發(fā)展的條件下而誕生的一種綜合行性解決方案，其核心手段還然是我們熟悉的幀同步或者狀態(tài)同步。使用幀同步技術(shù)我們需要每幀把玩家的Input信息發(fā)送出去，然后讓另一端的物理引擎根據(jù)輸入去模擬結(jié)果。如果使用狀態(tài)同步我們則需要本地模擬好數(shù)據(jù)并把物理位置、旋轉(zhuǎn)等關(guān)鍵信息發(fā)送到其他的客戶端，然后其他客戶端可以根據(jù)情況決定是否再執(zhí)行本地的物理模擬（如果是快照同步，由于拿到的就是最終的結(jié)果，那么就不需要本地再進(jìn)行模擬了）
（2）難點
這樣看來，物理同步好像與常規(guī)的同步也沒什么本質(zhì)上的區(qū)別，那么為什么他卻是一個難題呢？我認(rèn)為原因有以下兩點：
1）物理引擎的不確定性 2）在物理引擎參與模擬的條件下，網(wǎng)絡(luò)同步的微小誤差很容易被迅速放大（3）首先談?wù)勎锢硪娴牟淮_定性
- 歸納
首先，我們談?wù)勎锢硪娴拇_定性問題。很不幸，目前所有的物理引擎嚴(yán)格來說都不是確定性的，因為想保證不同平臺、編譯器、操作系統(tǒng)、編譯版本的指令順序以及浮點數(shù)精度完全一致幾乎是不可能的。關(guān)于物理確定性的討論有很多[3]，核心問題大致可以歸類為以下幾點
- 這里摘選一段PhysX物理引擎的描述[6]：
The PhysX SDK can be described as offering limited determinism（注：提供了有限程度的確定性）. Results can vary between platforms due to differences in hardware maths precision and differences in how the compiler reoders instructions during optimization. This means that behavior can be different between different platforms, different compilers operating on the same platform or between optimized and unoptimized builds using the same compiler on the same platform（注：不同平臺、編譯器、優(yōu)化版本都會影響確定性）. However, on a given platform, given the exact same sequence of events operating on the exact scene using a consistent time-stepping scheme, PhysX is expected to produce deterministic results. In order to achieve this determinism, the application must recreate the scene in the exact same order each time and insert the actors into a newly-created PxScene. There are several other factors that can affect determinism so if an inconsistent (e.g. variable) time-stepping scheme is used or if the application does not perform the same sequence of API calls on the same frames, the PhysX simulation can diverge.
- 不同引擎比較
如果游戲只是單個平臺上發(fā)行，市面上常見的物理引擎（Havok，PhysX，Bullet）基本上都可以保證結(jié)果的一致性。因為我們可以通過使用同一個編譯好的二進(jìn)制文件、在完全相同的操作系統(tǒng)上運行來保證指令順序并解決浮點數(shù)精度問題，同時打開引擎的確定性開關(guān)來保證約束的計算順序（不過會影響性能），這也是很多測試者在使用Unity等商業(yè)引擎時發(fā)現(xiàn)物理同步可以完美進(jìn)行的原因。當(dāng)然，這并不是說我們就完全放棄了跨平臺確定性的目標(biāo)，比如Unity新推出的DOTS架構(gòu)[7][8]正在嘗試解決這個問題（雖然注釋里面仍然鮮明的寫著“Reserved for future”）。
-
導(dǎo)致的結(jié)果
考慮到物理引擎的確定性問題，我們可以得出一個初步的結(jié)論——完全使用幀同步做物理同步是不合適的（或者說做跨平臺游戲是行不通的）。而對于狀態(tài)同步，我們可以定時地去糾正位置信息來避免誤差被放大。如果一定要使用幀同步去做跨平臺同步，那么只能選擇放棄物理引擎自己模擬或者用定點數(shù)來改造物理引擎，這可能是得不償失的。 -
大師的辦法
下面不妨先排除掉一致性的問題，來看看如何實現(xiàn)所謂的“物理同步”。實際上，無論是優(yōu)化手段還是實現(xiàn)方式與前兩篇提到的方案是幾乎一致的，幀同步、快照同步、狀態(tài)同步都可以采用，增量壓縮、Inputbuffer等優(yōu)化手段也一樣可以用于物理同步的開發(fā)中。Network Next的創(chuàng)始人Glenn Fiedler在2014年撰寫了一系列的物理同步相關(guān)的文章[9]，使用一個同步的Demo非常詳細(xì)地闡述了同步技術(shù)是如何應(yīng)用以及優(yōu)化的。涉及到的技術(shù)點大致如下，涵蓋了網(wǎng)絡(luò)同步的大部分的知識細(xì)節(jié)：
- 另外，在2018年的GDC上，Glenn也對物理同步進(jìn)行一次演講分享[10]，具體的細(xì)節(jié)建議大家移步到Glenn Fiedler的網(wǎng)站以及GitHub[11]去看。
Glenn Fiedler的物理同步Demo
（4）即網(wǎng)絡(luò)同步的誤差是如何被物理模擬迅速放大的
接下來，我們再來談?wù)劦诙€難點，即網(wǎng)絡(luò)同步的誤差是如何被物理模擬迅速放大的（尤其在多人交互的游戲中）。我們在前面的章節(jié)里也談過，為了保證本地客戶端的快速響應(yīng)，通常會采取預(yù)測回滾的機(jī)制（Client prediction，即本地客戶端立刻相應(yīng)玩家操作，服務(wù)器后續(xù)校驗決定是否合法）。這樣我們就犧牲了事件順序的嚴(yán)格一致來換取主控端玩家及時響應(yīng)的體驗，在一般角色的非物理移動同步時，預(yù)測以及回滾都是相對容易的，延遲比較小的情況位置的誤差也可以幾乎忽略。然而在物理模擬參與的時候，情況就會變得復(fù)雜起來。
主控(Autonomous/Master)以及模擬(Simulate/Replica)都是針對某個對象而言的。
假如有兩個客戶端，玩家A控制小車1，玩家B控制小車2。小車1在玩家A的客戶端上就是主控的，小車2在玩家A的客戶端上就是模擬的。同理，小車2在B客戶端上就是主控的，小車1在B客戶端上就是模擬的。
假如在一個游戲中（帶有預(yù)測，也就是你本地的對象一定快于遠(yuǎn)端）你和其他玩家分別控制一個物理模擬的小車朝向?qū)Ψ經(jīng)_去，他們相互之間可能發(fā)生碰撞而彼此影響運動狀態(tài)，就會面臨下面的問題。
1.由于網(wǎng)絡(luò)同步的誤差無法避免，那么你客戶端上的發(fā)生碰撞的位置一定與其他客戶端的不同
（?本地客戶端的模擬小車（對手小車）一定落后其控制端）
2.其次，對于本地上的其他模擬小車，要考慮是否在碰撞時完全開啟物理模擬(Ragdoll)。如果不開啟物理，那么模擬小車就會完全按照其主控端同步的位置進(jìn)行移動，即使已經(jīng)在本地發(fā)生了碰撞他可能還是會向前移動。如果開啟碰撞，兩個客戶端的發(fā)生碰撞的位置會完全不同。無論是哪種情況，網(wǎng)絡(luò)同步的誤差都會在物理引擎的“加持”下迅速被放大進(jìn)而導(dǎo)致兩端的結(jié)果相差甚遠(yuǎn)。
(不開啟物理模擬條件下，模擬端不會在碰撞時立刻停下)
3、其實對于一般角色的非物理移動同步，二者只要相撞就會迅速停止移動，即使發(fā)生穿透只要做簡單的位置“回滾”即可。然而在物理模擬參與的時候，直接作位置回滾的效果會顯得非常突兀并出現(xiàn)很強(qiáng)的拉扯感，因為我們幾乎沒辦法在本地準(zhǔn)確的預(yù)測一個對象的物理模擬路徑。如果你仔細(xì)閱讀了前面Glenn Fiedler的文章（或者上面總結(jié)的技術(shù)點），你會發(fā)現(xiàn)里面并沒有提到常見的預(yù)測回滾技術(shù)，因為他只有一個主控端和一個用于觀察結(jié)果的模擬端，并不需要回滾。
- 在2017年的GDC上，來自育碧的技術(shù)負(fù)責(zé)人Matt Delbosc就《看門狗2》中的載具同步進(jìn)行了演講[12]，詳細(xì)的分析了多個主控端控制不同對象發(fā)生碰撞時應(yīng)該如何處理。
《看門狗2》的網(wǎng)絡(luò)模型是基于狀態(tài)同步的P2P，主控角色預(yù)測先行而模擬對象會根據(jù)快照（snapshot，即模擬對象在其主控端的真實位置）使用Projective Velocity Blengding做內(nèi)插值，他們在制作時也面臨和上面描述一樣的問題。假如兩個客戶端各控制一個小車撞向?qū)Ψ?#xff0c;由于延遲問題，敵人在本地的位置一定是落后其主控端的。那么就可能發(fā)生你開車去撞他時，你本地撞到了他的車尾，而他的客戶端什么都沒有發(fā)生。
- 時間差來解決這個問題
所以，首先要做的就是盡量減少不同客戶端由于延遲造成的位置偏差，Matt Delbosc引入了一個TimeOffset的概念，根據(jù)當(dāng)前時間與TimeOffset的差值來決定對模擬對象做內(nèi)插值還是外插值，有了合適的外插值后本地的模擬對象就可以做到盡量靠近敵方的真實位置。
而關(guān)于碰撞后位置的誤差問題，他們采用了Physics Simulation Blending技術(shù)，即發(fā)生碰撞前開啟模擬對象的RigidBody并設(shè)置位置權(quán)重為1（快照位置的權(quán)重為0），然后在碰撞發(fā)生后的一小段時間內(nèi)，不斷減小物理模擬的權(quán)重增大快照位置的權(quán)重使模擬對象的運動狀態(tài)逐漸趨于與其主控端，最終消除不一致性，騰訊的吃雞手游就采用了相似的解決方案[13]。
不過實際上， Matt團(tuán)隊遇到的問題遠(yuǎn)不止這些，還有諸如如何用插值解決旋轉(zhuǎn)抖動問題，人物與載具相撞時不同步怎么辦等等，知乎上有一篇譯文可以參考[14]。
可能有些朋友會問，如果我不使用預(yù)測回滾技術(shù)是不是就沒有這個問題呢？答案依然是否定的，假如你在運行一個車輛的中間突然變向，而這個操作被丟包或延遲，只要服務(wù)器不暫停整個游戲來等待你的消息，那么你本地的結(jié)果依然與其他客戶端不同進(jìn)而產(chǎn)生誤差。也就是說除非你使用最最原始的“完全幀同步”（即客戶端每次行動都要等到其他客戶端的消息全部就緒才行），否則由于網(wǎng)絡(luò)同步的延遲無法避免，誤差也必定會被物理模擬所放大。
- 同樣在2017年，另一款風(fēng)靡全球的競技游戲——《火箭聯(lián)盟》悄然上線，可謂是將物理玩法發(fā)揮到了極致。次年，《火箭聯(lián)盟》的開發(fā)者Jared Cone也來到了GDC，分享了他們團(tuán)隊是如何解決物理同步問題的[14]。
《火箭聯(lián)盟》的核心玩法是“用車踢球”，每個玩家控制一個汽車，通過撞擊足球來將其“踢”進(jìn)敵方的球門。由于是多人競技游戲，所以一定要有一個權(quán)威服務(wù)器來避免作弊，最終的結(jié)果必須由服務(wù)器來決定。相比于《看門狗》，他們遇到的情況明顯更復(fù)雜，除了不同玩家控制不同的小車，還有一個完全由服務(wù)器操控的小球。按照常規(guī)的同步方式，本地的主控玩家預(yù)測先行，其他角色的數(shù)據(jù)由服務(wù)器同步下發(fā)做插值模擬。但是在這樣一個延遲敏感且?guī)в形锢砟M的競技游戲中，玩家的Input信息的丟失、本地對象與服務(wù)器的位置不統(tǒng)一都會頻繁的帶來表現(xiàn)不一致的問題，而且FPS中常見的延遲補(bǔ)償策略并不適合當(dāng)前的游戲類型（簡單來說就是延遲大的玩家會影響其他玩家的體驗，具體原因我們在上一篇延遲補(bǔ)償?shù)恼鹿?jié)也有討論）。
ji+ 解決方案
為了解決這些問題，Jared Cone團(tuán)隊采用了“InputBuffer”以及“客戶端全預(yù)測”兩個核心方案。
1)InputBuffer，即服務(wù)器緩存客戶端的Input信息，然后定時的去buffer里面獲取（buffer大小可以動態(tài)調(diào)整），這樣可以減少網(wǎng)絡(luò)延遲和抖動帶來的卡頓問題。
2)客戶端全預(yù)測，即客戶端上所有可能產(chǎn)生移動的對象（不僅僅是主控對象）全部會在本地預(yù)測先行，這樣本地在預(yù)測成功時所有對象的位置都是準(zhǔn)確的，客戶端與服務(wù)器的表現(xiàn)也會高度一致，當(dāng)然預(yù)測失敗的時候自然會也要處理位置回滾。
仔細(xì)分析這兩款游戲，你會發(fā)現(xiàn)他們采用都是“狀態(tài)同步+插值+預(yù)測回滾”的基本框架，這也是目前業(yè)內(nèi)上比較合適的物理同步方案。
（5）總結(jié)
除了同步問題，物理引擎本身對系統(tǒng)資源（CPU/GPU）的消耗也很大。比如在UE4引擎里面，玩家每一幀的移動都會觸發(fā)物理引擎的射線檢測來判斷位置是否合法，一旦場景內(nèi)的角色數(shù)量增多，物理引擎的計算量也會隨之增大，進(jìn)而改變Tick的步長，幀率降低。而幀率降低除了導(dǎo)致卡頓問題外，還會進(jìn)一步影響到物理模擬，造成更嚴(yán)重的結(jié)果不一致、模型穿透等問題，所以我們需要盡量減少不必要的物理模擬并適當(dāng)簡化我們的計算模型。
3）參考資料
參考資料： [1] WIKI, "Pong", WIKI, 2020.Available:https://en.wikipedia.org/wiki/Pong[Accessed:2020-12-12] [2] Tony Wang, "游戲物理模擬簡史", 知乎, 2020.Available:https://zhuanlan.zhihu.com/p/106977617[Accessed:2020-12-12] [3] Theraot, "How can I perform a deterministic physics simulation?",Gamedev Stackexchange, 2019.https://gamedev.stackexchange.com/questions/174320/how-can-i-perform-a-deterministic-physics-simulation[Accessed:2020-12-12] [4] Yossi Kreinin, "Consistency: how to defeat the purpose of IEEE floating point", Personal Blog , 2008. Available:http://yosefk.com/blog/consistency-how-to-defeat-the-purpose-of-ieee-floating-point.html[Accessed:2020-12-12] [5] Glenn Fiedler, "Floating Point Determinism", Personal Blog , 2010. Available:https://gafferongames.com/post/floating_point_determinism/[Accessed:2020-12-12] [6] NVIDIA, "NVIDIA PhysX SDK 3.4.0 Documentation Determinism", NVIDIA , 2020. Available:https://docs.nvidia.com/gameworks/content/gameworkslibrary/physx/guide/Manual/BestPractices.html[Accessed:2020-12-12] [7]MelvMay, "How much deterministic is Physics from Unity3d In 2019?",Unity Forum,2020.Available:https://forum.unity.com/threads/how-much-deterministic-is-physics-from-unity3d-in-2019.711311/[Accessed:2020-12-12] [8]Unity, "Burst User Guide",Unity Manual, 2020.Available:https://docs.unity3d.com/Packages/com.unity.burst@1.0/manual/index.html?_ga=2.60059693.1096806956.1607653832-2097754989.1600740353[Accessed:2020-12-12] [9] Glenn Fiedler, "Introduction to Networked Physics", Personal Blog，2014. Available: https://gafferongames.com/post/introduction_to_networked_physics/[Accessed:2020-12-12] [10]Glenn Fiedler，"Physics for Game Programmers : Networking for Physics Programmers"， 2018.Available:https://www.gdcvault.com/play/1022195/Physics-for-Game-Programmers-Networking[Accessed:2020-12-12] [11]Glenn Fiedler，"UnityDemo: Networked Physics in Virtual Reality: Networking a stack of cubes with Unity and PhysX" , 2018. Available:https://github.com/fbsamples/oculus-networked-physics-sample/[Accessed:2020-12-12] [12] Matt Delbosc, "Replicating Chaos Vehicle Replication in Watch Dogs 2", GDC, 2017. Available:https://www.bilibili.com/video/BV1KA41187jk[Accessed:2020-12-12] [13]Ned,"手游中載具物理同步的實現(xiàn)方案", 騰訊游戲?qū)W院, 2018. Available:https://gameinstitute.qq.com/knowledge/100044[Accessed:2020-12-12] [14]Funny David, "看門狗2的載具同步(翻譯)", 知乎, 2019. Available:https://zhuanlan.zhihu.com/p/95560180[Accessed:2020-12-12] [15]Jared Cone, "It IS Rocket Science! The Physics of 'Rocket League' Detailed", GDC, 2018. Available:https://www.bilibili.com/video/av44416219[Accessed:2020-12-12]七、優(yōu)化技術(shù)總結(jié)
總結(jié)
以上是生活随笔為你收集整理的游戏思考04补充：网络游戏同步算法的理解（参考网易雷火jerish的文章，未完待续7/23，参考文献附尾，物理同步已更新完）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： java遍历Set集合
- 下一篇： Java 字符串分割陷阱