Node.js 製作即時多人遊戲框架_node.js

在 Node.js 如火如荼發展的今天，我們已經可以用它來做各種各樣的事情。前段時間UP主參加了極客鬆活動，在這次活動中我們意在做出一款讓「低頭族」能夠更多交流的遊戲，核心功能便是 Lan Party 概念的即時多人互動。極客鬆比賽只有短得可憐的36小時，要求一切都敏捷迅速。在這樣的前提下初期的準備顯得有些「水到渠成」。跨平台應用的 solution 我們選擇了node-webkit，它足夠簡單且符合我們的要求。

依照需求，我們的開發可以依照模組分開進行。本文具體講述了開發 Spaceroom（我們的即時多人遊戲框架）的過程，包括一系列的探索與嘗試，以及對 Node.js、WebKit 平臺本身的一些限制的解決，和解決方案的提出。

Getting started
Spaceroom 一瞥
在最開始，Spaceroom 的設計肯定是需求驅動的。我們希望這個框架可以提供以下的基礎功能：

能夠以 房間(或說頻道) 為單位，區分一組使用者
能夠接收收集群組內使用者發送的指令
在各個客戶端之間對時，能夠按照規定的 interval 精確廣播遊戲數據
能夠盡量消除網路延遲帶來的影響
當然，在coding 的後期，我們為Spaceroom 提供了更多的功能，包括暫停遊戲、在各個客戶端之間產生一致的隨機數等（當然根據需求這些都可以在遊戲邏輯框架裡自己實現，並非一定需要用到Spaceroom 這個更多在通訊層面工作的框架）。

APIs
Spaceroom 分為前後端兩部分。伺服器端所需要做的工作包括維護房間列表，提供建立房間、加入房間的功能。我們的客戶端 APIs 看起來像這樣:

spaceroom.connect(address, callback) – 連線伺服器
spaceroom.createRoom(callback) – 建立一個房間
spaceroom.joinRoom(roomId) – 加入一個房間
spaceroom.on(event, callback) – 監聽事件
……
客戶端連接到伺服器後，會收到各種各樣的事件。例如在一間房間中的用戶，可能會收到新玩家加入的事件，或是遊戲開始的事件。我們給了客戶“生命週期”，他在任何時候都會處於以下狀態的一種：

 

你可以透過 spaceroom.state 取得客戶端的目前狀態。

使用伺服器端的框架相對來說簡單很多，如果使用預設的設定文件，那麼直接運行伺服器端框架就可以了。我們有一個基本的需求：伺服器程式碼 可以直接運行在客戶端中，而不需要一個單獨的伺服器。玩過 PS 或 PSP 的玩家應該要清楚我在說什麼。當然，可以跑在專門的伺服器裡，自然也是極好的。

邏輯程式碼的實作這裡簡略了。初代的 Spaceroom 完成了一個 Socket 伺服器的功能，它維護房間列表，包括房間的狀態，以及每個房間對應的遊戲時通訊（指令收集，bucket 廣播等）。具體實作可以參考源碼。

同步演算法

那麼，要怎麼才能使得各個客戶端之間顯示的東西都是即時一致的呢？

這個東西聽起來很有趣。仔細想想，我們需要伺服器幫我們傳遞什麼東西？自然就會想到是什麼可能造成各個客戶端之間邏輯的不一致：使用者指令。既然處理遊戲邏輯的程式碼都是相同的，那麼給定同樣的條件，程式碼的運作結果也是相同的。唯一不同的就是在遊戲過程當中，接收到的各種玩家指令。理所當然的，我們需要一種方式來同步這些指令。如果所有的客戶端都能拿到同樣的指令，那麼所有的客戶端從理論上就能有一樣的運作結果了。

