長々と開発中だった SandVox Simulator を公開しました。Falling-sand game と呼ばれているゲームの一種で、それの3D版です。スマホとPCどちらからでも遊べます。ある程度のスペックがあれば……。
以下では開発に至った経緯や小話、技術関連の話と近況について書いておきます。
開発に至った経緯
去年のいつ頃だったか忘れましたが[1]、VALVE INDEX を手に入れて念願の3次元VR体験が可能になったので、VRChat で遊べる砂遊びワールドみたいなものを作ろうと考えていました。
VR で遊ぶ以上3次元である必要があるのですが、処理速度上シェーダで更新処理を書く以外なく、かつシェーダでは scatter 処理がほとんどできないため、実装が果てしなく難しくなります。そんなこんなでお蔵入りしていたアイデアですが、時を経て元の目的を忘れ、とりあえずブラウザで遊べる3D砂ゲーを作ろうということで開発が始まります（昨年8月末頃）。
実はこの頃超忙しく、本当はこんなことをしている暇などなかったのですが、人間とは不思議なもので忙しいときほど余計なことをするモチベーションが上がるんですね。時間の余裕に反比例して開発は進み、着手から2週間足らずでいい感じになってきます。
その後さらに忙しくなり、さすがに開発をする暇もなく半年ほどプロジェクトは放置されます。
途中で得た知見
開発の途中で見た目を fancy にすべくレイトレーシングが導入されました。この過程でボクセルに対するレイトレーシングの考察と、簡易的なボリュームレンダリングの式の導出を行うことになります。これだけでも大きな価値がありました。
他にも JavaScript の extreme な最適化に関するいろいろな知見が得られました。詳細は後述します。
技術的な話
シミュレーションは 64×64×64 のボクセル上で行われています。これは 512×512 の画像のピクセル数と同じであり、総数は 262144 と非常に多いです。
これは全てのボクセルに対して計算する処理について処理負荷が26万倍となることを意味しており、並大抵の最適化では太刀打ちできないことを意味します。
SandVoxel Simulator では、労力の 90% 以上は高速化に費やされているといっても過言ではありません。その甲斐あって、iPhone などのモバイル端末でも滑らかなシミュレーションが可能になりました。
処理時間26万倍の世界
まず、全ボクセルに対して行うあらゆる処理が激重になります。単純な関数呼び出し一つであってもです。対象のボクセルに対し何もしなくていい場合は、更新処理を行う関数を呼ぶ必要がありません。こうしてボクセルに何もない Empty なボクセルを特別扱いして、セルが Empty でないときだけ更新関数を呼び出すようにします。
しかし、これでは不十分です。ゲームのプレイヤーは容易にフィールド全体を砂で埋め尽くしうるので、Empty でないセルが全体を埋め尽くすことが容易に考えられます。
実際に埋め尽くした様子
ここまで極端でなくても、画面下半分が水で埋まっているなどという状況は容易に想定できます。そうした状況でもできれば快適に動いてほしいものです。そこで、実際に更新がありそうなセルだけについて更新関数を呼び出すことが考えられます。
- 隣接する前後上下左右6セルのいずれかに変化があった
- 自身に変化があった
セルについてのみ更新関数を呼び出すことで、画面下半分が水で埋まっているといった状況でも高速な処理を行うことができるようになりました。
しかし、これでも高速化は十分ではありませんでした。26万倍という定数があまりに大きすぎて、通常考えなくていいレベルでの最適化が必要になっていました。
ループ展開
何もしていないように見えても、for 文の内部では
- ループが終了したかどうかの条件分岐
- ループのために使用する変数の更新
が行われています。これらは通常、取るに足らない処理であり、そもそも気にすること自体が馬鹿げているとすらいえます。しかし、ループの中身が軽く、処理時間が26万倍される世界では、このような処理ですら処理時間が非常に重要になってきます。
そこで、ループ処理を展開し、ループの中身をコピペして条件分岐が走る回数を n/1 に減らします。この n は、ループ更新に要する時間が十分（相対的に）小さくなるように定めます。
本当ならこんな処理はコンパイラがやってほしいところではあるんですが、残念ながら今日の JavaScript ではそうともいかないようです。実際、このようなループ展開で数十%程度処理が軽くなりました。
JIT を意識する
多くの JavaScript の処理系では Just In Time Compiler (JIT) が採用されており、必要に応じてプログラムの断片をインタプリタによる処理ではなく直接的な機械語に変換してから実行する仕組みが取り入れられています。これらは当然ですが大幅な処理速度向上に繋がります。
JavaScript の高速化でよく言われていることとして、関数呼び出しのインライン化が挙げられます。JavaScript においては関数呼び出しはオーバーヘッドが大きく、関数呼び出しのインライン化は多くの場合高速化に繋がります。しかし、やたらめったら関数呼び出しをインライン化すればいいのかというと、そういうわけではありません。
JavaScript の JIT は関数単位で行われることが多く、あまりに巨大な関数は関数の JIT 化を阻害します。つまり、適切な粒度で関数呼び出しを行うことが必要であり、そのような粒度の見極めが極度の高速化においては重要となります。
高級な機能を使わない
ボトルネックになりそうな部分では、JavaScript で提供されている高級な機能を一切使用していません。オブジェクトの生成は一切行わず、フィールドアクセスすらも極力避け、ほとんどアセンブリ言語のように JavaScript を使用します。
結果として生成されるコードは醜い限りですが、使用している Haxe のインライン化機能を使って可能な限り可読性を保つようにしています。
ビット演算をフル活用する
メインのセル更新処理では、どうしても条件分岐が大量に出てきます。例えば木のセルに対しては「隣接するセルが引火の原因となる場合は一定の確率で木を燃やす」という処理を行っています。ここで問題があり、引火の原因となるセルは
- 燃えている木
- 炎
- 電気の通った鉄
- 溶岩
- 燃えている油
- 溶解した鉄
- ……
と大量に種類があります。これらすべてに対して比較処理を行っていては到底処理が追い付かず、また、新しい元素を追加したときのバグの要因にもなります。そこで、元素の識別子にその元素の特性をそのまま埋め込む工夫をしています。
例えば、引火の要因となる元素については、どこかのビットが立った HOT フラグを用意しておき、 OR 演算で識別子自体に HOT フラグを埋め込んであります。こうすることで AND 演算でまとめて特定の種類のセルを比較することが可能になり、新しく引火の要因となるセルを追加するときにも、識別子に HOT フラグを立てておくだけでよいのでバグを抑制することができます。
メモリのアクセスを連続化する
C/C++ などでは、CPU のキャッシュを考えてメモリアクセスを連続化すると処理が高速になることがあります。JavaScript でも同様のことが成り立つかは疑問だったのですが、試してみた限り（少なくとも Chrome においては）連続的なメモリアクセスは離散的なそれよりも高速に処理されていました。
そこで、更新処理の枝刈りを行う際には、実際の更新順序よりもメモリの連続性を優先した順序でチェックを行い、枝刈りの高速化を図りました。ループ展開と併せて行うことで相当の効果があったと思います。
GLSL も高速化する
レイトレーシングを行っているので、GPU 側の処理も相当なものになります。OpenGL の wiki を参考にして可能な限り 乗算→可算 のコンボ (MAD = multiply, then add) を使うようにしたり、ビルトイン関数を使って条件分岐を減らしたり、登場頻度が高い空白のマス目に対する処理を狙って高速化したりします。
さらに、CPU から GPU へのデータ転送にかかる時間も洒落にならないので、必要な部分だけを texSubImage2D を用いて送信するなどします。とにかく何も起きていないときの処理を最大限高速化することがユーザー体験において重要です。
高速化以外の話
見た目について
チープな Ambient Occulusion もどきを取り入れてみたりしました。元々データがボクセルなので、周辺に照光を邪魔するボクセルが存在するかどうかでなんとなく日当たりのよさを計算できます。地味ですが見た目に絶大な効果を発揮します。
また、ライティングに使用する法線ベクトルを滑らかにする処理を加えました。
例えば画像のようなレンガ球であれば、本来ライティングもゴツゴツした感じで行われるはずなのですが、法線ベクトルを平滑化する処理を加えることで、柔らかいシェーディングを実現しています。法線ベクトルの平滑化は全ボクセルへのループを含み、ボトルネックとなり得るので、GPU 側で行っています。
また、こちらの記事を参考に、3方向からの滑らかなテクスチャマッピングを行う Triplanar Mapping を実装してみたりもしました。が、ボクセルに対してはあまり相性がよろしくなく、結局平面に沿ったマッピングの方が視覚的に良い結果が得られました。
内部データ
内部的にはこのようなデータでフィールド全体が保存されており、こんな感じのデータが毎回 GPU に転送されています。煙の色や、熱に関する情報はまた別のテクスチャを通して処理しています。
シェア機能の実装
シェア機能のためにサーバー側のプログラムも実装しました。今までは簡単な PHP を直に書いていたのですが、今回データの正当性チェックのロジックがややこしくなり、さすがに PHP を直に書くのが辛くなったため、Haxe の PHP 出力機能を使ってみました。コンパイルオプション一つで出力ターゲットを変えることができ、プラットフォーム依存でない部分のコードはそのまま再利用することができるため、サーバーサイドのプログラムも比較的快適に書くことができました。ありがたや。
右下にある Share ボタンから作品を Twitter に投稿できるので、いい感じの作品ができたらぜひ投稿してください。
近況について
どうにかやっています。
- しばらく集中的に英語を勉強していました。無事に English VTuber の沼に沈みました。
- あまりにやわらかあたま塾が遊びたくてついに Nintendo Switch を購入しました。そのまま全プラチナメダルコンプリートと柔王の称号を獲得しました。スコアが 8600 台に到達して満足しました。
- Noita にドハマりして数百時間を溶かしました。いまだに実績が全て埋まっていません。
そんな感じです。
- 今調べてみたら去年じゃなくて一昨年でした。時間の流れが恐ろしい。 ↩︎
