Case Study: Inside World Wide Maze

HTML5 Rocks

World Wide Maze はスマートフォンを使ってボールを転がし、3D 迷路化された Web サイト上でゴールを目指すゲームです。

スマートフォンから DeviceOrientation イベントで取得された傾き情報を WebSocket を通じて PC に送信し、WebGLWeb Workers で構築された 3D 空間をかけめぐる、といったように HTML5 の機能をふんだんに使ったゲームになっています。

この記事では、それらの機能を具体的にどのように使っているか・制作フロー・最適化ポイントなどについて解説していきす。

DeviceOrientation

スマートフォンの傾き情報を取得するには DeviceOrientation イベントを使います。deviceorientation イベントを addEventListener すると、一定時間ごとに引数に DeviceOrientationEvent オブジェクトを持ったコールバックが呼ばれます。このコールバックは一定時間ごとに呼ばれますが、その間隔はデバイスによって異なってきます。iOS + Chrome, iOS + Safari だと 1/20 秒ごとぐらい、Android 4 + Chrome だと 1/10 秒ぐらいです。

window.addEventListener(‘deviceorientation’, function (e) {
  // do something here..
});

DeviceOrientationEvent オブジェクトにはデバイスの XYZ 軸それぞれの傾きが度単位(ラジアンではない)で入っています。(XYZ 軸がそれぞれ何を表すかは上記 w3c のページを参照してください。)ただし、これもデバイスとブラウザの組み合わせによって返ってくる値が異なります。実際に返ってくる値の範囲を調査し、まとめた表が以下になります。

一番上のブルーのところの値が W3C の仕様で定義されてる値、グリーンが仕様どおりになっている値です。赤が仕様と違う値。驚くことに仕様通りの値を返してくるのは Android の Firefox だけでした。いくら Firefox が正しいとはいえ、実装でいうと多数に合わす方が合理的なので、World Wide Maze では iOS で返ってくる値を基準に、Android の方をズラして対応する仕組みにしています。

if android and event.gamma > 180 then event.gamma -= 360

実はそれでも Nexus 10 は対応できません。Nexus 10 の返す値は、範囲的には他の Android と同じですが、beta と gamma が逆になるというバグがあり、それも別途対応しています。(横位置をデフォルト位置としてる?)

このように、物理デバイスが絡む API では、仕様が決まっていたとしても、そのとおりの値が返ってくる保証はなく、想定されるデバイスすべてで実際に動作させて値を確認するという作業が必須になります。そしてそれは想定外の値が入力されうるということなので、その場合の対処もあわせて仕組みを作らなければなりません。World Wide Maze では初回プレイ時のチュートリアルの STEP 1 としてデバイスのキャリブレーションをさせていますが、傾き値が想定外の場合、絶対にゼロ位置に合わせられないので、内部的に制限時間を設け、制限時間内に合わせられない場合、キーボード操作に切り替えるように誘導しています。

WebSocket

WWM では、スマートフォンと PC は WebSocket で接続されています。正確には、スマートフォン→サーバー→PC のように、間に中継用のサーバーが存在します。WebSocket には直接ブラウザ同士を接続する機能はないのでこのようになっています。(WebRTC の Data Channels をつかうと P2P 接続できるので中継サーバーは不要になりますが、実装時点では Chrome Canary と Firefox Nightly でしか利用できませんでした。)

実装には、接続タイムアウトや切断時の再接続などの機能をもった Socket.IO (v0.9.11) を採用しました。サーバーサイドは複数の WebSocket 実装をテストした結果、最もパフォーマンスのよかった NodeJS + Socket.IO の組み合わせを採用しました。

番号によるペアリング

  1. PC がサーバーに接続。
  2. ランダムに生成した番号を PC に渡す。
    サーバーは番号と PC のペアを覚えておく。
  3. モバイルから番号を指定してサーバーに接続。
  4. 指定した番号に対応する PC が存在すれば、それとペアを作る。
    なければエラー。
  5. モバイルからデータが流れてきたら、ペアとなる PC に送る。逆も。