網路遊戲的同步演算法千奇百怪，適用的場景也各不相同。 Spaceroom 採用的同步演算法類似於幀鎖定的概念。我們把時間軸分成了一個一個的區間，每一個區間都稱為一個 bucket。 Bucket 是用來裝載指令的，由伺服器端維護。在每一個 bucket 時間段的結尾，伺服器把 bucket 廣播給所有客戶端，客戶端拿到 bucket 之後從中取出指令，驗證之後執行。

為了降低網路延遲造成的影響，伺服器接到的來自客戶端的指令每一個都會按照一定的演算法投遞到對應的 bucket 中，具體按照以下步驟：

設 order_start 為指令所攜帶的指令發生時間， t 為 order_start 所在 bucket 的起始時間
如果 t delay_time 將指令投遞到 t delay_time 對應的 bucket 中
其中delay_time 為約定的伺服器延遲時間，可以取為客戶端之間的平均延遲，Spaceroom 裡預設取值80，以及bucket 長度預設取值48. 在每個bucket 時間段的末尾，伺服器將此bucket 廣播給所有客戶端，並開始接收下一個bucket 的指令。客戶端根據收到的 bucket 間隔，在邏輯中自動進行對時，將時間誤差控制在一個可以接受的範圍內。

這個意思是，正常情況下，客戶端每隔 48ms 會收到從伺服器端發來的一個 bucket，當到達需要處理這個 bucket 的時間時，客戶端會進行相應處理。假設客戶端 FPS=60，每隔 3幀 左右的時間，會收到一次 bucket，根據這個 bucket 來更新邏輯。如果因為網路波動，超出時間後還沒有收到 bucket，客戶端暫停遊戲邏輯並等待。在一個 bucket 之內的時間，邏輯的更新可以使用 lerp 的方法。

在 delay_time = 80, bucket_size = 48 的情況下，任一指令最少會被延遲 96ms 執行。改變這兩個參數，例如在 delay_time = 60, bucket_size = 32 的情況下，任一指令最少會被延遲 64ms 執行。

計時器引發的血案

整個看下來，我們的框架在運作的時候需要有一個精確的計時器。在固定的 interval 下執行 bucket 的廣播。理所當然地，我們首先想到了使用setInterval()，然而下一秒我們就意識到這個想法有多麼的不靠譜：調皮的setInterval() 似乎有非常嚴重的誤差。而且要命的是，每次的誤差都會累積起來，造成越來越嚴重的後果。

於是我們馬上又想到了使用 setTimeout()，透過動態地修正下一次到時的時間來讓我們的邏輯大致穩定在規定的 interval 左右。例如這次setTimeout()比預期少了5ms, 那麼我們下次就讓他提前5ms. 不過測試結果不盡人意，而且這怎麼看都不夠優雅。

所以我們又要換一個思路。是否可以讓 setTimeout() 盡可能快速地到期，然後我們檢查當前的時間是否到達目標時間。例如在我們的循環中，使用setTimeout(callback, 1) 來不停地檢查時間，這看起來像是一個不錯的主意。

令人失望的計時器
我們立即寫了一段程式碼來測試我們的想法，結果令人失望。在目前最新的node.js 穩定版(v0.10.32)以及 Windows 平台下，運行這樣一段程式碼：

複製程式碼 程式碼如下:

var sum = 0, count = 0; 
function test() { 
  var now = Date.now(); 
  setTimeout(function () { 
    var diff = Date.now() - now; 
    sum = diff; 
    count ; 
    test(); 
  }); 
} 
test(); 

一段時間之後在控制台裡輸入 sum/count，可以看到一個結果，類似：

複製程式碼 程式碼如下:

> sum / count 
15.624555160142348 

什麼?!!我要 1ms 的間隔時間，你卻告訴我實際的平均間隔為 15.625ms！這個畫面簡直是太美。我們在 mac 上做同樣的測試，得到的結果是 1.4ms。於是我們心生疑惑：這到底是什麼鬼？如果我是一個果粉，我可能就要得出 Windows 太垃圾然後放棄 Windows 的結論了，不過好在我是一名嚴謹的前端工程師，於是我開始繼續思索起這個數字來。

