網(wǎng)絡(luò)同步在游戲歷史中的發(fā)展變化(三)—— 狀態(tài)同步的發(fā)展歷程與基...

前言：

網(wǎng)絡(luò)同步屬于游戲開(kāi)發(fā)中比較重要且復(fù)雜的一部分，但是由于網(wǎng)上的資料內(nèi)容參差不齊，很多人直接拿別人的結(jié)論寫文章，導(dǎo)致很多人對(duì)這一塊的很多概念和理解都是錯(cuò)誤的。本文參考了大量的相關(guān)論文和資料（花了半年的時(shí)間看了不下70篇論文、博客、視頻），從網(wǎng)絡(luò)同步的基本概念講起，進(jìn)一步深入到服務(wù)器架構(gòu)與同步算法的實(shí)現(xiàn)細(xì)節(jié)，可以幫你系統(tǒng)的梳理網(wǎng)絡(luò)同步技術(shù)的發(fā)展與應(yīng)用。該系列估計(jì)有6篇，本篇核心內(nèi)容為“狀態(tài)同步的發(fā)展歷程與基本原理”，首發(fā)在網(wǎng)易雷火官方的知乎賬號(hào)上。

注：在公眾號(hào)后臺(tái)回復(fù)“網(wǎng)絡(luò)同步論文”可獲取文中所引用的論文

網(wǎng)絡(luò)同步在游戲歷史中的發(fā)展變化（一）—— 網(wǎng)絡(luò)同步與網(wǎng)絡(luò)架構(gòu)

網(wǎng)絡(luò)同步在游戲歷史中的發(fā)展變化（二）——?Lockstep與幀同步

目錄（第三篇）：

四.State Synchronization 狀態(tài)同步

??1.雷神之錘與快照同步

?（Quake and Snapshot）

??2.星際圍攻：部落中的網(wǎng)絡(luò)架構(gòu)?（The TRIBES Engine??Networking Model）

??3.客戶端預(yù)測(cè)與回滾（Client-side prediction and Rollback）

??4.事件鎖定與時(shí)鐘同步?(Event Locking and Clock??Synchronization)

??5.插值技術(shù)（Interpolation and Extrapolation ）

四.狀態(tài)同步State Synchronization?

在二十年前，相比于使用幀同步（為了方便描述，后續(xù)的文章中以幀同步代替Lockstep）還是狀態(tài)同步，開(kāi)發(fā)者們更關(guān)心的是網(wǎng)絡(luò)架構(gòu)的實(shí)現(xiàn)方式（P2P/CS)。換句話講，在當(dāng)時(shí)業(yè)內(nèi)看來(lái)，P2P架構(gòu)的同步模型雖然減少了延遲，但由于作弊、跨平臺(tái)、難以維護(hù)大型網(wǎng)絡(luò)游戲等問(wèn)題，人們更希望用CS架構(gòu)來(lái)取代P2P。同時(shí)，開(kāi)發(fā)者們雖然可以繼續(xù)在CS架構(gòu)下使用邏輯比較簡(jiǎn)潔的幀同步，但有不少開(kāi)發(fā)者都認(rèn)為剛剛誕生的狀態(tài)同步貌似更符合CS架構(gòu)的同步理念。

需要強(qiáng)調(diào)的是，幀同步與狀態(tài)同步并不是一個(gè)簡(jiǎn)單的對(duì)立概念，其中的差異包括“數(shù)據(jù)格式與內(nèi)容”，“邏輯的計(jì)算位置”，“是否有權(quán)威服務(wù)器”等 。隨著時(shí)間的推進(jìn)，兩種算法互相借鑒互相發(fā)展，早已不是當(dāng)年的樣子。網(wǎng)上存在很多概念模糊的文章，包括一些大佬對(duì)同步的概念理解也有偏差，這些都很容易對(duì)新手產(chǎn)生誤導(dǎo)。所以筆者建議，如果你想真正的了解或者學(xué)習(xí)網(wǎng)絡(luò)同步，不妨跟著這篇文章去了解二者的發(fā)展歷史，相信看過(guò)后的你一定能更深刻的理解到幀同步與狀態(tài)同步的異同。（文末同上篇一樣貼出了大量的文獻(xiàn)內(nèi)容）

1.雷神之錘與快照同步（Snapshot）

