> makibishi throw|

「Game Programming Patterns」 読了した

積んでいた「Game Programming Patterns ― ソフトウェア開発の問題解決メニュー」を読み終わったので、感想などをダラダラと書いていきます。

全体的な感想

ゲームを題材にしたデザインパターンの本ですが、非常に面白く、また汎用的な内容でした。

まず 1 章で良いアーキテクチャ、悪いアーキテクチャについて定義し、それ以降の 2〜20 章でパターンを紹介しています。各パターンについて、まず素朴なコードを提示し、そのコードに機能を追加していった時にコードが複雑になっていく状況を見ていき、どのようにすれば良かったのだろうか?という形式で説明しています。

サンプルコードは C++で書かれていますが、C++でのみ実装可能なパターンは一つもなく、あらゆる言語で応用出来る内容です。私の場合は C++の仮想メソッド、フレンドクラスなどは知らなかったので調べる必要がありました。

ゲームを題材にしているおかげで例示されている状況が普通に面白く、頭に入ってきやすいです。特にゲーム開発経験者であれば、実際の開発シーンでよく遭遇する場面がそのまま題材になっており、すぐにでも使えそうな知識が得られます。

ゲームは固有のハード機器の上で動かすことが多いためか、キャッシュミスや GPU のグラフィックス描画、 CPU パイプラインのストールなど、計算量の削減とは別の観点からのパフォーマンス改善についても触れられており、計算リソースがシビアな環境下にも役立てられそうです。

各章について

第一章 アーキテクチャ、実行速度、ゲーム

良いソフトウェアアーキテクチャ=変更が容易なコードベースと定義し、実行速度とのトレードオフや、悪いアーキテクチャとの棲み分けについて述べています。ゲームの実行速度に関して、面白いゲームを速くすることの方が、速いゲームを面白くするよりも簡単だという言葉が印象的でした。

また、悪いアーキテクチャ(変更が難しいコードベース)がふさわしい場面としてプロトタイプの作成を挙げており、プロトタイプの出来が良かったために、 悪いコードベースのまま製品に組み込まれてしまうのを防ぐために製品とは別言語で実装するというテクニックも紹介されており、これには苦笑いしました。

第二章 コマンド

ゲームのキーコンフィグや、Undo、Redo を容易に実装出来るパターンです。AI によって操作されるキャラクターのインターフェースとしても使えるというところがなるほどと思いました。

第三章 フライウェイト

インスタンスに依存しない重量級のデータを別オブジェクトとして切り出し、インスタンスからはそのデータをポインタとして参照するパターンです。実際のグラフィックスカードでも共通のメッシュ、テクスチャ+インスタンス毎のパラメータという形で描画する方法をサポートしているというのを初めて知りました。

第四章 オブザーバ

ゲームの実績解除の機能を例にオブザーバーパターンについて説明しています。オブザーバーとサブジェクトを使って情報をやりとりすることで、無関係なシステム同士の結合を避けることができます。 より複雑な例として、オブザーバが複数のサブジェクトを監視出来るパターン(オブザーバーとサブジェクトが多対多)についても言及されています。 サブジェクトがオブザーバーの死に気付かない場合、逆にオブザーバーがサブジェクトの死に気付かない場合の対処法についても述べられており、オブザーバーパターンを採用する場合の実践的な実装に触れることができました。多対多のパターンはかなり複雑なので、一度実際に実装してみたいです。

第五章 プロトタイプ

JavaScript などの言語に組み込まれている prototype を発端に、同じような発想がゲーム上のコードにも役立つ場面について説明しています。モンスターなどのデータを効率よく管理するために prototype を使うという発想も興味深いです。ただ、prototype の循環の検証など、データから実際のパラメータを復元する部分が複雑になりそうという印象でした。

第六章 シングルトン

この章はパターンの紹介ではなく、なるべくシングルトンパターンを使うことを避けることを主眼に置いています。シングルトンはそもそもグローバル変数で、加えて遅延初期化による複雑な問題を引き起こすとして、シングルトンである必要がない状況を解説しています。

第七章 ステート