等等，這個數字為什麼那麼眼熟？ 15.625ms 這個數字會不會太像 Windows 下的最大計時器間隔了？立即下載了一個 ClockRes 進行測試，控制台一跑果然得到瞭如下結果：

複製程式碼 程式碼如下:

Maximum timer interval: 15.625 ms 
Minimum timer interval: 0.500 ms 
Current timer interval: 1.001 ms 

果不其然！查閱 node.js 的手冊我們可以看到這樣一段對 setTimeout 的描述：
 
The actual delay depends on external factors like OS timer granularity and system load.
然而測試結果顯示，這個實際延遲是最大計時器間隔(注意此時系統的當前計時器間隔只有1.001ms)，無論如何讓人無法接受，強大的好奇心驅使我們翻翻看node.js 的源碼來一窺究竟。

Node.js 中的 BUG

相信大部分你我都對Node.js 的even loop 機制有一定的了解，查看timer 實現的源碼我們可以大致了解到timer 的實現原理，讓我們從event loop 的主循環講起：
 

複製程式碼 程式碼如下:

while (r != 0 && loop->stop_flag == 0) { 
    /* 更新全域時間 */ 
    uv_update_time(loop); 
    /* 檢查計時器是否到期，並執行對應計時器回呼 */ 
    uv_process_timers(loop); 
 
    /* Call idle callbacks if nothing to do. */ 
    if (loop->pending_reqs_tail == NULL && 
        loop->endgame_handles == NULL) { 
      /* 防止event loop退出 */ 
      uv_idle_invoke(loop); 
    } 
 
    uv_process_reqs(loop); 
    uv_process_endgames(loop); 
 
    uv_prepare_invoke(loop); 
 
    /* 收集 IO 事件 */ 
    (*poll)(loop, loop->idle_handles == NULL && 
                  loop->pending_reqs_tail == NULL && 
                  loop->endgame_handles == NULL && 
                  !loop->stop_flag && 
                  (loop->active_handles > 0 || 
                   !ngx_queue_empty(&loop->active_reqs)) && 
                  !(mode & UV_RUN_NOWAIT)); 
    /* setImmediate() 等 */ 
    uv_check_invoke(loop); 
    r = uv__loop_alive(loop); 
    if (mode & (UV_RUN_ONCE | UV_RUN_NOWAIT)) 
      break; 
  } 

其中 uv_update_time 函數的源碼如下：（https://github.com/joyent/libuv/blob/v0.10/src/win/timer.c））

複製程式碼 程式碼如下:

void uv_update_time(uv_loop_t* loop) { 
  /* 取得目前系統時間 */ 
  DWORD ticks = GetTickCount(); 
 
  /* The assumption is made that LARGE_INTEGER.QuadPart has the same type */ 
  /* loop->time, which happens to be. Is there any way to assert this? */ 
  LARGE_INTEGER* time = (LARGE_INTEGER*) &loop->time; 
 
  /* If the timer has wrapped, add 1 to it's high-order dword. */ 
  /* uv_poll must make sure that the timer can never overflow more than */ 
  /* once between two subsequent uv_update_time calls. */ 
  if (ticks LowPart) { 
    time->HighPart = 1; 
  } 
  time->LowPart = ticks; 
} 

此函數的內部實現，使用了 Windows 的 GetTickCount() 函數來設定目前時間。簡單來說，在呼叫setTimeout 函數之後，經過一連串的掙扎，內部的 timer->due 會被設定為目前 loop 的時間 timeout。在 event loop 中，先透過 uv_update_time 更新目前 loop 的時間，然後在uv_process_timers 中檢查是否有計時器到期，如果有就進入 JavaScript 的世界。通篇讀下來，event loop大概是這樣一個流程：

更新全域時間

