リアルタイム マルチプレイヤー ゲームを作成するための Node.js フレームワーク_node.js

現在、Node.js の開発が本格的に行われており、すでに Node.js を使用してさまざまなことができるようになりました。少し前に、UP オーナーは Geek Song イベントに参加しました。このイベントでは、「低レベルの人々」がよりコミュニケーションできるようにするゲームを作成することを目指していました。ランパーティーのコンセプト。 Geek Pine コンテストの開催時間は哀れなほど短く 36 時間で、すべてが素早く行われることが求められます。そのような前提の下では、最初の準備は少し「自然」に見えました。クロスプラットフォーム アプリケーションのソリューションとして、十分にシンプルで要件を満たす Node-Webkit を選択しました。

ニーズに応じて、モジュールに応じて個別に開発を行うことができます。この記事では、一連の探索と試み、Node.js および WebKit プラットフォーム自体のいくつかの制限の解決、およびソリューションの提案を含む、Spaceroom (当社のリアルタイム マルチプレイヤー ゲーム フレームワーク) の開発プロセスについて詳しく説明します。

はじめに
スペースルームの概要
当初から、Spaceroom のデザインは間違いなくニーズ主導型でした。このフレームワークが次の基本機能を提供できることを期待しています:

ルーム (またはチャンネル) 単位でユーザーのグループを区別できるようになります
コレクショングループ内のユーザーから指示を受け取ることができます
各クライアント間の時刻同期により、指定された間隔に従ってゲームデータを正確にブロードキャストできます
ネットワーク遅延による影響を最小限に抑えることができます
もちろん、コーディングの後半段階で、ゲームの一時停止、さまざまなクライアント間で一貫した乱数の生成など、Spaceroom にさらに多くの機能を提供しました (もちろん、これらは必要に応じてゲーム ロジック フレームワークに実装できますが、必ずしも、コミュニケーション レベルで機能するフレームワークである Spaceroom を使用する必要があるわけではありません)。

API
Spaceroom は、フロントエンドとバックエンドの 2 つの部分に分かれています。サーバー側で必要な作業には、ルーム リストの管理、ルームの作成およびルームへの参加機能の提供が含まれます。クライアント API は次のようになります:

spaceroom.connect(address, callback) – サーバーに接続します
spaceroom.createRoom(callback) – ルームを作成します
spaceroom.joinRoom(roomId) – ルームに参加します
spaceroom.on(event, callback) – イベントをリッスンします
…
クライアントがサーバーに接続すると、さまざまなイベントを受信します。たとえば、ルーム内のユーザーは、新しいプレイヤーが参加した、またはゲームが開始されたというイベントを受信する場合があります。クライアントには「ライフサイクル」が与えられており、常に次のいずれかの状態になります:

spaceroom.state を通じてクライアントの現在の状態を取得できます。

サーバー側フレームワークの使用は比較的簡単です。デフォルトの構成ファイルを使用する場合は、サーバー側フレームワークを直接実行するだけです。基本的な要件があります。それは、別のサーバーを必要とせずに、サーバー コードがクライアント内で直接実行できることです。 PS や PSP でプレイしたことがある人なら、私が何を言っているのか正確にわかるでしょう。もちろん専用サーバー上で動作させることもできるので当然優秀です。

ロジック コードの実装はここで簡略化されています。第一世代の Spaceroom は、ルームのステータスを含むルームのリストと、各ルームに対応するゲーム時の通信 (コマンド収集、バケット ブロードキャストなど) を維持するソケット サーバーの機能を完成させました。具体的な実装についてはソースコードを参照してください。

同期アルゴリズム

それでは、各クライアント間で表示される内容をリアルタイムで一貫させるにはどうすればよいでしょうか?