ステートマシンを用いて各状態での振る舞いをシンプルに記述するパターンです。このパターンの紹介で挙げられている例、おそらくアクションゲームの開発者であればほぼ 100%同じような状況に直面しているのではないでしょうか。私も単純な動きをする敵は例のような if 文の塊で作れたものの、ある程度複雑な動きをするボスキャラクターの実装では同じようにいかず、色々と知識を仕入れた結果ステートマシンを用いた実装で作り直すという経緯を辿ったことがあります。

まず列挙型でステートを定義するところから始まり、より複雑な実装にも対応出来るよう、ステートをクラスにして個別の振る舞いを各ステートに持たせるところまで丁寧に書かれています。 ステートをクラスにした場合に振る舞いの重複した実装を防ぐ階層的状態機械(HFSM)は初めて知りました。

第八章 ダブルバッファ

通常ゲームエンジンが知らない間に行ってくれているダブルバッファの仕組みについて説明しています。自分でダブルバッファリングを実装する必要がある C++のゲームライブラリ、 DX ライブラリを思い出しました。

ダブルバッファの、「次の状態を予め準備しておく」という考えを画面描画以外に適用する例も示されており興味深かったです。

第九章 ゲームループ

この章と次章「更新メソッド」は、パターンの紹介というよりはゲームエンジンの内部実装の説明に近いです。実時間の進行とゲーム世界の進行を同期させるため、ゲーム世界の状態更新とゲームの画面描画の周期を独立させるというアイデアや、ハード機器の事情によって消費電力を低減させたい場合のループのさせ方について説明しています。

ゲームエンジンの実装が大変さを垣間見ることが出来る章です。

第十章 更新メソッド

これも大抵のゲームエンジンで初めから実装されています。ゲームに登場するオブジェクト毎に update メソッドを持たせ、メインループで各オブジェクトの update を呼びます。冒頭のちょっとしたことをするだけでも複雑になっていく例を見ると、ゲームエンジンのありがたみが分かります。

第十一章 バイトコード

非常に大掛かりなパターンの紹介です。ゲームユーザーに非常に高レベルなカスタマイズを許す場合の考え方が書かれています。ユーザーが利用可能な API を仮想マシンから利用出来るようにして、セキュリティ面を保証しつつゲームのカスタマイズを可能にしています。ゲームエンジンでよく Lua 言語が使われますが、その背景が分かります。

また、Ruby がインタプリタパターンからバイトコードに改めたという話にも触れており、面白かったです。

第十二章 サブクラスサンドボックス

基底クラスを使った高々 1 階層の継承関係を作り、基底クラスに共通のユーティリティメソッドを持たせることで派生クラスとシステムの結合を防ぐパターンです。基底クラスにどのような形でユーティリティメソッドを持たせるのかについても、様々な例が紹介されています。

第十三章 型オブジェクト

例えば「モンスター」のような概念について、各モンスターを派生クラスとして実装するのではなく「種族」のような型オブジェクトを持たせることで再コンパイルなど変更の手間を防ぐ手法を解説しています。これにより、各モンスターのデータを json など単なるデータとして管理出来るようになり、レベルデザイナー・プログラマー間のやりとりも楽になります。

ポケモンはまず間違いなくこのパターンが使われていると思います。

第十四章 コンポーネント

最初に多重継承によって引き起こされる死の菱形(菱形継承問題)について取り上げ、この問題の解決策として、ビヘイビアをコンポーネントとして切り出すコンポーネントパターンを紹介しています。Unity など主流のゲームエンジンで Entity Component System が採用されているため、このパターンもどちらかというとゲームエンジンの内部実装の説明に近いかもしれません。

コンポーネント間の通信の実装は相当複雑になりそうで、Unity のように凄まじい量のコンポーネントをサポートしているケースではどのような作りになっているのか気になりました。

第十五章 イベントキュー

ゲームの同期的なサウンド出力を例に、イベントキューを使って非同期にリクエストを処理する例を説明しています。単純な配列を使ってO(1)O(1)でキューを実装する例(環状バッファ)が紹介されていますが、データ構造の授業の課題で同じものを実装したことがある気がします。

