node/webosocketによるオンラインゲームの実装を考える / オンメモリ、KVS、RDBMS、圧縮プロトコル、そのゲームデザイン + 就活の話

node

派手で見栄えがする大規模なプロダクトを作ろう！っていうことで、一人でフルスタックなネトゲを作っている。大きなプログラムを書いても破綻しないようにテスト書きまくってテストファーストを心がけたり、Travis-CIによる継続的インテグレーションで頑張ったり。

というわけで作っているのはMMORPGなんだけど、ここで実装するのはまあ平均的なMMORPGを想像してもらいたい。自分がやろうとしているのは、モダンなOSSとさくらの安いVPSで、独学の学生一人でもフルスタックなネトゲみたいなのが組める、ということの実証。

なんでそんなことをしているかって言うと、一応就活中で、見栄えがするアプリ提出できるとおいしいなーっていう下心。


*追記* ここでは https://github.com/mizchi/wanderer のことを言ってるんだけど大規模リファクタリング中なのでここで言ってることは半分ぐらいしか実装してない

前置き

自分が得意なのでnodeで実装しているけど、 たぶんC++/TCPで組んでも考えることは同じだと思われる。
Web+DB的なことは、はてなのホッテントリウォッチャーとしてひと通り目を通していて、オンラインゲームを支える技術、大規模ウェブサービスを支える技術をナナメ読みした程度で、高負荷サービスを自分で運用したことはないんだけど、これに関しては手元でチューニングしつつ色々考えたことをまとめる。

WebSocketで如何に効率よくデータを配るか

基本的な考え方は、サーバー上にはステートマシンとしてすべての状態を持つゲームロジックがあり、メインループが回ってデータが更新され続けている。プレイヤーはそこにキー情報やクリック情報を送って自分のキャラクターを操作する。

Apacheなどと違ってnodeによるセッションはコネクションを維持し続けるので、Cometのような擬似ポーリングをする必要がない。通信のオーバーヘッドが少ないので、小さいデータを断続的に送るのに向いている。

小さなデータを断続的に送るのと、ある程度まとまったデータをドンと送るのはシチュエーション次第。
マップにログインしたときはマップをレンダリングするための配列情報が必要だし、基本的にその後変化することはない。というか変化する部分と切り離す必要がある。そこでインタラクションを取りたい場合は、その都度再構成するのが良いと思う。

1ネームスペース、1マップ

nodeでwebsocketを使う際は socket.ioを使うと思う。socket.ioではネームスペースを区切ることが出来る。ネームスペースを作成すると、そのネームスペースに属している接続に、ブロードキャストすることができる。これによって必要な範囲に必要な分量だけデータを送りつけることが出来る。

websocketで配るようなデータは基本的にキャッシュがきかない(動的に変化する)ので、フロントサーバーを置く必要性は感じない。nginxが対応するまではnode-http-proxyなどを使って直に晒すのがいい。サーバーに担当してもらうのは画像やjs(たぶん分量が多い)の配信だ。

nodeで書くと嬉しいのは、圧縮、復元を同じロジックで書いて使いまわせること。
たとえば、僕はまず通信用に圧縮変換テーブルを作った。それらを プレーヤーネーム、プレーヤID、x座標、y座標、残りHP率、アニメーションフラグを１つの配列に押し込んで、それらをさらにnode-msgpackで圧縮しクライアントに送りつける。クライアントでも同じロジックを使って再現し、同じ方式で圧縮してサーバーに送る。

あとは演出上、サーバーと同じロジックをクライアントもある程度持つ必要がある。
AがBに投射攻撃をしたいとする。このとき、AからBへ攻撃が発動可能ならばアイコンを緑に、発動不可ならばアイコンを赤にしたい、とする。
サーバーではAが所属するマスからBのマスへのブレゼンハム線分を引き、障害がなければ発動する、というロジックで動いている。このコードをクライアントでも使いまわせると、サーバーへ「それが可能であるか、可能であるならばどういうデータ構造で表現するか」という問い合わせを減らすことが出来る。もちろん、基本的にマスターデータはサーバー上にあり、クライアントのデータとはズレがあるのだが、通信のラグが有ることをプレーヤーも認識せざるを得ない以上、納得できる話ではあると思う。

clusterによる分散

nodeにはclusterというモジュールで別のnodeのシングルコールバックのメインループとTCPで通信する機能を持っている。これも一定の単位で処理を分散するのに使えるだろう。
とはいえ、スレッド分割でスケールするのがコア数までなので、諦めて無難にサーバー側でスケールするのがよい。

nodeのボトルネック V8拡張 どこでトレードオフを取るか

敵モンスターに毎フレームA*による経路探索させると、計算が重すぎてラグった。1秒に1回、探索打ち切りも早めに制限することにした。実際には、ある程度近ければ一秒に一回プレイヤーの方向を向き直り向かってくる、という挙動になったので、ゲーム的にはちょうどよかったのだが…。