これは面白そうですね。よく考えてみましょう。合格するにはサーバーに何が必要でしょうか?さまざまなクライアント間で論理的な不一致を引き起こす可能性があるもの、つまりユーザーの指示について考えるのは自然なことです。ゲームロジックを扱うコードはすべて同じであるため、同じ条件を与えられた場合、コードの結果は同じになります。唯一の違いは、ゲーム中に受け取るさまざまなプレーヤーの指示です。もちろん、これらの命令を同期する方法が必要です。すべてのクライアントが同じ命令を取得できる場合、理論的にはすべてのクライアントが同じ実行結果を得ることができます。

オンライン ゲームの同期アルゴリズムはさまざまであり、適用されるシナリオも異なります。 Spaceroom で使用される同期アルゴリズムは、フレーム ロックの概念に似ています。タイムラインを間隔に分割し、各間隔をバケットと呼びます。バケットは命令をロードするために使用され、サーバーによって維持されます。各バケット期間の終了時に、サーバーはバケットをすべてのクライアントにブロードキャストします。クライアントがバケットを取得した後、バケットから命令をフェッチし、検証後に実行します。

ネットワーク遅延の影響を軽減するために、サーバーがクライアントから受信した各命令は、特定のアルゴリズムに従って対応するバケットに配信されます。

order_start が命令によって運ばれる命令の発生時刻、t が order_start が配置されているバケットの開始時刻であると仮定します
t late_time t 遅延_時間
に対応するバケットにコマンドを配信します。 このうち、Delay_time は合意されたサーバー遅延時間であり、クライアント間の平均遅延とみなすことができます。Spaceroom のデフォルト値は 80、バケット長のデフォルト値は 48 です。各バケット期間の終了時に、サーバーはこのバケットをブロードキャストし、すべてのクライアントが次のバケットに対する指示の受信を開始します。クライアントは、受信したバケット間隔に基づいてロジックで時刻調整を自動的に実行し、時刻誤差を許容範囲内に制御します。

これは、通常の状況では、クライアントは 48 ミリ秒ごとにバケットをサーバーから受信し、バケットの処理時間に達すると、それに応じてバケットを処理することを意味します。クライアントの FPS=60 と仮定すると、約 3 フレームごとにバケットが受信され、このバケットに基づいてロジックが更新されます。ネットワークの変動により時間を超えてもバケットが受信されない場合、クライアントはゲーム ロジックを一時停止して待機します。バケット内では、論理更新で lerp メソッドを使用できます。

Delay_time = 80、bucket_size = 48 の場合、すべての命令は少なくとも 96ms 遅延します。これら 2 つのパラメータを変更すると、たとえば、lay_time = 60、bucket_size = 32 の場合、すべての命令は少なくとも 64ms 遅延します。

タイマーが引き起こした殺人

全体的に見ると、フレームワークには実行時に正確なタイマーが必要です。一定間隔でバケットブロードキャストを行います。もちろん、最初は setInterval() を使用することを考えましたが、次の瞬間にこの考えがいかに信頼性に欠けているかに気づきました。いたずらな setInterval() には非常に重大なエラーがあるようでした。そして恐ろしいのは、あらゆる間違いが蓄積され、ますます深刻な結果を引き起こすことです。

そこで、すぐに setTimeout() を使用して次回の到着時間を動的に修正し、指定された間隔付近でロジックをほぼ安定した状態に保つことを考えました。たとえば、今回の setTimeout() は予想より 5 ミリ秒短かったので、次回は 5 ミリ秒早くします。ただし、テスト結果は満足のいくものではなく、これは十分にエレガントではありません。

そこで、私たちは再び考え方を変える必要があります。 setTimeout() をできるだけ早く期限切れにして、現在の時間が目標時間に達しているかどうかを確認することはできますか。たとえば、このループでは、 setTimeout(callback, 1) を使用して時間を常にチェックするのが良いように思えます。

残念なタイマー
私たちはすぐにコードを書いてアイデアをテストしましたが、結果は残念なものでした。最新の安定バージョンのnode.js (v0.10.32) および Windows プラットフォームで、次のコードを実行します:

コードをコピーします コードは次のとおりです:

変数合計 = 0、カウント = 0; 関数 test() {
var now = Date.now(); setTimeout(function() {
var diff = Date.now() - 今; 合計 = 差分
カウント ; テスト();
});
}
テスト();



しばらくしてから、コンソールに sum/count を入力すると、次のような結果が表示されます:

コードをコピーします

コードは次のとおりです: > 合計 / カウント 15.624555160142348

何?! 1 ミリ秒の間隔を要求したのに、実際の平均間隔は 15.625 ミリ秒だと言われました。この写真はとにかく美しすぎます。 Mac で同じテストを行ったところ、1.4 ミリ秒という結果が得られました。そこで私たちは、「これは一体何だろう？」と疑問に思いました。私が Apple ファンだったら、Windows はゴミすぎると結論付けて Windows を諦めなければならないかもしれませんが、幸いなことに私は厳格なフロントエンド エンジニアなので、この数字について考え始めました。

ちょっと待って、なぜこの数字に見覚えがあるのでしょうか? 15.625ms という数値は、Windows の最大タイマー間隔に近すぎますか?すぐにテスト用に ClockRes をダウンロードし、コンソールで実行すると、次の結果が得られました:

コードをコピー

コードは次のとおりです:

最大タイマー間隔: 15.625 ミリ秒
最小タイマー間隔: 0.500 ミリ秒
現在のタイマー間隔: 1.001 ミリ秒

予想通り！ Node.js マニュアルを見ると、setTimeout について次のような説明があります。

実際の遅延は、OS タイマーの粒度やシステム負荷などの外部要因によって異なります。
ただし、テスト結果は、この実際の遅延が最大タイマー間隔であることを示しています (現時点でのシステムの現在のタイマー間隔はわずか 1.001 ミリ秒であることに注意してください)。これはいずれにせよ、私たちの強い好奇心が私たちをソース コードに注目させました。 node.js を詳しく見てみましょう。

Node.js のバグ

皆さんも私も Node.js の偶数ループの仕組みについてはある程度理解していると思いますが、タイマー実装のソースコードを見てみると、タイマーの実装原理は大体理解できると思います。イベントループのループ:

コードをコピー コードは次のとおりです:

while (r != 0 && ループ->stop_flag == 0) {
/* 世界時刻を更新します */
uv_update_time(ループ); /* タイマーが期限切れになったかどうかを確認し、対応するタイマー コールバックを実行します */
uv_process_timers(ループ);
/* 何もしない場合はアイドル状態のコールバックを呼び出します */
If (loop->pending_reqs_tail == NULL &&
ループ->endgame_handles == NULL) {
/* イベントループが終了しないようにします */
uv_idle_invoke(loop); }

uv_process_reqs(ループ); uv_process_endgames(ループ);
uv_prepare_invoke(ループ);
/* IO イベントを収集 */
(*poll)(loop,loop->idle_handles == NULL &&
ループ->pending_reqs_tail == NULL &&
ループ->エンドゲームハンドル == NULL &&
!loop->stop_flag &&
(ループ->アクティブハンドル> 0 ||
!ngx_queue_empty(&loop->active_reqs)) &&
!(モード & UV_RUN_NOWAIT));
/* setImmediate() など */
uv_check_invoke(ループ); r = uv__loop_alive(ループ); If (モード & (UV_RUN_ONCE | UV_RUN_NOWAIT))
休憩
}



uv_update_time 関数のソース コードは次のとおりです: (
https://github.com/joyent/libuv/blob/v0.10/src/win/timer.c
))

コードをコピーします

コードは次のとおりです:

void uv_update_time(uv_loop_t* ループ) { /* 現在のシステム時刻を取得します */ DWORD ティック = GetTickCount(); /* LARGE_INTEGER.QuadPart が同じ型であると仮定します */ /* ループ->時間、これをアサートする方法はありますか? */ LARGE_INTEGER* 時間 = (LARGE_INTEGER*) &loop->time

/* タイマーがラップした場合は、その上位 dword に 1 を加算します */
/* uv_poll はタイマーが */
を超えてオーバーフローしないようにする必要があります /* 後続の 2 つの uv_update_time 呼び出しの間に 1 回 */
if (ティック < time->LowPart) {
時間->HighPart = 1; }
時間->LowPart = ティック
}

この関数の内部実装では、Windows GetTickCount() 関数を使用して現在時刻を設定します。簡単に言うと、setTimeout 関数を呼び出した後、一連の格闘の後、内部タイマー ->due が現在のループ タイムアウトに設定されます。イベント ループでは、まず uv_update_time を通じて現在のループ時間を更新し、次に uv_process_timers でタイマーが期限切れかどうかを確認します。期限切れになっている場合は、JavaScript の世界に入ります。記事全体を読んだ後、イベント ループにはおそらく次のプロセスがあることがわかります:

世界時間を更新します

タイマーを確認し、期限切れになったタイマーがある場合は、コールバックを実行します
reqs キューを確認し、保留中のリクエストを実行します
IO イベントを収集するためのポーリング関数を入力します。IO イベントが到着すると、次のイベント ループで実行するために、対応する処理関数を reqs キューに追加します。ポーリング関数内では、IO イベントを収集するためにシステム メソッドが呼び出されます。このメソッドは、IO イベントが到着するか、設定されたタイムアウトに達するまでプロセスをブロックします。このメソッドが呼び出されると、タイムアウトは最新のタイマー有効期限に設定されます。これは、IO イベントの収集がブロックされ、最大ブロック時間が次のタイマーの終了時間になることを意味します。
Windows でのポーリング関数の 1 つのソース コード:

コードをコピーします コードは次のとおりです:

static void uv_poll(uv_loop_t* ループ, int ブロック) {
DWORD バイト、タイムアウト
ULONG_PTR キー
OVERLAPPED* 重複しました。
uv_req_t* 要求
if (ブロック) {
/* 最新のタイマーの有効期限を取得します */
タイムアウト = uv_get_poll_timeout(ループ); } else {
タイムアウト = 0; }
GetQueuedCompletionStatus(loop->iocp,
&バイト、
                                                      &overlapped、
/* 最長でも次のタイマーが期限切れになるまでブロックします */
タイムアウト);
if (重複) {
/* パッケージがデキューされました */
req = uv_overlapped_to_req(オーバーラップ); /* IO イベントをキューに挿入します */
uv_insert_pending_req(ループ, 要求); } else if (GetLastError() != WAIT_TIMEOUT) {
/* 重大なエラー */
uv_fatal_error(GetLastError(), "GetQueuedCompletionStatus"); }
}

上記の手順に従って、タイムアウト = 1ms のタイマーを設定すると仮定すると、ポーリング機能は最大 1ms までブロックされ、その後再開されます (期間中に IO イベントがない場合)。イベント ループに入り続けると、uv_update_time が時刻を更新し、次に uv_process_timers がタイマーの期限が切れたことを検出してコールバックを実行します。したがって、予備的な分析は、uv_update_time に問題がある (現在時刻が正しく更新されていない) か、ポーリング関数が 1 ミリ秒待機してから回復し、この 1 ミリ秒の待機に問題があるかのどちらかであるということです。

MSDN を検索すると、驚くべきことに GetTickCount 関数の説明が見つかりました。

GetTickCount 関数の分解能はシステム タイマーの分解能に制限されており、通常は 10 ミリ秒から 16 ミリ秒の範囲になります。