最初の接続はモバイルからも可能ですが、単純に動作が逆になるだけです。

Tab Sync

番号によるペアリングをさらに簡単にする方法として、Chrome 特有の機能である Tab Sync を使用しました。Tab Sync 機能を使うと、PC で開いていたものと同じ URL をモバイル側でも簡単に開くことができます(逆ももちろん可能)。PC 側でサーバーから発行された接続番号を history.replaceState を使って URL にくっつけます。

history.replaceState(null, null, ‘/maze/’ + connectionNumber)

Tab Sync が有効であればこの URL が数秒後に同期され、モバイル側で同じ URL が開けるようになります。モバイル側では開かれた URL をチェックして、番号がついていればすぐに接続を開始します。この方法では番号を手動で入力することもカメラで QR コードを読み取る必要もありません。

レイテンシー

日本からアクセスした場合、中継用のサーバーがアメリカに存在するため、実際にスマートフォンから送られた傾きデータが PC に到着するまでに、おおよそ 200ms 程度の遅延が発生します。開発時にローカル環境で動かしていた状況と比較すると明らかに反応が鈍いのですが、ローパスフィルタのようなもの(具体的には指数移動平均)を挟むことであまり気にならないレベルにすることができました。(実際、傾きセンサーが返す値はノイズもかなり含まれていて、そのまま傾きの値を画面に反映させるとすごくガタガタするので、見栄え的にもローパスフィルタは必要でした。)ジャンプに関してはそういう訳にはいかないので、明らかに遅延してるのが分かりますが、これについてはどうしようもありませんでした。

当初からレイテンシーが発生することは分かっていたので、中継用サーバーを世界各地に配置して、各クライアントから一番近い=レイテンシーが少ないサーバーに接続しにいく方法を考えていましたが、今回使用することになった GCE (Google Compute Engine) が当時 US しか存在しなかったため、この仕様になりました。

Nagle アルゴリズム問題

普通の OS では、TCP レベルでバッファリングすることで、効率良く通信するための Nagle アルゴリズム という仕組みがが実装されているのですが、このアルゴリズムが有効なままだとリアルタイムにデータを送信することができないという現象がありました。(正確にはこれに加えて TCP 遅延 ACK が組み合わさった場合。遅延 ACK でなくても、サーバーが海外にあったりして ACK がある一定レベル遅れる場合には同様の問題が発生します。)

Chrome for Android の WebSocket 実装では Nagle を無効にするための TCP_NODELAY オプションが付いているので、Nagle 遅延問題は発生しませんでしたが、Chrome for iOS につかわれている WebKit の WebSocket 実装には、このオプションが指定されておらず、遅延問題が発生します。同じ WebKit を使っている Safari も同様。この問題は Google を通して Apple に報告され、開発バージョンの WebKit ではすでに修正されている とのこと。

実際、この問題が発生すると、100ms ごとに送信している傾きデータが、500ms ごとにまとめて PC 側に届きます。これではゲームとして成立しないので、サーバーサイドから短い間隔(50msぐらい)でデータを送り続けることで遅延を回避しています。これはおそらく ACK が短い間隔で届くために、Nagle アルゴリズム的に送信可能な状態になるからだと考えています。

これは実際にデータを受信した間隔をグラフにしたものです。前のパケットとの時間間隔を表していて、緑が送信間隔、で赤が受信間隔。下が 54ms、上が 158ms で、中心がほぼ 100ms です。iPhone で日本にある中継サーバーをつかったときのものになります。送受信ともにほぼ 100ms なので、動きはスムースです。

そしてこれが US にあるサーバーでやってみたときのグラフです。緑の送信間隔はちゃんと 100msですが、受信間隔は下が 0ms で上が 500ms という具合に、いくつかのデータがまとめられて PC 側に届いていることが分かると思います。

そしてこれがサーバーからダミーのデータを送り続けることで遅延回避したときのグラフです。日本のサーバーほどではないですが、受信間隔がほぼ 100ms 付近に安定したのが分かるでしょうか?

バグ?