快照是一個(gè)通用的行業(yè)術(shù)語(yǔ)，即在任何給定時(shí)刻記錄設(shè)備的狀態(tài)并在設(shè)備出現(xiàn)故障時(shí)進(jìn)行還原。快照技術(shù)常用于計(jì)算機(jī)的各種存儲(chǔ)系統(tǒng)，例如邏輯卷管理、數(shù)據(jù)庫(kù)、文件系統(tǒng)等。在游戲領(lǐng)域中，快照的含義更像是照片一樣，將當(dāng)前場(chǎng)景所有的信息保存起來(lái)。嚴(yán)格來(lái)說(shuō)，快照同步應(yīng)該屬于狀態(tài)同步的前身，雖然思想相似但是具體實(shí)現(xiàn)卻有不小的差異。

1996年，在doom發(fā)行不久后，Id software就公開(kāi)了新作——雷神之錘（Quake）。在Quake里他們舍棄了之前的P2P而改用CS架構(gòu)，同時(shí)也舍棄了lockstep的同步方式。新的架構(gòu)下，客戶端就是一個(gè)純粹的渲染器(稱為Dumb Client)，每一幀玩家所有的操作信息都會(huì)被收集并發(fā)送到服務(wù)器，然后服務(wù)器將計(jì)算后的結(jié)果壓縮后發(fā)給客戶端來(lái)告知他們有哪些角色可以顯示，顯示在什么位置上。

上述的這個(gè)過(guò)程就是我們所說(shuō)的快照同步，即服務(wù)器每幀接受客戶端的輸入來(lái)計(jì)算整個(gè)世界的狀態(tài)，然后將結(jié)果快照發(fā)送給所有客戶端。Quake這里所謂的快照，就是把整個(gè)游戲世界里面所有對(duì)象的狀態(tài)做一次臨時(shí)保存（他更強(qiáng)調(diào)的是對(duì)象的可視化狀態(tài)，比如位置和旋轉(zhuǎn)等）。通過(guò)這個(gè)快照，我們可以還原出這一刻世界的狀態(tài)應(yīng)該是什么樣子的。

Quake運(yùn)行時(shí)，邏輯幀率與渲染幀率是保持一致的。由于所有的核心邏輯都是在服務(wù)器進(jìn)行，所以也不需要通過(guò)鎖步來(lái)避免客戶端不同步的問(wèn)題，只要在收到服務(wù)器消息后執(zhí)行渲染就好了。當(dāng)然，對(duì)于性能以及網(wǎng)絡(luò)環(huán)境較差的玩家來(lái)說(shuō)，游戲體驗(yàn)仍然很糟糕。因?yàn)槟惆聪乱粋€(gè)按鈕后，可能很長(zhǎng)時(shí)間都沒(méi)有反應(yīng)，當(dāng)收到服務(wù)器的快照消息后，你可能已經(jīng)被網(wǎng)絡(luò)好的玩家擊殺了。

IdSoftware自2012年以來(lái)已經(jīng)陸續(xù)把Quake以及Doom相關(guān)的源碼上傳到了GitHub上面[4]。如果你看過(guò)其中Quake的源碼，會(huì)發(fā)現(xiàn)整個(gè)網(wǎng)絡(luò)的架構(gòu)還是比較簡(jiǎn)單清晰的，博主FABIEN SANGLARD就在網(wǎng)上分享了關(guān)于Quake源碼的剖析[5]（還有很多其他項(xiàng)目的源碼剖析）。

//client   WinMain  {    while (1)    {        newtime = Sys_DoubleTime ();        time = newtime - oldtime;        Host_Frame (time)        {          setjmp          Sys_SendKeyEvents          IN_Commands          Cbuf_Execute
          /* Network */          CL_ReadPackets          CL_SendCmd
          /* Prediction//Collision */          CL_SetUpPlayerPrediction(false)          CL_PredictMove          CL_SetUpPlayerPrediction(true)          CL_EmitEntities
          /* Rendition */          SCR_UpdateScreen        }        oldtime = newtime;    }  }