檢查定時器，如果有定時器過期，執行回呼
檢查 reqs 佇列，執行正在等待的請求
進入 poll 函數，收集 IO 事件，如果有 IO 事件到來，將對應的處理函數新增到 reqs 佇列中，以便在下一次 event loop 中執行。在 poll 函數內部，呼叫了一個系統方法來收集 IO 事件。這個方法會讓進程阻塞，直到有 IO 事件到來或是到達設定好的逾時時間。呼叫這個方法時，超時時間設定為最近的一個 timer 到期的時間。意思是阻塞收集 IO 事件，最大阻塞時間為 下一個 timer 的到底時間。
Windows下 poll 函數之一的原始碼：

複製程式碼 程式碼如下:

static void uv_poll(uv_loop_t* loop, int block) { 
  DWORD bytes, timeout; 
  ULONG_PTR key; 
  OVERLAPPED* overlapped; 
  uv_req_t* req; 
  if (block) { 
    /* 取出最近的一個計時器的過期時間 */ 
    timeout = uv_get_poll_timeout(loop); 
  } else { 
    timeout = 0; 
  } 
  GetQueuedCompletionStatus(loop->iocp, 
                            &bytes, 
                            &key, 
                            &overlapped, 
                           /* 阻塞至下個計時器到期 */ 
                            timeout); 
  if (overlapped) { 
    /* Package was dequeued */ 
    req = uv_overlapped_to_req(overlapped); 
    /* 把 IO 事件插入佇列 */ 
    uv_insert_pending_req(loop, req); 
  } else if (GetLastError() != WAIT_TIMEOUT) { 
    /* Serious error */ 
    uv_fatal_error(GetLastError(), "GetQueuedCompletionStatus"); 
  } 
} 

按照上述步驟，假設我們設定了一個 timeout = 1ms 的計時器，poll 函數會阻塞最多 1ms 之後恢復（如果期間沒有任何 IO 事件）。在繼續進入 event loop 迴圈的時候， uv_update_time 就會更新時間，然後uv_process_timers 發現我們的計時器到期，執行回呼。所以初步的分析是，要么是uv_update_time 出了問題（沒有正確地更新當前時間），要么是 poll 函數等待 1ms 之後恢復，這個 1ms 的等待出了問題。

查閱 MSDN，我們驚人地發現 GetTickCount 函數的描述：

The resolution of the GetTickCount function is limited to the resolution of the system timer, which is typically in the range of 10 milliseconds to 16 milliseconds.
 
GetTickCount 的精度是如此的粗糙！假設 poll 函數正確地阻塞了 1ms 的時間，然而下一次執行uv_update_time 的時候並沒有正確地更新目前 loop 的時間！所以我們的計時器沒有被判定為過期，於是 poll 又等了 1ms，又進入了下一次 event loop。直到終於 GetTickCount 正確地更新了（所謂15.625ms更新一次），loop 的當前時間被更新，我們的計時器才在 uv_process_timers 裡被判定過期。

向 WebKit 求助
Node.js 的這段原始碼看得人很無助：他使用了一個精度低下的時間函數，而且沒有做任何處理。不過我們立刻想到了既然我們使用 Node-WebKit，那麼除了 Node.js 的 setTimeout，我們還有 Chromium 的 setTimeout。寫一段測試程式碼，用我們的瀏覽器或Node-WebKit 跑一下：http://marks.lrednight.com/test.html#1 (#後面跟的數字表示需要測定的間隔) ，結果如下圖：