Android 4 (ICS) のデフォルトブラウザは WebSocket の API が存在するにもかかわらず、接続することができないという問題があります。その場合、Socket.IO の connect_failed イベントが発生します。内部的にはタイムアウトしているのですが、サーバーサイドでも接続が確認できない状態です。(生 WebSocket では試していないので、もしかすると Socket.IO の問題かもしれない。)

中継サーバーのスケーリング

中継サーバーがやっていることはさほど難しいものではないので、同じ番号のソケットが同じサーバーに繋がるようにさえ気を使えば、サーバーを増やすこと自体はそれほど難しくありません。

Physics

ゲーム内のボールの動き(重力に応じて転がる、床にぶつかる、壁にぶつかる、アイテムを取得するなどなど)は、すべて 3 次元の物理シミュレーションを行なっています。実装には、様々なゲームなどでの採用実績がある BulletEmscripten を用いて JavaScript に移植した Ammo.js と、さらにそれを Web Worker として実行させる Physijs を使用しました。

Web Workers

Web Workers は、JavaScript ファイルを別スレッドとして並列に実行できる機能です。Web Worker として起動された JavaScript は呼び出し元のスレッドとは別のスレッドとして動作するので、重い処理をさせても画面が固まったりすることはありません。Physijs はこの Web Worker をうまくつかうことで、通常では負荷の高い 3D 物理演算をスムーズに動作させることができます。World Wide Maze では物理演算と WebGL の描画を完全に別のフレームレートで動かすことで、WebGL の描画負荷が高くフレームレートが落ちてしまう低スペックマシンでも、物理演算自体は極力 60fps を維持し、ゲームの操作感が損なわれないよう配慮しています。

画像は Lenovo G570 での動作時のフレームレートです。上が WebGL(画面描画)で、下が物理演算のフレームレートをそれぞれ表しています。GPU が Intel HD Graphics 3000 という CPU 内蔵のもののため、想定フレームレートの 60fps には達していませんが、物理演算フレームレートは想定通りのため、ゲームプレイは高スペックのものとさほど変わりありません。

Web Worker が動作するスレッドには console オブジェクトが存在しないため、デバッグログを取るためには postMessage でメインスレッドに送信しないといけません。console4Worker を使うと、Worker 内に通常の console オブジェクトと同等のものを用意してくれるので、デバッグが格段にやりやすくなります。

最近の Chrome では、Web Worker 起動時に Breakpoint 設定できたりするので、これも覚えておくと便利です。Developer Tools の Workers のパネルに表示されます。

パフォーマンス

ステージ全体のポリゴン数は多い時で 10 万を超えることもありますが、それらをすべて Physijs.ConcaveMesh (Bullet でいうと btBvhTriangleMeshShape) として生成しても、特別パフォーマンスに問題は出ませんでした。

当初、当たり判定が必要なオブジェクトが増えるに連れて、フレームレートが落ちるという問題がありましたが、Physijs 内の無駄な処理を省くことによって、パフォーマンスが改善しました。改善したものは本家から fork しています。

Ghost object

当たり判定はあるけど当たっても衝撃を受けたりせず、他に影響を与えないオブジェクトを、Bullet では Ghost object と呼びます。Physijs では正式にサポートされていませんが、Physijs.Mesh 生成後にフラグをいじることで、Physijs でも実現可能です。World Wide Maze ではアイテムとゴールの当たり判定に、この Ghost object を使用しています。

hit = new Physijs.SphereMesh(geometry, material, 0)
hit._physijs.collision_flags = 1 | 4
scene.add(hit)

collision_flags の 1 は CF_STATIC_OBJECT、4 は CF_NO_CONTACT_RESPONSE。このあたりの情報は Bullet の forum とか Stack Overflow を探すと出てきます。あと、Bullet のドキュメント。Physijs は Ammo.js の wrapper で、Ammo.js は Bullet そのものなので、Bullet でできていることは大抵 Physijs でもできます。

Firefox 18 問題