但Quake里面由于客戶端只是一個(gè)簡(jiǎn)單的渲染器，同步過(guò)程中會(huì)出現(xiàn)很多明顯的問(wèn)題，比如延遲過(guò)大，客戶端性能浪費(fèi)，服務(wù)器壓力大等。而其中最明顯的問(wèn)題就是對(duì)帶寬的浪費(fèi)，對(duì)于一個(gè)物體和角色比較少的游戲，可以使用快照將整個(gè)世界的狀態(tài)都存儲(chǔ)并發(fā)送，但是一旦物體數(shù)量多了起來(lái)，帶寬占用就會(huì)直線上升。所以，我們希望不要每幀都把整個(gè)世界的數(shù)據(jù)都發(fā)過(guò)去，而是只發(fā)送那些產(chǎn)生變化的對(duì)象數(shù)據(jù)（可以稱為增量快照同步）。更進(jìn)一步的，我們還希望將數(shù)據(jù)拆分的更細(xì)一些，并根據(jù)客戶端的特點(diǎn)來(lái)定制發(fā)送不同的數(shù)據(jù)?；谶@種思想，《星際部落：圍攻》團(tuán)隊(duì)的開(kāi)發(fā)者們開(kāi)始對(duì)網(wǎng)絡(luò)架構(gòu)進(jìn)行抽象和分層，構(gòu)造出來(lái)一套比較完善的"狀態(tài)同步"系統(tǒng)并以此開(kāi)發(fā)出了Tribe游戲系列。

The TRIBES Engine可以認(rèn)為是第一個(gè)實(shí)現(xiàn)狀態(tài)同步的游戲引擎，《星際部落：圍攻》也可以認(rèn)為是第一個(gè)比較完美的實(shí)現(xiàn)了狀態(tài)同步的游戲。

下圖是該引擎的網(wǎng)絡(luò)架構(gòu)[6]：

平臺(tái)數(shù)據(jù)包模塊（Platform Packet Module）可以理解成被封裝的Socket模塊，連接管理器（Connection Manager）處理多個(gè)客戶端與服務(wù)器的連接，流管理器（Stream Manager）負(fù)責(zé)將具體的數(shù)據(jù)分發(fā)到上面的三個(gè)高級(jí)管理器。

• Ghost管理器：負(fù)責(zé)向客戶端發(fā)送需要同步對(duì)象的狀態(tài)信息，類似屬性同步。

• 事件管理器：維護(hù)事件隊(duì)列，每個(gè)事件相當(dāng)于一個(gè)的RPC。

• 移動(dòng)管理器：本質(zhì)上與事件管理器相同，但是由于移動(dòng)數(shù)據(jù)的需要高頻的捕捉和發(fā)送，所以單獨(dú)封裝成一個(gè)特殊的管理器。

3.客戶端預(yù)測(cè)與回滾

（Client-side prediction and Rollback）

《毀滅公爵》是上世紀(jì)90年代一個(gè)經(jīng)典的FPS游戲系列，首部作品的發(fā)布時(shí)間與Doom幾乎相同，網(wǎng)絡(luò)架構(gòu)也極為相似。在1996年發(fā)布的《毀滅公爵3D》里面，為了提高客戶端的表現(xiàn)與響應(yīng)速度，他放棄了“Dumb客戶端”的方案并首次采用客戶端預(yù)測(cè)來(lái)進(jìn)行優(yōu)化（這里主要指移動(dòng)預(yù)測(cè)）[7]。即在服務(wù)器確認(rèn)輸入并更新游戲狀態(tài)之前，讓客戶端立即對(duì)用戶輸入進(jìn)行本地響應(yīng)。由于這種方式可以大大的降低網(wǎng)絡(luò)延遲所帶來(lái)的困擾，很快的Quake也開(kāi)始參考對(duì)網(wǎng)絡(luò)架構(gòu)進(jìn)行的大刀闊斧的修改。在1997年發(fā)布的更新版本QuakeWorld里面[8][9]，Quake添加了對(duì)互聯(lián)網(wǎng)對(duì)戰(zhàn)的支持以及客戶端預(yù)測(cè)等新的內(nèi)容。

關(guān)于預(yù)測(cè)，其實(shí)就是本地先執(zhí)行，所以并不需要什么特別的算法，反倒是預(yù)測(cè)后的客戶端與服務(wù)器的同步處理有很多值得優(yōu)化的地方。由于玩家的行為是沒(méi)辦法完全預(yù)測(cè)的，所以你不知道玩家會(huì)在什么時(shí)候突然停下或者轉(zhuǎn)彎，所以經(jīng)常會(huì)發(fā)生預(yù)測(cè)失敗的情況。

如果玩家本地的預(yù)測(cè)結(jié)果與服務(wù)器幾乎一致，那么我們認(rèn)為預(yù)測(cè)是成功且有效的，玩家不會(huì)受到任何影響，可以繼續(xù)操作。反之，如果客戶端結(jié)果與服務(wù)器不一致，我們應(yīng)該如何處理呢？這里分為兩種情況。