GetTickCount の精度は非常に荒いです。ポーリング関数が 1 ミリ秒間正しくブロックしたが、次回 uv_update_time が実行されたときに、現在のループ時間が正しく更新されないとします。したがって、タイマーが期限切れになったと判断されなかったため、ポーリングはさらに 1 ミリ秒待って、次のイベント ループに入りました。 GetTickCount が最終的に正しく更新され (いわゆる 15.625 ミリ秒ごとに更新)、ループの現在時間が更新されるまで、タイマーが uv_process_timers で期限切れになったと判断されました。

WebKit に助けを求める
このNode.jsのソースコードは非常にどうしようもないもので、精度の低い時刻関数をそのまま使っています。しかし、私たちは Node-WebKit を使用しているので、Node.js の setTimeout に加えて Chromium の setTimeout もあるのだとすぐに思いました。テスト コードを作成し、ブラウザまたは Node-WebKit で実行します: http://marks.lrednight.com/test.html#1 (# に続く数字は、測定する必要がある間隔を示します) 、結果は以下のようになります:

HTML5 仕様によれば、理論上の結果は最初の 5 回は 1 ミリ秒、それ以降の結果は 4 ミリ秒である必要があります。テスト ケースに表示される結果は 3 回目から始まります。つまり、理論的にはテーブル上のデータは最初の 3 回で 1 ミリ秒、その後の結果はすべて 4 ミリ秒になるはずです。結果にはある程度の誤差があり、規制によれば、得られる理論上の最小結果は 4ms です。満足はしていませんが、node.js の結果よりも明らかに満足のいくものです。強力な好奇心トレンド Chromium のソース コードを見て、それがどのように実装されているかを見てみましょう。 (https://chromium.googlesource.com/chromium/src.git//38.0.2125.101/base/time/time_win.cc)

まず、ループの現在時刻を決定するために、Chromium は timeGetTime() 関数を使用します。 MSDN を参照すると、この関数の精度がシステムの現在のタイマー間隔に影響されることがわかります。私たちのテストマシンでは、理論上は上記の 1.001ms です。ただし、Windows システムのデフォルトでは、アプリケーションがグローバル タイマー間隔を変更しない限り、タイマー間隔は最大値 (テスト マシンでは 15.625 ミリ秒) になります。

IT業界のニュースを追っている人なら、このようなニュースを目にしたことがあるはずです。 Chromium ではタイマー間隔が非常に短く設定されているようです。もうシステムタイマーの間隔を気にする必要はないようですね?すぐに喜んではいけません。この修正は私たちに打撃を与えます。実際、この問題は Chrome 38 で修正されています。以前の Node-WebKit の修復を使用する必要がありますか?これは明らかに洗練されておらず、よりパフォーマンスの高いバージョンの Chromium を使用できなくなります。

Chromium ソース コードをさらに詳しく見てみると、タイマーがあり、タイマーのタイムアウトが 32 ミリ秒未満の場合、Chromium はシステムのグローバル タイマー間隔を変更して、15.625 ミリ秒未満の精度のタイマーを実現することがわかります。 (ソース コードを表示) タイマーを開始すると、HighResolutionTimerManager と呼ばれるものが有効になり、このクラスは現在のデバイスの電源タイプに基づいて EnableHighResolutionTimer 関数を呼び出します。具体的には、現在のデバイスがバッテリーで動作している場合は EnableHighResolutionTimer(false) が呼び出され、電源を使用している場合は true が渡されます。 EnableHighResolutionTimer 関数の実装は次のとおりです:

コードをコピー コードは次のとおりです:

void Time::EnableHighResolutionTimer(bool Enable) {
  Base::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 を呼び出します。   // したがって、期間効果を元に戻します。 
  if (有効にする) {
    timeEndPeriod(kMinTimerIntervalLowResMs); 
    timeBeginPeriod(kMinTimerIntervalHighResMs); 
  } else {
    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 Chromium の setTimeout を使用すると、 setTimeout(fn, 1) の通知差は 4ms 程度で制御できますが、 setTimeout(fn, 48) の通知差は 1ms 程度で制御できます。の蓝図、它让我们的代码看起来像是如：

复制代 代码如下:

/* 最大間隔偏差を取得します */

var 偏差 = getMaxIntervalDeviation(bucketSize); // バケットサイズ = 48、偏差 = 2; 
function gameLoop() {
  var now = Date.now(); 
  if (previousBucketbucketSize <= now) {
    前のバケット = 今; 
    doLogic(); 
  }
  if (previousBucketbucketSize - Date.now() > 偏差) {
    // 46ミリ秒待ちます。実際の遅延は 48ms 未満です。 
    setTimeout(gameLoop, BucketSize - 偏差); 
  } else {
    // 待機中です。 process.nextTick では IO イベントをブロックしないため、setImmediate の代わりに setImmediate を使用してください。 
    setImmediate(gameLoop); 
  }
}

上記のコードでは、上記の理論によれば、最大エラーが 46 ミリ秒の遅延で発生したとしても、エラーが直接 Bucket_size に等しくなるのではなく、bucket_size (bucket_size – 偏差) 未満になるまで待つことができます。実際の間隔は 48 ミリ秒未満です。残りの時間は、ビジー待機メソッドを使用して、ゲームループが十分に正確な間隔で実行されるようにします。

Chromium を使用して問題をある程度解決しましたが、明らかに十分にエレガントではありません。

私たちの最初のリクエストを覚えていますか?サーバー側のコードは、Node-Webkit クライアントから独立して実行でき、Node.js 環境を備えたコンピューター上で直接実行できる必要があります。上記のコードを直接実行すると、偏差の値は少なくとも 16 ミリ秒になります。これは、48 ミリ秒ごとに 16 ミリ秒待機する必要があることを意味します。 CPU使用率は上昇し続けます。

予期せぬサプライズ

Node.js には非常に大きなバグがあるのに、誰も気づかなかったのですか?その答えは私たちを本当に驚かせました。このバグは v.0.11.3 で修正されました。 libuv コードの master ブランチを直接表示して、変更された結果を確認することもできます。具体的な方法は、ポーリング関数が完了を待った後、ループの現在時刻にタイムアウトを追加することです。このようにして、GetTickCount が応答しない場合でも、ポーリングを待機した後、この待機時間を追加します。したがって、タイマーはスムーズに期限切れになります。

つまり、長い時間をかけて取り組んできた問題は、v.0.11.3 で解決されました。しかし、私たちの努力は無駄ではありません。 GetTickCount 関数の影響を除いても、ポーリング関数自体もシステム タイマーの影響を受けるためです。解決策の 1 つは、システム タイマーの間隔を変更する Node.js プラグインを作成することです。

ただし、今回のゲームでは、初期設定ではサーバーが存在しません。クライアントがルームを作成すると、それがサーバーになります。サーバー コードは Node-WebKit 環境で実行できるため、Windows システムでのタイマーの問題は最優先事項ではありません。上記の解決策によれば、結果は十分に満足できます。

エンディング

タイマーの問題を解決した後、フレームワークの実装には基本的に障害はありません。 WebSocket サポート (純粋な HTML5 環境) を提供し、さらに通信プロトコルをカスタマイズして、よりパフォーマンスの高い Socket サポート (Node-WebKit 環境) を実装します。もちろん、Spaceroom の機能は当初比較的初歩的なものでしたが、要求が高まり時間の経過とともに徐々にフレームワークを改善していきました。

たとえば、ゲームで一貫した乱数を生成する必要があることがわかったとき、そのような機能を Spaceroom に追加しました。 Spaceroom は、ゲームの開始時に乱数シードを配布します。クライアントの Spaceroom は、md5 のランダム性を利用して乱数シードを利用して乱数を生成する方法を提供します。

とても満足しているようです。このようなフレームワークを作成する過程で、私も多くのことを学びました。 Spaceroomに興味のある方は、ぜひご参加ください。スペースルームはもっといろんなところで力を発揮できると思います。