依照 HTML5 的規範，理論結果應該是前5次結果是1ms，以後的結果是4ms。測試案例中顯示的結果是從第3次開始的，也就是說表上的資料理論上應該是前3次都是1ms，之後的結果都是4ms。結果有一定的誤差，而且根據規定，我們能得到的最小的理論結果是4ms。雖然我們不滿足，但顯然這比 node.js 的結果讓我們滿意多了。強大的好奇心趨勢我們看看 Chromium 的源碼，看看他是如何實現的。 (https://chromium.googlesource.com/chromium/src.git/ /38.0.2125.101/base/time/time_win.cc)

首先，在決定 loop 的當前時間方面，Chromium 使用了 timeGetTime() 函數。查閱 MSDN 可以發現這個函數的精度受系統目前 timer interval 影響。在我們的測試機上，理論上也就是上文中提到的 1.001ms。然而 Windows 系統預設情況下，timer interval 是其最大值（測試機上也就是 15.625ms），除非應用程式修改了全域 timer interval。

如果你有在關注 IT界的新聞，你一定看過這樣的一則新聞。看起來我們的 Chromium 把計時器間隔設定得很小了嘛！看來我們不用擔心系統計時器間隔的問題了？不要開心得太早，這樣的一條修復給了我們當頭一棒。事實上，這個問題在 Chrome 38 中已經得到了修復。難道我們要使用修復以前的 Node-WebKit？這顯然不夠優雅，而且阻止了我們使用性能更高的 Chromium 版本。

進一步查看 Chromium 原始碼我們可以發現，在有計時器，且計時器的 timeout

複製程式碼 程式碼如下:

void Time::EnableHighResolutionTimer(bool enable) { 
  基礎::AutoLock 鎖(g_high_res_lock.Get()); 
  if (g_high_res_timer_enabled == 啟用)
    回; 
  g_high_res_timer_enabled = 啟用； 
  if (!g_high_res_timer_count)
    回; 
  // 由於 g_high_res_timer_count != 0，ActivateHighResolutionTimer(true) 
  // 被調用，其中使用 g_high_res_timer_enabled 調用 timeBeginPeriod
  // 其值與 |enable| 相反。有了這些信息，我們
  // 使用 timeBeginPeriod 和
中使用的相同值來呼叫 timeEndPeriod   // 因此撤銷週期效應。 
  如果（啟用）{ 
    timeEndPeriod(kMinTimerIntervalLowResMs); 
    timeBeginPeriod(kMinTimerIntervalHighResMs); 
  } 其他 { 
    timeEndPeriod(kMinTimerIntervalHighResMs); 
    timeBeginPeriod(kMinTimerIntervalLowResMs); 
  } 
} 

其中，kMinTimerIntervalLowResMs = 4，kMinTimerIntervalHighResMs = 1。 timeBeginPeriod 以及timeEndPeriod 是Windows提供的用於修改系統定時器間隔的函數。接下來在接電源時，我們能得到的最小的定時器間隔是1ms，而使用電池時，是4ms。由於我們的循環不斷地呼叫了setTimeout，根據W3C規範，最小的間隔也是4ms，所以鬆口氣，這個對我們的影響不大。

另一個精準度問題

回到開頭，我們發現測試結果顯示，setTimeout的間隔不是穩定在4ms的，而是在不斷地波動。而http://marks.lrednight.com/test.html#48 測試結果也顯示，間隔在 48ms 和 49ms 之間跳動。原因是，在 Chromium 和 Node.js 的事件循環中，等待 IO 事件的那個 Windows 函數呼叫的精確度，受目前系統的計時器影響。遊戲邏輯的實作需要用到 requestAnimationFrame 函數（不間斷更新時鐘），這個函數可以幫助我們將計時器間隔至少設定為 kMinTimerIntervalLowResMs（因為他需要一個 16ms 的計時器，觸發了計時器計時器的要求）。測試機使用電源供應器的時候，系統的定時器間隔是1ms，所以測試結果有±1ms的時鐘。如果你的電腦沒有被更改系統計時器間隔，執行上面那個#48的測試，max可能會到48 16=64ms。

利用 Chromium 的 setTimeout 實現，我們可以將 setTimeout(fn, 1) 的托盤控制在 4ms 左右，而 setTimeout(fn, 48) 的托盤可以控制在 1ms 左右。於是，我們的心中有了一個新的想法的藍圖，它讓我們的程式碼看起來像這樣：

複製程式碼程式碼如下：

/* 取得最大間隔偏差 */ 
var 偏差 = getMaxIntervalDeviation(bucketSize); // 桶大小 = 48, 偏差 = 2; 
函數 gameLoop() { 
  var now = Date.now(); 
  if (previousBucket bucketSize     以前的桶子=現在； 
    doLogic(); 
  } 
  if (previousBucket bucketSize - Date.now() > 偏差) { 
    // 等待 46 毫秒。實際延遲小於48ms。 
    setTimeout(gameLoop,bucketSize-偏差); 
  } 其他 { 
    // 忙著等待。使用 setImmediate 而不是 process.nextTick，因為前者不會阻止 IO 事件。 
    setImmediate(遊戲循環); 
  } 
} 

上面的程式碼讓我們等待一個誤差小於 bucket_size( bucket_size – deviation) 的時間而不是直接等於一個 bucket_size，46ms 的 delay 即便發生了最大的誤差，根據上文的理論，實際間隔也是小於48ms的。剩下的時間我們使用忙等待的方法，確保我們的 gameLoop 在足夠精確的 interval 下執行。

雖然我們利用 Chromium 在一定程度上解決了問題，但這顯然不夠優雅。

還記得我們最初的要求嗎？我們的伺服器端程式碼是應該可以脫離 Node-Webkit 用戶端的，直接在一台有 Node.js 環境的電腦中運作。如果直接跑上面的程式碼，deviation 的值至少是16ms，也就是說在每一個48ms中，我們要忙等待16ms的時間。 CPU使用率蹭蹭就上去了。

意想不到的驚喜

真是氣人啊，Node.js 裡這麼大的一個BUG，沒人注意到嗎？答案真是讓我們喜出望外。這個BUG在 v.0.11.3 版本裡已經修復了。直接查看 libuv 程式碼的 master 分支也能看到修改後的結果。具體的做法是，在 poll 函數等待完成之後，把 loop 的當前時間，加上一個 timeout。這樣即便 GetTickCount 沒有反應過來，在經過poll的等待後，我們還是加上了這段等待的時間。於是計時器就能夠順利地到期了。

也就是說，辛苦半天的問題，在 v.0.11.3 裡已經解決了。不過，我們的努力不是白費的。因為即便消除了 GetTickCount 函數的影響，poll 函數本身也受到系統計時器的影響。解決方案之一，便是編寫 Node.js 插件，更改系統定時器的間隔。

不過我們這次的遊戲，初步設定是沒有伺服器的。客戶端建立房間之後，就成為了一個伺服器。伺服器程式碼可以跑在 Node-WebKit 的環境中，所以 Windows 系統下計時器的問題的優先順序並不是最高的。按照上文中我們給出的解決方案，結果已經足夠讓我們滿意。

收尾

解決了計時器的問題，我們的框架實作基本上再沒什麼阻礙了。我們提供了 WebSocket 的支援（在純 HTML5 環境下），也自訂了通訊協定實現了效能更高的 Socket 支援（Node-WebKit 環境下）。當然，Spaceroom 的功能在最初是比較簡陋的，但隨著需求的提出和時間的增加，我們也逐漸地完善這個框架。

例如我們發現在我們的遊戲裡需要產生一致的隨機數的時候，我們就為 Spaceroom 加上了這樣的功能。在遊戲開始的時候 Spaceroom 會分發隨機數種子，客戶端的 Spaceroom 提供了利用 md5 的隨機性，借助隨機數種子產生隨機數的方法。

看起來還是蠻欣慰的。在寫這樣一個框架的過程當中，也學到了很多的東西。如果你對 Spaceroom 有點興趣，也可以參與它當中。相信，Spaceroom 會在更多的地方施展它的拳腳。