一.在沒(méi)有時(shí)間戳的條件下，收到了一條過(guò)時(shí)的服務(wù)器位置數(shù)據(jù)。你在本地的行為相比服務(wù)器是超前的，假如你在time=10ms的和time=50ms時(shí)候分別發(fā)送了一條指令。由于網(wǎng)絡(luò)延遲的存在，當(dāng)你已經(jīng)執(zhí)行完第二個(gè)指令的時(shí)候才收到服務(wù)器對(duì)第一條指令的位置同步。很明顯，我們不應(yīng)該讓過(guò)時(shí)的服務(wù)器數(shù)據(jù)來(lái)糾正你當(dāng)前的邏輯。解決方法就是在每個(gè)指令發(fā)出的時(shí)候帶上他的時(shí)間戳，這樣客戶端收到服務(wù)器反饋的時(shí)候就知道他處理的是哪條指令信息。

二.假如我們?cè)谥噶罾锩嫣砑恿藭r(shí)間戳的信息，并收到了一條過(guò)時(shí)的服務(wù)器位置數(shù)據(jù)。在上一篇文章里我們提到了TimeWarp算法，即當(dāng)一個(gè)對(duì)象收到了一個(gè)過(guò)去某個(gè)時(shí)刻應(yīng)該執(zhí)行的事件時(shí)，他應(yīng)該回滾到那個(gè)時(shí)刻的狀態(tài)，并且回滾前面所有的行為與狀態(tài)（包括取消之前行為所產(chǎn)生的事件）。這個(gè)時(shí)候我們可以用類似的方法在本地進(jìn)行糾正，大體的方案就是把玩家本地預(yù)執(zhí)行的指令都記錄好時(shí)間戳并存放到一個(gè)MOVE BUFFER列表里（類似一個(gè)滑動(dòng)窗口）。如果服務(wù)器的計(jì)算結(jié)果與你本地預(yù)測(cè)相同，可以回復(fù)你一個(gè)ACKMOVE。如果服務(wù)器發(fā)現(xiàn)你的某個(gè)移動(dòng)位置有問(wèn)題時(shí)，會(huì)把該指令的時(shí)間戳以及正確的位置打包發(fā)給你。當(dāng)你收到ACKMOVE的時(shí)候，你可以把MOVE BUFFER里面的數(shù)據(jù)從表里面移除，而當(dāng)你收到錯(cuò)誤糾正信息時(shí)就需要本地回滾到服務(wù)器指定的位置同時(shí)把錯(cuò)誤時(shí)刻后面MOVE BUFFER里面的指令重新執(zhí)行一遍。這里讀者可能會(huì)產(chǎn)生一個(gè)疑問(wèn)——為什么不直接拉回？因?yàn)檫@時(shí)候他想糾正的是之前的錯(cuò)誤而不是現(xiàn)在的錯(cuò)誤，如果簡(jiǎn)單的拉回就會(huì)讓你覺(jué)得被莫名其妙的拉回到以前的一個(gè)位置。同時(shí)，考慮到已經(jīng)在路上的指令以及后續(xù)你要發(fā)送的預(yù)測(cè)指令，會(huì)讓服務(wù)器后續(xù)的校驗(yàn)與糾正變得復(fù)雜且奇怪，具體流程細(xì)節(jié)可以參考下圖。另外，Gabriel Gambetta博主在他的文章中，也對(duì)這種情況進(jìn)行了簡(jiǎn)單的分析[10]。