Firefox が 17 から 18 にバージョンアップした際、Web Worker 間でデータをやり取りする方法に変更があったため、Physijs が動かなくなる問題が起こりました。GitHub に Issue 登録したら数日で解決。オープンソースってすごーい、と思うと同時に、多数のオープンソースフレームワークを用いて World Wide Maze が出来上がってることを再認識し、なんらかのフィードバックをすべきという思いでこの文章を書いています。

asm.js

World Wide Maze とは直接関係ありませんが、先日 Mozilla が発表した asm.js に Ammo.js が早速対応していました。(asm.js は Emscripten で生成された JS をさらに高速に動かすためのようなもので、Emscripten の作者 = Ammo.js の作者なので当然といえば当然。)Chrome も asm.js に対応すれば、物理演算部分の負荷がかなり減ると思われます。実際 Firefox Nightly で試した際は、実感できるレベルでかなり高速でした。高速化が必要な部分は C/C++ で書いて Emscripten で JS にするのがベスト??

WebGL

WebGL の実装には一番活発に開発が進んでいる three.js (r53) を利用しました。開発後期には revision が 57 まで進んでいましたが、大幅な API 変更が入っていることがわかっていたので、最初に導入した revision のままリリースしました。

Glow effect

ボールのコア部分やアイテムなどがぼわーっと光るグロー表現は、いわゆる 川瀬式 MGF の簡易版によって実装されています。ただし通常の川瀬式が輝度の高い部分を bloom させているのに対し、World Wide Maze では光らせる部分を別のレンダーターゲットに描画する方式にしています。これは Web サイトのスクリーンショットをステージテクスチャに使用しなければならず、高輝度部分を単純に抽出してしまうと背景が白いサイトなどは全域にグローがかかってしまうため。HDR で全てを処理することも考えられましたが、実装がかなり複雑になりそうだったので今回は見送りました。

左上が 1 pass 目、グロー部分別途描画後、ブラーかけたもの。右下 2 pass 目、1 pass 目を縦横半分に縮小してブラー適用。右上 3 pass 目、2pass 目をさらに縦横半分にしてブラー適用。左下がそれらを重ねあわせた最終映像。ブラーにつかってるのが three.js 付属の VerticalBlurShader, HorizontalBlurShader なのでここはもう少し最適化できそうです。

Reflective ball

ボールの映り込み処理は three.js のサンプルをベースにしました。ボールの位置から全方位レンダリングしたものを環境マップとして使用しています。ボールの位置が変わるたびに環境マップをアップデートする必要がありますが、60fps でアップデートするのは負荷が高いため、3 フレームおきにアップデートするようにしています。毎フレーム更新するのと比べると、多少スムースさには欠けますが、言われなければわからないレベルです。

Shader, shader, shader....

WebGL では全ての描画にシェーダー (vertex shader, fragment shader) が必要となります。three.js に用意されているものだけでも幅広い表現は可能ですが、より凝った表現をしたり最適化が必要になったりすると、自らシェーダーを書くことは避けられません。World Wide Maze では CPU が物理演算でビジーになりがちなので、CPU (JavaScript) で書くほうが簡単な処理でも、極力シェーダー (GLSL) で書くことで、GPU を使うようにしました。海の波の表現はもちろん、ボールが登場するときのメッシュや、ゴールの花火もほぼシェーダーで表現されています。

ボール登場時のメッシュの表現テスト。一番左が実際に使われているもので 320 ポリゴン。真ん中が 5000 ポリゴンぐらい。右が 30 万ポリゴンぐらい。これぐらい大量のポリゴンになってもシェーダーで処理すれば 30fps 維持できる。

ステージ上にちらばっている小さなアイテムは、全てがひとつのメッシュになっていて、個々の動きはそれぞれのポリゴンの頂点をシェーダーで移動させることで表現されています。これは大量に置いてみてパフォーマンスが落ちないかテストしているところ。だいたい 5000 個のオブジェクトが配置されています。ポリゴン数的には 2 万程度。全く問題ありません。

poly2tri