また、O(n)O(n)かかるが同じリクエストを統合し、まとめて処理する方法や、オブザーバーパターンでも言及されていた、1 対多、多対 1、多対多の読み込み/書き込みについても軽く触れられています。

第十六章 サービスロケータ

サウンドシステムのような多くのクラスと結合するクラスについて、抽象インターフェースを介してアクセスさせるパターンです。紹介されていた例では抽象化されたインターフェイスに接続されるサービスプロバイダを使い分けるシチュエーションについて詳しく説明されていませんでしたが、下記の例のように、マルチプラットフォーム開発で接続先の API が変わる状況でまさにこのパターンが使われているのをみたことがあります。(クラス名は適当です。)

class Locator {
  private static service_:Audio;

  // TARGET_PLATFORMはコンパイル時の環境変数など
  public static function provide(TARGET_PLATFORM) {
    var service = switch (TARGET_PLATFORM) {
      case 'PS4':
        new PS4Audio();
      case 'Switch':
        new SwitchAudio();
      case 'Mac','Unix':
        new UnixAudio();
      case 'Windows':
        new WindowsAudio();
      case _:
        new NullAudio();
    }

    service_ = service;
  }

  public static function getAudio() {
    return service_;
  }
}

第十七章 データ局所化

この章はパターンというよりはパフォーマンスの話です。CPU=>メモリの応答の事情を考慮した、パフォーマンス改善について述べています。

CPU は高速で小サイズの CPU キャッシュを持っており、そこには CPU が要求したデータの他、そのデータに隣接するデータが読み出されるため、配列のような連続的に領域を確保するデータ構造の方が早いことが例え話で説明されます。その後前述のコンポーネントシステムでキャッシュミスによる速度低下が発生している例を示し、パフォーマンス改善の例を解説しています。この改善例はやや扱いづらい状態になっており、データ局所化の観点からみたパフォーマンスと良いソフトウェアアーキテクチャがトレードオフの関係にあることが分かります。

この章に書かれていたことはほとんど初耳で、RAM と CPU の性能差が年々開き続けており、RAM からのデータフェッチの間 CPU がかなりの時間アイドル状態になっているということ自体初めて知りました。また、著者が実際に実験を行い、配列とポインタで 50 倍ものパフォーマンス差が出たというのも目から鱗でした。

第十八章 ダーティフラグ

図形の変換でおなじみのアフィン変換を例に、遅延評価を使って無駄な計算を防ぐ手法について説明しています。 RPG のバフの計算など、様々なシーンに使えそうだなと思いました。ただ、バグなく実装するのは骨が折れそうです。

第十九章 オブジェクトプール

メモリ領域のフラグメンテーションについて問題提起し、頻繁にオブジェクトが作成・削除される環境でフラグメンテーションを防ぐ方法を説明しています。再利用可能なオブジェクトを探すためにO(n)O(n)必要なのを、配列とポインタ(とフライウェイトパターン)を同時に使うことでO(1)O(1)で実現する実装が非常に参考になりました。

この本ではオブジェクトプールをフラグメンテーションの解決策として挙げていましたが、過去にゲームのサンプルコードで、毎フレーム実行されるコード(update メソッド)の中で重いオブジェクトの new を防ぐためにオブジェクトプールが使われていたのを見たことがあります。様々な観点でパフォーマンス改善に寄与するパターンだと思います。

第二十章 空間分割

RTS の戦闘フラグやアクションゲームの衝突判定などで、判定回数がO(n2)O(n^2)になるのを避けるためのパターンです。 本書では同じマス、隣接マスとの判定のサンプルコードのみ示されており、本格的な空間分割のアルゴリズムは名前の紹介に留まっています。

書評からは外れた話になりますが、私は面接の場で自作ゲームの衝突判定について質問され、よく分かっていなかったため適当な返しをしてしまい、不合格になったという苦い経験があります。それが悔しく衝突判定のアルゴリズムについてかなり調べたので、アクションゲームの衝突判定について少し突っ込んだ解説が出来そうです。この辺りの話をいつか記事にしたいです。