關(guān)于TimeWarp算法的補(bǔ)充：Timewarp技術(shù)最早出現(xiàn)于仿真模擬中[11]，我們可以認(rèn)為這些仿真程序中采用的是“以事件驅(qū)動(dòng)的幀同步”。也就是說(shuō)，給出一個(gè)指令，他就會(huì)產(chǎn)生并觸發(fā)多個(gè)事件，這些事件可能進(jìn)而觸發(fā)更多的事件來(lái)驅(qū)動(dòng)程序，同理取消一個(gè)過(guò)去發(fā)生的事件也需要產(chǎn)生一個(gè)新的取消事件才行。這樣造成的問(wèn)題就是回滾前面的N個(gè)操作，就需要產(chǎn)生N個(gè)新的對(duì)抗事件，而且這N個(gè)事件還需要發(fā)送到所有其他的客戶端執(zhí)行。如果這N個(gè)事件又產(chǎn)生了新的事件，那么整個(gè)回滾的操作就顯得復(fù)雜了很多。換成前面移動(dòng)的例子來(lái)解釋一下，就是客戶端收到服務(wù)器的糾正后，他會(huì)立刻發(fā)送回滾命令告訴（P2P架構(gòu)下）所有其他客戶端，我要取消前面的操作，然后其他客戶端在本地也執(zhí)行回滾。而在如今的CS架構(gòu)狀態(tài)同步的方式下，服務(wù)器可能早就拒絕了客戶端的不合法行為，所以并不需要處理回滾（同理，其他客戶端也是）。所以嚴(yán)格來(lái)說(shuō)，TimeWarp技術(shù)以及優(yōu)化后的BreathTimeWarp技術(shù)[12]都是針對(duì)“以事件驅(qū)動(dòng)的幀同步”，并不能與預(yù)測(cè)回滾這套方案完全等價(jià)。當(dāng)然，隨著時(shí)間的推移，很多概念也變的逐漸寬泛一些，我們平時(shí)提到的時(shí)間回溯TimeWarp技術(shù)大體上與快照回滾是一個(gè)意思的。

4.事件鎖定與時(shí)鐘同步(Event Locking and Clock Synchronization)

1997年，Jim Greer與Zack Booth Simpson在開(kāi)發(fā)出了他們第一款基于CS架構(gòu)的RTS游戲——”NetStorm：Island at war“。隨后在發(fā)布的文章中又提出了“事件鎖定”這一概念[13]，相比幀同步會(huì)受到其他客戶端延遲的影響，事件鎖定是基于事件隊(duì)列嚴(yán)格按序執(zhí)行的，客戶端只管發(fā)消息然后等待服務(wù)器的響應(yīng)即可，其他時(shí)候本地正常模擬，不需要等待。在目前常見(jiàn)的游戲中，我們很少會(huì)聽(tīng)說(shuō)到事件鎖定這種同步方式，因?yàn)槭录i定的本質(zhì)就是通過(guò)RPC產(chǎn)生事件從而進(jìn)行同步（也就是排除屬性同步的狀態(tài)同步）。事件鎖定在CS架構(gòu)上是非常自然的，相比幀同步，可以定義并發(fā)送更靈活的信息，也不必再擔(dān)心作弊的問(wèn)題。

不過(guò)，由于事件中經(jīng)常會(huì)含有時(shí)間相關(guān)的信息（比如在X秒進(jìn)行開(kāi)火）以及服務(wù)器需要對(duì)客戶端的不合法操作進(jìn)行糾正，所以我們需要盡可能的保持客戶端與服務(wù)器的時(shí)鐘同步。實(shí)現(xiàn)時(shí)鐘同步最常見(jiàn)且廣泛的方式就是網(wǎng)絡(luò)時(shí)間協(xié)議（Network Time Protocol，簡(jiǎn)稱NTP）[14]，NTP屬于應(yīng)用層協(xié)議下層采用UDP實(shí)現(xiàn)，1979年誕生以來(lái)至今仍被應(yīng)用在多個(gè)計(jì)算機(jī)領(lǐng)域里，包括嵌入式系統(tǒng)時(shí)間、通信計(jì)費(fèi)、Windows時(shí)間服務(wù)以及部分游戲等。NTP使用了一種樹(shù)狀、半分層的網(wǎng)絡(luò)結(jié)構(gòu)來(lái)部署時(shí)鐘服務(wù)器，每個(gè)UDP數(shù)據(jù)包內(nèi)包含多個(gè)時(shí)間戳以及一些標(biāo)記信息用來(lái)多次校驗(yàn)與分析，

整個(gè)時(shí)鐘同步的具體算法涉及到非常多的細(xì)節(jié)，我們這里只考慮他的時(shí)鐘同步算法（其他的內(nèi)容請(qǐng)參考?xì)v年的RFC）：

假如一個(gè)服務(wù)器與客戶端通信，客戶端在t0向服務(wù)器發(fā)送數(shù)據(jù)，服務(wù)器在t1收到數(shù)據(jù)，t2響應(yīng)并回包給客戶端，最后客戶端在t3時(shí)間收到了服務(wù)器的數(shù)據(jù)。

二者的時(shí)間差為“θ”，假如往返延遲相同，則有

所以可以將“θ”定義為