ステージ形状はサーバーから受け取ったアウトライン情報をもとに JavaScript 側でポリゴン化していますが、この処理の中で重要な三角形化 (triangulation) の three.js での実装があまりよくありません。高い確率で triagulation に失敗します。そこで別の triangulation ライブラリである poly2tri を自力で組み込もうと思ったのですが、どうやら three.js は過去に poly2tri を組み込もうとしたらしく、一部コメントアウトするだけで組み込むことができました。結果、エラーは大幅に減り、プレイできるステージが増えました。それでも低い確率でエラーは発生するのですが、なぜか poly2tri のエラーは alert を出す仕組みになっているため、その部分は例外を投げるように変更しました。

ブルーの外形を三角形分割して赤いポリゴンを生成しています。

Anisotropic filtering

通常の mipmap では縦横等倍に縮小してしまうので、ポリゴンを極端な角度から見た場合、World Wide Maze でいうステージの奥の方のテクスチャは、解像度の低いテクスチャを横に伸ばしたような見え方になってしまいます。Wikipedia リンクの右上の絵がわかりやすいと思います。実際には横方向の解像度はもっと必要で、WebGL (OpenGL) では Anistoropic filtering という機能でその問題を解消しています。three.js では THREE.Texture.anistorpy に 1 より大きな値を設定すると anstropic filtering が有効になります。ただしこの機能は extension なので GPU によってはサポートされていない場合もあります。

Optimize

WebGL (OpenGL) の処理を軽くする一番重要な点は、WebGL best practices にもあるように、draw call をいかに少なくするかというところ。開発当初は、ステージの島・橋・ガードレールすべてが別のオブジェクトだったため、draw call が 2000 を超えることもあって、複雑なステージだと重くなりがちでした。しかし、同じ種類のオブジェクトを全て一つのメッシュにまとめるようにしたところ、draw call は 50 程度まで減り、負荷もかなり軽減されました。

そしてさらなる最適化のために使ったのが Chrome の tracing 機能です。Chrome の Developer tools に含まれる Profiler でもメソッド単位の処理時間などがある程度把握できますが、tracing を使うことでさらにその中のどの部分がどれぐらいの時間かかっているかを 1/1000 秒単位で見ることができます。tracing そのものの使い方は この記事 を読むのがよいでしょう。

これはボールの映り込み用の環境マップを作っている部分の trace 結果です。three.js 内部の関連しそうなところに console.time, console.timeEnd を仕込むとこのようなグラフができあがります。左から右に時間がながれていて、各レイヤーは call stack のようなものです。console.time を入れ子にするとさらに内部の時間が測れます。上が最適化前、下が最適化後。上では render0 ~ 5 のそれぞれで updateMatrix (ちょっと見切れてるけど) が呼ばれていますが、これはオブジェクトの位置や回転が変更されたときだけに必要な処理なので、全体で一回呼ばれるように変更しました。

当然ながら trace することそのものが負荷になるので、必要以上に console.time を仕込むと実際のパフォーマンスとの差がひどくなって、最適化ポイントがわかりづらくなります。

Performance adjuster