V8とC++ではさすがに10倍ほどの速度差が出る。これを考えるとC++でA*アルゴリズムを書きなおせば単純に毎秒10回は経路探索しても構わなくなる。nodeはnodeという名前通り、APIを介する役割だけを追って、重いアルゴリズムをnodeのV8拡張で書きなおせば、かなりボトルネックは解消される。
非同期メソッドにするとより良いだろうが、そうするとゲームデザイン側で工夫しなければいけない。たとえば、ニューラルネットで書かれた状況判断エンジンに次の行動を選ばせて、その結果が出るまで前の結果を繰り返し続ける、とか。結果が遅延することが許されないといけない。

nodeを使ってる以上、ある程度のところで妥協するのが妥当で、本当にここだけやばい！みたいな箇所でピンポイントでC++に置き換えるのがいいだろう。とはいっても、3Dの物理エンジンを使いたいのだったら全部nodeで書くのは無謀で、バックにbulletなどを置いてV8経由でAPIを提供する方が良いだろう。

リレーショナルか、KVSか

モデルはJSONで保存されている。開発中はnstore(ローカルのKVS)を使っているが、Redis、Kyoto-TyrantなどのKVSを使うことを考える。このときリレーショナルなDBMを使う必要はあまりない。基本的にプレイヤーネームとセーブデータは一対一に紐づいているおり、内部パラーメータでクエリを投げる必要は考えなくていいとすると、探索コストが低く実装も容易なKVSで組んでしまうのが手っ取り早い。リレーショナルである必要がないものをリレーショナルで組むと、実装が無駄にややこしくなる(バグを含みやすい)。

リレーショナルなDBMが必要なシチュエーションは、たとえばオークションシステムを導入したいとする。持つべき情報は 出品者ID、アイテムID(アイテムIDを主キーとした別テーブルあり)、希望価格、残り時間等だろうか。こういうものは価格順や種別等でソートできる必要があるだろうからリレーショナルが適していると思われる。

どこからDBで、どこからメモリか

キャメルケースはクラスってことで、だいたいの概念図

Character - 複雑な状態を持つ
JSON <-> CharacterModel -> Player(extends Character)

Stage 
  - map:Map
  - players: [Player (extends Character)]
  - monsters: [Monster (extends Character)]
  - connections:[Stage]

CharacterModelはJSONのデータを内部にコピーし、書きだす機能を持つ。CharacteModelはJSONのデータに基づいてCharacterクラスのインスタンスを生成してメモリに乗せる。CharacterModelの持つ情報はJSONで表現可能なデータフォーマットに基づくが、Characterはその限りではない。Playerと紐付くCharacterはシングルトン化する。monstersはCharacterModelを介さず、直接パラメータを打ち込んでCharacterクラスを生成する。

Stageは上記で述べたように１つのネームスペースと対応していて、「D砂漠・東」などのゲーム的な名前を持っている。connectionsは隣接するStageとその接続点の情報を持つ。Mapは設置オブジェクト情報、当たり判定、などのゲーム的なデータを持ち、Characterから参照されている。

Characterのゲームロジックの中でのアクションによってCharacterModelが更新され、CharacterModelが更新されるとCharacterのオブジェクトも再構築される。
CharacterModelの更新はDBアクセスなため、できるだけ控えたい。たとえば敵を倒して経験値を入手する、というイベントは高頻度に発生すると考えられるが、一回の経験値の入手自体は重要度は高くない。
更新しないといけないのは、たとえばレベルアップのロジック。CharacterクラスはCharacterModelから引き継いで経験値情報を持ち、規定値に達してレベルアップした際にモデルを更新、DBへ反映し、Characterクラス自身も新しいステータス情報を元に更新する。

他には

  • 15分に一度(不慮の事態でロールバックした時、プレイヤーのモチベーションが落ちないような頻度)
  • レアアイテムの入手
  • シナリオフラグの変更(ボス撃破)

こうしておけばほとんどDBに負荷をかけずに済む。その分メモリの負荷がきついが、その場合はスケールするか、頑張って圧縮するしかない。マップを適切に区切ると負荷が調節できる。が、ROのプロンテラやウルティマオンラインのブリ三叉路みたいに超過密地帯はサーバー負荷的にはきついだろうが、そういう場所があることでプレーヤーのお祭り感が演出できるとも言えるだろうし、ベンチマークにもなる。


以上、作りながら考えていたこと。書き殴りになったけど、参考になれば。

最後に

大学生で就活中です。あんまり大手企業に惹かれないので、楽しそうなベンチャーを見て回っています。そういえば昨日カヤックさんのワンクリック就活出しました。ワンクリックだったので。(他に面接待ちも一件あるけど)
とりあえず遊びに来いやっていうお誘いがあれば mizcki＠gmail.comにメールください。JavaやLLならどの言語でもそこそこ触れます。得意なのはnodeとpythonです。C++等低レベルは苦手です。絵を書いたりフォトショ触ったりは出来ませんが教養程度にはHTML/CSS組めます。鯖管ほどじゃないですがLinux(Debian系)いじれます。

企画は経験値低いですが興味はあります。とくにゲームの企画興味ありますが、普通のソーシャルゲーは苦手です。トラビアンは好きでした。どっちかっていうとコンシューマゲームの方が好きなんですが、そうなるとスキルがミスマッチな気がするので誰かアドバイスください。ネットウォッチ力は高いです。


勉強会出る方ではなくそれ系のコネが少ないのでブログで書きました。疲れた。