Starling と四分木で広大なマップを描画する
要件
何画面にも渡るような、広大なマップを縦横無尽に駆け回るというのは、 ビデオゲームの世界においてはファミコン以前からある楽しみの一つだ。
最近はゲームエンジンやフレームワークが巷に溢れているが、 こうした広いマップ（特にタイルマップで表現できないような柔軟なもの） を扱うのは、意外と標準装備ではできなかったりする。
今回は Starling で四分木 （QuadTree） を使って広いマップの描画を扱うものを書いたので、記録しておく。 （QuadTree を使った Sprite はすでに Starling の extension として作っている人がいたが、 自分のフレームワーク用に最適化するために今回は自分で書いた。）
QuadTree で Viewport Culling を行うデモ
まずは作ってみた結果を。
QuadTree Demo 1
- 方向キーで移動
- スペースキーでズームアウト
- Z キーでデバッグ表示の ON / OFF
- （画面上の UI でも操作可能）
画面中央の枠が実際の表示領域 （Viewport） であると思ってほしい。 画面を動かすと、Viewport 周辺にあるオブジェクトだけ表示が有効になっていることが分かると思う。
QuadTree のような工夫が必要な理由
世にあるゲームエンジンの多くは、2D でも 3D でも描画オブジェクトをツリー構造で扱う。 （よく Scene Graph と呼ばれるものだ。Flash では Display List と呼んだりもする。）
3D だと普通は画面に見えているものだけを計算・描画するように選定する処理 （Culling） がエンジンに備わっている。 ところが 2D のエンジン（Starling や Cocos2D）ではこれを標準でやっていないことが多い。 そのため、単純に広いマップを作ろうとして巨大な Scene Graph を作ると、 画面外にあるオブジェクトに対しても行列計算が走り、重くなる。スケールしないのだ。
だから自分で空間分割をして、見えていない領域をばっさり計算対象から外すように、 Culling のようなことをしてやる必要がある。
空間分割について
空間分割は 3D や物理エンジンでは必須のテクニックなので、先人達によっていくつもの手法が確立されている。 有名どころだと、
- Uniformed Grid （シンプルに均一の格子で区切るもの）
- kd-tree （空間を次元軸に沿って 2 つに割っていく）
- QuadTree（3D なら Octree / 階層的な入れ子ノードで分割）
- BVH （Bounding Volume Hierarchy / 近いオブジェクトをボトムアップでまとめていく）
などがある。当然、各種メリット・デメリット、向き不向きがある。 参考資料としては、日本語の書籍では以下のようなものを読めばよいだろう。
タイルマップでない世界を分割する
世界がタイルマップで構築されている場合（スーファミ以前のドラクエやマリオを想像してほしい） は単純なグリッドで分割してやればよいだろう。 でも Ubisoft の「レイマン」のようなリッチな画面を作るとき、 個々のオブジェクトを自由に拡大縮小・回転して配置したくなる。
そうすると空間には大小様々な領域を持つオブジェクトが散在するようになる。 空間的に密な部分もあれば疎な部分もあるかもしれない。これは Uniformed Grid では扱いづらい。
今回は QuadTree でこれに対処した。空間全体をまず 4 つの領域（ノード）に区切る。 オブジェクトが 4 つのどこかにすっぽり収まるなら、その領域をさらに 4 つに区切って、同じことを繰り返す。 これ以上すっぽり収まらなくなるか、ある程度細かい領域に分割できたなら、そこでやめる。 こうしてツリー上にオブジェクトを登録しておけば、 画面外にあるオブジェクトを処理の対象から除外するときに、 ツリーの根元のほうからばっさり OFF にできるというわけだ。
ちなみに実際には 4 分割といっても、空間をきっちり分けるのではなく、 各ノードがある程度他のノードに重なるように分けていく。 これは境界線上にまたがるオブジェクトがツリーの上層にとどまってしまう問題を避けるためだ。 こうした QuadTree を Loose QuadTree と呼んだりする。
汎用化して自前フレームワークに取り込み
最終的には汎用的に使えるように、自前のフレームワークのコンポーネントとしてまとめた。 以下のデモはそのコンポーネントを使用して、複数レイヤーを扱っている。 （操作方法は先のものと同じ）
KrewWorld というクラスにレイヤーを登録して、レイヤーにゲームオブジェクトを置くイメージ。 KrewWorld が内部で QuadTree を使う。QuadTree 部分のコードは こんな感じ 。
オブジェクトの移動や衝突判定などを考えるとまだまだやることがあるのだが、 とりあえずはこれで「スケールする広いマップの描画」ができるようになった。
次は
もともとアクションゲーム（タイルベースでない 2D のプラットフォーマー） が作りたくてこれを実装していた。 ようやくこれで本来のゲーム作りに着手できる。
色々便利な道具が揃っている時代だが、それでも結構 自前で用意してやらなければならないものはある。 ものを作るためには努力は惜しんではなるまい。
Menu
Tatsuya Koyama
Game Developer