將往返延遲相加，那么可以得到一個(gè)RTT延遲

當(dāng)然，該操作不會(huì)只執(zhí)行一次，客戶端會(huì)同時(shí)請(qǐng)求多個(gè)服務(wù)器，然后對(duì)結(jié)果進(jìn)行統(tǒng)計(jì)分析、過(guò)濾，并從最好的三個(gè)剩余候選中估算時(shí)間差，然后調(diào)整時(shí)鐘頻率來(lái)逐漸減小偏移。如果我們的系統(tǒng)對(duì)精度要求不是非常高，我們還可以使用簡(jiǎn)化版的SNTP(Simple Network Time Protocal），時(shí)鐘同步算法與NTP是相同的，不過(guò)簡(jiǎn)化了一些流程。

不過(guò)無(wú)論是NTP還是SNTP，對(duì)于游戲來(lái)說(shuō)都過(guò)于復(fù)雜（而且只能用UDP實(shí)現(xiàn)）。因此Jim Greer等人提出了“消除高階的流式時(shí)間同步”，流程如下：

• 1. 客戶端把當(dāng)前本地時(shí)間附在一個(gè)時(shí)間請(qǐng)求數(shù)據(jù)包上，然后發(fā)送給服務(wù)器

• 2. 服務(wù)器收到以后，服務(wù)器附上服務(wù)器時(shí)間戳然后發(fā)回給客戶端

• 3. 客戶端收到之后，用當(dāng)前時(shí)間減去發(fā)送時(shí)間除以2得到延遲。再用當(dāng)前時(shí)間減去服務(wù)器時(shí)間得到客戶端和服務(wù)端時(shí)間差，再加上半個(gè)延遲得到正確的時(shí)鐘差異 delta=(Currenttime - senttime)/2

• 4. 第一個(gè)結(jié)果應(yīng)該立刻被用于更新時(shí)鐘，可以保證本地時(shí)間和服務(wù)器時(shí)間大致一致

• 5. 客戶端重復(fù)步驟1至3多次，每次間隔幾秒鐘。期間可以繼續(xù)發(fā)送其他數(shù)據(jù)包的，但是為了結(jié)果精確應(yīng)該盡量少發(fā)

• 6. 每個(gè)包的時(shí)間差存儲(chǔ)起來(lái)并排序，然后取中位數(shù)作為中間值

• 7.丟棄和中間值偏差過(guò)大（超出一個(gè)標(biāo)準(zhǔn)偏差，或者 超過(guò)中間值1.5倍）的樣例，然后對(duì)剩余樣例取算術(shù)平均

上述算法精髓在于丟棄和中間值偏差超過(guò)一個(gè)標(biāo)準(zhǔn)偏差的數(shù)值。其目的是為了去除TCP中重傳的數(shù)據(jù)包。舉例來(lái)說(shuō)，如果通過(guò)TCP發(fā)送了10個(gè)數(shù)據(jù)包，而且沒(méi)有重傳。這時(shí)延遲數(shù)據(jù)將集中在延遲的中位數(shù)附近。假如另一個(gè)測(cè)試中，如果其中第10個(gè)數(shù)據(jù)包被重傳了，重傳將導(dǎo)致這次的采樣在延遲柱狀圖中極右端，處于延遲中位數(shù)兩倍的位置。通過(guò)直接去掉超出中位數(shù)一個(gè)標(biāo)準(zhǔn)偏差的樣例，可以過(guò)濾掉因重傳導(dǎo)致的不準(zhǔn)確樣例。（排除網(wǎng)絡(luò)很差重傳頻繁發(fā)生的情況）

5.插值技術(shù)?（Interpolation and Extrapolation ）

插值技術(shù)在早期的幀同步就被應(yīng)用到游戲里面了?；蛘哒f(shuō)更早的時(shí)候就被應(yīng)用到軍事模擬，路徑導(dǎo)航等場(chǎng)景中。插值分為內(nèi)插值[15]（ interpolation ）以及外插值[16]（extrapolation，或者叫外推法）兩種。

內(nèi)插值是一種通過(guò)已知的、離散的數(shù)據(jù)點(diǎn)，在范圍內(nèi)推求新數(shù)據(jù)點(diǎn)的方法（重建連續(xù)的數(shù)據(jù)信息），常見(jiàn)于各種信號(hào)處理和圖像處理。在這篇文章中，我們指根據(jù)已知的離散點(diǎn)在一定時(shí)間內(nèi)按照一定算法去模擬在點(diǎn)間的移動(dòng)路徑。內(nèi)插值具體的實(shí)現(xiàn)方法有很多，如

片段插值（Piecewise constant interpolation）線性插值（Linear interpolation）多項(xiàng)式插值（Polynomial interpolation）樣條曲線插值（Spline interpolation）三角內(nèi)插法（trigonometric interpolation）有理內(nèi)插（rational interpolation小波內(nèi)插（wavelets interpolation）

多項(xiàng)式插值與線性插值對(duì)比

外插值，指從已知數(shù)據(jù)的離散集合中構(gòu)建超出原始范圍的新數(shù)據(jù)的方法，也可以指根據(jù)過(guò)去和現(xiàn)在的發(fā)展趨勢(shì)來(lái)推斷未來(lái)，屬于統(tǒng)計(jì)學(xué)上的概念。與外插值還有一個(gè)相似的概念稱為DeadReckoning（簡(jiǎn)稱DR），即導(dǎo)航推測(cè)。DR是一種利用現(xiàn)在物體位置及速度推定未來(lái)位置方向的航海技術(shù)，屬于應(yīng)用技術(shù)方向的概念。DR的概念更貼近游戲領(lǐng)域，即給定一個(gè)點(diǎn)以及當(dāng)前的方向等信息，推測(cè)其之后的移動(dòng)路徑，外推的算法也有很多種，

線性外推（Linear extrapolation）多項(xiàng)式外推（Polynomial extrapolation）錐形外推 （Conic extrapolation）云形外推 （French curve extrapolation）

在游戲中，一般按照線性外推或勻變速直線運(yùn)動(dòng)推測(cè)即可。不過(guò)，對(duì)于比較復(fù)雜的游戲類型，我們也可以采用三次貝塞爾曲線、向心Catmull-Rom曲線等模擬預(yù)測(cè)。

總之，無(wú)論是內(nèi)插值還是外插值，考慮到運(yùn)算的復(fù)雜度以及表現(xiàn)要求，游戲中以線性插值、簡(jiǎn)單的多項(xiàng)式插值為主。

應(yīng)用：

早期的lockstep算法中，在一個(gè)客戶端在收到下一幀信息前，為了避免本地其他角色靜止卡頓，會(huì)采用外插值來(lái)推斷其接下來(lái)一小段時(shí)間的移動(dòng)路徑[17][18]。普通DR存在一個(gè)問(wèn)題（參考下圖），t0時(shí)刻其他客戶端收到了主機(jī)的同步信息預(yù)測(cè)向虛線的方向移動(dòng)，不過(guò)主機(jī)客戶端卻開(kāi)始向紅色路徑方向移動(dòng)，等其他客戶端在t1時(shí)刻收到同步信息后會(huì)被突然拉倒t1'的位置，這造成了玩家不好的游戲體驗(yàn)。為了解決從預(yù)測(cè)位置拉扯到真實(shí)位置造成的視覺(jué)突變，我們會(huì)增加一些相應(yīng)的算法來(lái)將預(yù)測(cè)對(duì)象平滑地移動(dòng)到真實(shí)位置。

在狀態(tài)同步中，由于客戶端每次收到的是其他的角色的位置信息，為了避免位置突變，本地會(huì)采用內(nèi)插值來(lái)從A點(diǎn)過(guò)度到B點(diǎn)。插值的目的很簡(jiǎn)單，就是為了保證在同步數(shù)據(jù)到來(lái)之前讓本地的角色能有流暢的表現(xiàn)。

— 未完待續(xù) —

—? ?覺(jué)得不錯(cuò)請(qǐng)幫忙轉(zhuǎn)發(fā)、分享、點(diǎn)個(gè)在看吧? ?—

游戲開(kāi)發(fā)那些事

回復(fù)"gamebook",獲取游戲開(kāi)發(fā)書籍

回復(fù)"C++面試",獲取C++/游戲面試經(jīng)驗(yàn)

回復(fù)"操作系統(tǒng)",獲取操作系統(tǒng)經(jīng)典書籍

游戲開(kāi)發(fā)交流群(875867499)

往期熱門文章：

如何學(xué)習(xí)大型項(xiàng)目的源碼？

史上最全的C++/游戲開(kāi)發(fā)面試問(wèn)題總結(jié)

游戲中的角色是如何“動(dòng)”起來(lái)的？

參考文獻(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]