Web の特性上、さまざまなスペックのマシンでプレイされることが想定されます。2 月はじめに公開された Find Your Way To OZ では [IFLAutomaticPerformanceAdjust](https://code.google.com/p/oz-experiment/source/browse/project/develop/coffee/ifl/IFLAutomaticPerformanceAdjust.coffee) というクラスが、動作中の fps の変化にあわせてエフェクトなどを削減することで、スムースに再生することを助けていましたが、World Wide Maze ではこの IFLAutomaticPerformanceAdjust クラスを元に、以下の順でエフェクトを削減、ゲームプレイそのものが極力スムースに行われるように配慮しました。

  1. 45 fps を切ったら、環境マップの更新をやめる。
  2. それでも 40 fps を切ったら、レンダリング解像度を 70% にする。(面積比 50%)
  3. それでも 40 fps を切ったら、FXAA (アンチエイリアス) をやめる。
  4. それでも 30 fps を切ったら、グローをやめる。

Memory leak

three.js はオブジェクトをきれいに削除するのがちょっと面倒です。かといって放っておくと当然ながらメモリリークを起こしてしまうので、以下のようなメソッドを用意しました。@rendererTHREE.WebGLRenderer。(three.js 最新リビジョンでは deallocation の方法がちょっと変わってるので、たぶんこのままでは使えません。)

destructObjects: (object) =>
  switch true
    when object instanceof THREE.Object3D
      @destructObjects(child) for child in object.children
      object.parent?.remove(object)
      object.deallocate()
      object.geometry?.deallocate()
      @renderer.deallocateObject(object)
      object.destruct?(this)

    when object instanceof THREE.Material
      object.deallocate()
      @renderer.deallocateMaterial(object)

    when object instanceof THREE.Texture
      object.deallocate()
      @renderer.deallocateTexture(object)

    when object instanceof THREE.EffectComposer
      @destructObjects(object.copyPass.material)
      object.passes.forEach (pass) =>
        @destructObjects(pass.material) if pass.material
        @renderer.deallocateRenderTarget(pass.renderTarget) if pass.renderTarget
        @renderer.deallocateRenderTarget(pass.renderTarget1) if pass.renderTarget1
        @renderer.deallocateRenderTarget(pass.renderTarget2) if pass.renderTarget2

HTML

個人的に WebGL アプリでいちばんよいなーと思うのが HTML で画面レイアウトができることです。Flash や openFrameworks (OpenGL) だと、得点表示とかテキスト流し込みとか 2D 的な UI の構築が面倒です。Flash は IDE があるのでまだいいのですが、oF は慣れないとかなりつらい。(Cocos2D とかを使えば楽なのかな?) HTML であれば通常の Web ページを作るのと同様、CSS で全ての見た目を正確にコントロールできます。パーティクルが集まってロゴになる、みたいな演出は無理ですが CSS Transform の範囲であれば 3D 的な表現もできなくはありません。実際、“GOAL” や “TIME IS UP” の文字演出は CSS Transition で scale をアニメーションさせているだけです。(実装には Transit を使用しています。 )(背景のグラデーションはもちろん WebGLですが。)

実装としては、各ページ(タイトルとか RESULT とか RANKING とか)ごとに別の html ファイルに分けたものをテンプレートとして読み込み、適切なタイミングで、表示すべき値をセットした上で $(document.body).append() しています。ちょっとハマったのは append してからじゃないとマウスやキーボードイベントが設定できないこと。append 前に el.click (e) -> console.log(e) しても呼ばれません。

Internationalization (i18n)

英語版を作る際にも HTML であることはかなり有利に働きます。今回、国際化機能をつけるにあたって使ったライブラリは、通常の Web を i18n するための i18next というものですが、これをそのまま使うことができました。

ゲーム内にでてくるテキストの編集および翻訳作業は Google Spreadsheet 上で行いました。実際に i18next で必要になる JSON ファイルへは、Spreadsheet から TSV で exporrt されたファイルを独自のコンバーターで変換しました。リリース間際はアップデートが頻発したので、Spreadsheet から export する部分も自動化した方が楽だったなーという印象。

Chrome 内蔵の自動翻訳機能もページが HTML で構築されているので通常どおり機能します。ただし言語判定に失敗して使用していない言語(ベトナム語)などに判定されてしまうことがあるので現時点では無効にされています。(metatag で無効にできます。

RequireJS

JavaScript のモジュールシステムとして採用したのが RequireJS。10,000 行のソースコードは 60 ほどのクラス(= coffee ファイル)にわかれており、個別に js ファイルにコンパイルされる。RequireJS を使うとそれらを依存関係に基づいて適切な順序で読みこんでくれる。

define ->
  class Hoge
    hogeMethod: ->

として定義されたクラス (hoge.coffee) は、

define [‘hoge’], (Hoge) ->
  class Moge
    constructor: ->
      @hoge = new Hoge()
      @hoge.hogeMethod()

として使える。このとき hoge.js が必ず moge.js よりも前にロードされる必要がありますが、define の第 1 引数に hoge が指定されてるのでちゃんと hoge.js を先にロードしてくれます。(hoge.js のロードが終わった段階でコールバックされる。)この仕組みは AMD と呼ばれていて、サードパーティのライブラリでも AMD に対応しているものであれば、同様の呼び出し方で使えます。AMD に対応していないライブラリ(three.js など)でも、あらかじめ別に依存関係を指定しておけば、これも同様に扱えます。

感覚的に AS3 の import に近いのでそれほど違和感なく使えます。依存するファイルが増えた場合は、こういった対処方法 があるようです。

r.js

RequireJS には r.js というオプティマイザが付属しています。これはメインとなる js と依存関係のあるすべての js ファイルをひとつにまとめて、さらに UglifyJS (または Closure Compiler) で minify してくれるというもの。これによってブラウザが読み込まなければいけないファイル数・データサイズが削減されます。World Wide Maze の全 JavaScript ファイルサイズが 2MB ぐらい、r.js で optimize すると 1MB ぐらいまで減ります。gzip で配信できれば実質転送データ量は 250KB まで減らせます。(GAE が 1MB 以上のファイルは gzip 転送してくれない問題があって、実際には plain text 1MB のまま配信されています。)

Stage builder

ステージデータの生成は以下の手順。全て US にある GCE のサーバー上で行われています。

  1. WebSocket 経由でステージ化する URL を送る。
  2. PhantomJS でスクリーンショットを撮る。同時に div や img タグの位置も取得して JSON に出力。
  3. 2 で出力されたスクリーンショットと HTML 要素の位置情報をもとに、C++ (OpenCV, Boost) で書かれた独自プログラムによって、不要なエリアを削除、島を生成、橋で島を接続、ガードレール・アイテムの位置計算、ゴールの配置、などを行います。結果は JSON に出力され、これがブラウザに返されます。

PhantomJS

画面が不要なブラウザ。ウィンドウを開いたりすることなく、Web ページが開けるので、今回のようにサーバーサイドでスクリーンショットをとったり、自動テストにも使われています。ブラウザエンジンは Chrome や Safari に使用されているものと同じ WebKit なので、レイアウトや JavaScript の実行結果も通常のブラウザとほぼ同様。

PhantomJS は JavaScript または CoffeeScript でやりたい処理を書きます。スクリーンショットをとるのはサンプルにもあるようにすごく簡単。今回のサーバー環境は Linux (CentOS) だったので、日本語表示のために別途フォント (M+ FONTS) をインストールする必要がありました。それでも Windows や Mac とはフォントレンダリングの仕組みが違うので、同じフォントを入れても同じようには見えなかったりします。(実際にはほとんど気にはならない。)

img タグや div タグの位置を取得するのも、基本的には通常のページでやる方法と同じ。jQuery も普通に使うことができます。

stage_builder

当初はもうすこし DOM 的なことからステージ生成することを考えていたので(Firefox の 3D Inspector のような)、PhantomJS で DOM 解析のようなことをしていましたが、最終的には画像処理的に生成することになりました。そのために書いたのが stage_buidler という OpenCV と Boost を使った C++ プログラム。この中で行われているのは以下の処理。

  1. スクリーンショットと JSON を読み込む。
  2. 画像や文字などが島になるようにする。
  3. 島同士をつなぐ橋をつくる。
  4. 不要な橋を削除して迷路にする。
  5. 大アイテムを配置する。
  6. 小アイテムを配置する。
  7. ガードレールを配置する。
  8. 配置データを JSON で出力する。

順番に解説します。

スクリーンショットと JSON を読み込む

スクリーンショットをロードするのは普通に cv::imread。JSON はいくつかのライブラリをためしてみたけど picojson が一番使い勝手がよい気がします。

画像や文字などが島になるようにする

aid-dcc.com の NEWS 付近のスクリーンショット(クリックで実寸)。このなかで島になってほしいのは画像とテキスト周辺。これがうまく残るようにそれ以外を削除するには、白い背景色、つまり画像内で一番たくさん使われている色を削除すればいい。そうして処理したのが次の絵。

白が島候補地。

文字が細かく抜けすぎてるので、cv::dilate, cv::GaussianBlur, cv::threshold などで太らせます。画像の内部も抜けてしまってるので、PhantomJS から出力した img タグの情報をもとに白く塗りつぶします。で、できたのが次の絵。

テキストがある一定のかたまりになって、画像もそれぞれがちゃんと島になっている。

島同士をつなぐ橋をつくる

島ができたらそれぞれをつなぐ橋をかけます。各島から上下左右方向に隣の島を探します。一番近い島の、一番近い部分に橋をかけます。するとこんな感じ。

不要な橋を削除して迷路にする

このままだと自由に移動できすぎてしまうので、迷路になるように不要な橋を削除していきます。どれか一つ(たとえば左上とか)をスタートにして、その島につながっている橋を一つだけランダムに選択、残りを削除します。選択した橋につながってる次の島に移動して、同様にどれか選んで残りを削除します。行き止まりになったり、すでに行ったことがある島に戻ってきたりした場合は、行ったことがない島に繋がるところまで、戻る。というふうにして、全部の島をたどれば迷路完成。

大アイテムを配置する

島ごとにその島の面積に応じて、1 個または複数個、島の淵から一番遠い点をアイテム配置場所候補とする。ちょっと見難いけど、下図の赤い点。

その全候補ポイントから、左上にあるものをスタート地点(赤いまる)、右下にあるものをゴール地点(緑のまる)に設定。残りのなかから、最大 6 個を大アイテム(紫のまる)としました。

小アイテムを配置する

小アイテムは島の淵から一定距離はなれたラインにそって適当な数を並べている。上図(aid-dcc.com のじゃない)のグレーのラインが配置候補のラインで、淵から一定距離ずつオフセットした位置にあります。赤い丸が小アイテム位置。この絵は途中バージョンのものなので一直線に並んでいるが、最終バージョンではラインの左右にもう少しバラけた状態にしています。

ガードレールを配置する

ガードレールは基本的には島の外周に設置していますが、橋の部分は切り取らないといけません。ここで Boost の Geometry library が役に立ちました。島の外周データと橋の左右のラインが交差するポイントを求めたりといった、幾何計算が比較的簡単に実現できます。

島の周囲に描いてある緑のラインがガードレールです。見づらいかもしれませんが、橋の部分には描かれていません。これはデバッグ時に使った、最終的に JSON に書き出されるオブジェクトがすべて書き込まれた画像で、水色の点が小アイテム、グレーの点がリスタート候補ポイントです。海に落下したときは、落下したポイントから一番近いリスタートポイントから再開します。リスタートポイントは小アイテムを配置するときに使った手法とほぼ同じで、淵から一定距離はなれたところに等間隔に置いています。

配置データを JSON で出力する

出力にも picojson を使いました。標準出力に書きだしたものを、呼び出し側 (Node.js) が受け取ります。

Linux で動かすための C++ プログラムを Mac で作る

開発環境が Mac、デプロイ環境が Linux という異なる環境でしたが、OpenCV, Boost ともに両環境に存在したので、コンパイル環境さえ整えれば開発自体はさほど難しいものではありませんでした。Mac では Xcode で Command Line Tool としてビルド・デバッグし、それをそのまま Linux 上でコンパイルできるように、automake / autoconf を使って configure ファイルを作りました。Linux 側では configure && make するだけで実行ファイルができあがる仕組みです。コンパイラのバージョンが違うことなどが原因で、Linux 上でのみ発生するバグに遭遇することもありましたが、gdb を使うことで比較的容易に解決できました。

まとめ

Flash や Unity でもこのようなゲームは作ることはできます。その方がよい部分も多数あるのですが、プラグインが不要ですぐ体験できることや HTML5 + CSS3 のレイアウト機能は非常に強力で、やはり適材適所使い分けていくことが重要でしょう。HTML5 という環境でここまでのもが作り上げられたことは製作者自身も驚くところで、未熟な部分はまだたくさんありますが、これからの進化を楽しみにしています。

Comments

0