近代的タスクシステムの構築

program


いつか本に書こうと思っていたが、多忙につき、本を書くどころではない状況なので、内容が風化する前に誰かの参考になればと要点だけでも書き残しておく。


いまの視点(2009年)で見たときに拙著(ASIN:4798006033)にて不足している部分を補足するためのものである。この本自体はすでに絶版になりプレミア価格で取引されているが、もし参考文献を探しているなら、出来ればこの本は買わずに次に出すゲームプログラミング本のほう参考にして欲しい。


■　タスクシステムの定義


ここで言う「タスクシステム」とは、ゲームプログラミングの教科書に出てくるものである。(cf. 「本格的なシューティングゲームを実現するタスクシステム」 http://codezine.jp/article/detail/297?p=1 )


「タスクシステム」は初期のビデオゲームで、V-SYNCをイベントトリガとして画面を描画するときに、その描画プライオリティをコントロールすることが主な目的である。


(中略)


現在においても、依然として描画プライオリティを描画順序を調整することで実現することがあるので、その実装手段はゲームプログラミングにおいて興味の対象である。


また、その他のメリットとしてタスク間通信が出来るということや、タスクシステムを用いたフレームワークから恩恵が受けられる(かも知れない)ということが挙げられる。


■　タスクシステムを現代の視点で捉え直すと？


「描画用のcallback listならば、std::list<Task*>とかで充分じゃないか」と言われるかも知れない。


これは一理ある。ビデオゲーム黎明期においては、オールアセンブラで書くことが普通だったので、std::listのような便利なコンテナがあるわけでもなく、技巧的な方法でstd::listみたいなことを実現していただけで、いま書くならstd::listでもパフォーマンス的に問題がないことが多い。


(中略)


それではタスクシステムは現代においては不要なのかというとそうでもなく、成熟したタスクシステム(タスク自体のデバッグを支援するタスクデバッガのような環境を含めて「タスクフレームワーク」と呼ぶほうがふさわしいかも知れない)は、ゲーム開発において依然として有用であり(以下略)


■　タスクシステムを現在の実装技術で実装しなおすと？


話の範囲を限定するために、シューティングゲームを実装する場合を考えよう。


一つの描画単位を「タスク」と呼び、次のinterfaceを持つとしよう。

template <class DrawContext>
class Task
{
public:
  virtual void OnDraw(const DrawContext& context) = 0;
  virtual ~Task() {}
}

いま「タスク」という用語を、このTaskクラス派生クラスのことを意味すると定義しよう。


実際的には「描画を担うOnDrawメソッド」と、「そのキャラクターを移動させワールドを更新する処理」とを分離することもあるが、ここでは、簡単のためこのOnDrawメソッドによって、ワールドの更新もされるとしよう。


「ボス」はタスクであり、このボスの「取り巻き」もまた、タスクである。ボスは取り巻きを残した状態で先に消えて(プレイヤに倒されて)しまうかも知れない。取り巻きたちは、自分のボスを参照している。ボスが消えたあと、その参照は不正なものにならないか？これをどうやって解決するのか？


■　タスクシステムに対する代表的な批判


タスクシステムが保持しているlist(std::listなど)は「タスクのごった煮」であり、すべてのタスクにアクセスできるような(どちらかと言えば)globalな存在である。


タスクシステムに対する最初の批判として、「そのような他のオブジェクトを容易に破壊できる仕組みを使うべきではない」というのがある。


古典的なタスクシステムにおいてはタスクに番号(プライオリティ)が振られており、番号を指定して特定のタスクのポインタを得ることが出来た。しかし、タスク番号を間違えて指定してしまうと間違ったタスクのポインタが得られ、容易にオブジェクトを破壊できた。黎明期のゲームはアセンブラで実装することが多かったのでそういうことも起こりえた。それが、それほど問題として取り沙汰されなかったのは、並列実行されているタスクの数が10個程度であり、またその種類も限られていたため、あまりそういうミスは発生しなかったからである。


現代において、タスクシステムを実装するなら、もう少しタスク間通信を抽象化してタスク側からタスクシステムが保持しているlistには直接触れないようにするべきだが、実装の方法によってはそういうことも起こりえる。


あと、タスクシステムの保持しているlist(std::listなどで実装される)は、単なる描画のためのcallback listであって、それを(タスク全部入りのlistだからという理由だけで)特定の種類のタスクを列挙するのに使っていいのかという批判。これはある意味正しいし、「タスク全部入りのlist」から特定の種類のタスクだけ列挙するのは一般的には大変なのでわからないではない。(解決法は後述)


■　タスクシステムにおけるタスク間通信


ボスのタスクが5000番だとすれば、(C++で書くなら)例えば次のように記述できるといいかも知れない。

BossTask* bossTask = dynamic_cast<BossTask*>(taskSystem.GetTask(5000));

該当番号のタスクが存在しない場合は、nullが返るように作る。この実装は、難しくはないだろう。またdynamic_castがあるので型に対しても安全である。あるいは、template methodを用いて、

BossTask* bossTask = taskSystem.GetTask<BossTask>(5000);

のように書けるようにしてあっても良いだろう。


しかし、このGetTaskには時間がかかりそうに思える。古典的なタスクシステムの実装においてはこの実装にhashは用いられておらず、listを辿るのに時間がかかった。ただ、昔のゲームでは生成されているタスクの数が少なかったために問題はそれほど顕在化はしなかった。


近代的なゲームでは、速度の面では実装にはhashを用いたい。hash表を使えばたいていはメモリを一回look upするだけで済むからだ。しかし、hashを用いる場合、複数のタスクに同じタスク番号を割り当てたいときに困る。


例えば、同じタスク番号のものを列挙するなどという場合は、どういうコードを書くことになるだろう？
「ボスの取り巻き」のタスク番号が6000だとして次のように書きたい。

std::list<ボスの取り巻き*> tasks = taskSystem.GetAllTask<ボスの取り巻き>(6000);

しかし、タスク番号からTask*を得るのにhash表を用いる場合、同一タスク番号のhash entryが大量にあることになり、効率が大幅に落ちてしまう。これはよろしくない。


また、タスク番号とは別に生成された型で判別したいということもある。つまり次のように書きたい。

std::list<ボスの取り巻き*> tasks = taskSystem.GetAllTask<ボスの取り巻き>();

これでも少し冗長な気もするが、C# 3.0ならば、

var tasks = taskSystem.GetAllTask<ボスの取り巻き>();

とか、C++0xなら

auto tasks = taskSystem.GetAllTask<ボスの取り巻き>();

書けるだろうから、それなりに簡素だろう。


結局、問題は、
・タスク番号を指定して、そのタスク群を高速に列挙できる実装
・タスクの型を指定して、そのタスク群を高速に列挙できる実装
なんかが欲しいのだが、その実装が容易ではないということだ。


それゆえ、段幕シューティングのようにタスクシステムで記述するとタスクが何千もに達するようなゲームにおいて、そのオーバーヘッドを嫌い、
・弾だけはタスクにしない
・その部分はタスクシステムを用いずに実装する
のような方法で実装することもある。これはこれで理にかなっている。描画するオブジェクトすべてをタスク(Task派生クラス)にする必要はない。


また、上のタスクを高速に列挙する問題を解決する試みとして、特定のタスクに関してだけタスクシステムが保持しているものとは別のstd::listで管理することもある。タスクシステムが保持しているタスクのlist(std::listなど)は、描画用のコールバックのためのもので、もっと粒度の小さいlistが必要になる場合、タスクシステムのlistを「タスク全部入りのlistだから」という理由で使い回すべきではないというのは先に述べた通り。


■　boost::shared_ptrとboost::weak_ptrを用いたタスク間通信


「ボスの取り巻き」タスクが「ボス」のポインタを保持している場合、「ボス」タスクがdelete(C++的な意味で)されると、その「ボス」のポインタが不正なものになる。これを検出する必要がある。以下、これを「不正なタスク参照問題」と呼ぶ。


この検出が難しいから、タスクシステムではタスク番号を指定してタスク間通信を行なうのが一般的で、それゆえ、オーバーヘッドが高く、


・「タスクシステムなんてたいそうな名前つけても、ただのstd::listじゃね？」
・「タスク間通信のコストが馬鹿にならないから、描画用のlistとは別に自前でlistを持つべき！」


みたいなことを言い出す人がいて、それも、代表的なタスクシステム批判である。


ただ、私に言わせれば、「不正なタスク参照問題」がC++で解決できないのは単に実装技術が不足しているだけであって、次のように実装すれば良い。

タスクシステムが持つべきタスクのlist:
std::list<boost::shared_ptr<Task> > taskList;

ボスタスクをボスの取り巻きタスクが参照したいときに、ボスの取り巻きタスクが保持すべきメンバ
boost::weak_ptr<BossTask> bossTask;

結局、このようになっていれば、あるタスクのオブジェクトとしての生存を(使用前に)チェックすることは容易にできる。ただし、表記がやや冗長ではあるし、weak_ptrのオーバーヘッドはそれなりに小さいが全く無視できるほどかと言われるとそれはケースバイケースである。


GCつきの言語なら、このへんの問題がスマートに解決するので、「不正なタスク参照問題」は発生しない。GCつきの言語で書くなら古典的なタスクシステムのタスク間通信なんて、オーバーヘッドが大きいだけなのでやる気にならないだろう。これも「タスクシステム」が批判される一因である。


■　タスクのhandle化


タスク間通信のときにタスクに事前に振っておいたIDを用いればどうだろうか？つまり、タスクにWindowsのresource handleのようにincremental IDを付与しておいて、このhandleからhash表を使ってTask*を求めようという案。hash表を引いた時に該当タスクが無ければnullが返るようになっていればタスクの生存チェックが出来る。


handleからTask*に変換するのはboost::unordered_map(hash表を用いた連想コンテナ。C++0xなら標準搭載?)をそのまま使っても良いだろう。


この方法は、shared_ptr/weak_ptrを用いるのに比べると洗練されていない気も少しするが、表記の冗長さで言えばどっちもどっち。


生存チェックだけならわざわざhandleで管理する必要はなく、生存タスクのポインタの値を常にhash表に書き込んで管理しておけば、生存のチェックは出来ると思うかも知れないが、一度解放したメモリアドレスと同じメモリアドレスがnewによって割り当てられることがあるので、これはうまくいかないのである。


ともかく、他のタスクのメソッドを呼び出すとき、それに先だって、タスクの生存チェックを何らかの方法で行なうことを約束するなら、タスク間通信は普通のメソッド呼び出しの形に還元される。


■　「タスク高速列挙問題」をC++で解決する


すべての描画したいオブジェクト(この「オブジェクト」は、C++的な意味でのオブジェクトではなく、ゲームの対象キャラクターという程度の意味)を「タスク」にする必要がないということは既に述べたが、しかしこうなっているとタスクフレームワークから強力なデバッグのための支援が受けられるかも知れない。そこで、ここではすべての描画の必要のあるオブジェクトはタスクとして取り扱われている/取り扱うと仮定しよう。


このとき、特定の種類のタスクだけを高速に列挙したい。


「特定の種類」というのは、
・タスク番号
・RTTIで(typeid演算子で)取得された型情報
・事前にオブジェクトごとに設定しておいた値
など、何でも良い。


しかし、実際的には、「画面上のすべての弾に対して自機と接触判定を行なう」のように、「特定のタスクに対してメッセージを送りたい(メソッドを呼び出したい)」というより、「特定の種類のタスクを列挙してそれらすべてに対してメッセージを送りたい」ことのほうが普通だから、特定の型のタスクだけ高速に列挙することを考える。(この列挙では生存しているタスクしか列挙されず、自ずと(列挙された)タスクの生存性の保証をしてくれるから、タスクの生存チェックを行なう必要はない。)


つまり、typeid演算子の返り値が同じもの(動的な型が同じもの)のコレクションを返す、次のようなtemplate methodを実装することを考えよう。

template <class T>
std::list<T*> TaskSystem::getAllTask();

std::list<T*>を返すつもりなら最初から、

boost::unordered_map<type_info*,std::list<Task*> > tasksList;

のようなものをタスクシステムが保持しておいて、これを返せばいいと思うかも知れない。しかし、std::listに対するremoveであって、std::listに対するremove(erase)はO(N)の時間がかかるので(中略)


また、一つのタスクを生成するごとに std::list<Task*>をnewするのは馬鹿らしいので、その型の一つ目のタスクならば、std::list<Task*>をnewするのではなく、生のポインタを保持したほうがいいかも知れない。また、その型のタスクが0個になったときにこのtasksListからremoveするのも、せっかくnewしたstd::list<Task*>を解体することになるので(生成するタスクの種類が限られているタイプのゲームでは)やめたほうがいいような気は少しする。


しかしstd::listであれば、そのあとforeachで回す場合、列挙されたものが空集合であってもforeachを何もせず抜けるだけであり、タスクの生存チェックを明示的に書く必要がなくなるので便利なことが多い。


■　高速に列挙できて、かつ、高速にinsert/erase出来るコンテナ


以上の考察により、タスクシステムをより近代的で洗練された形で実装できるかというのは、
・メモリを馬鹿食いしても良いので「高速に列挙できて、かつ、高速にinsert/erase出来るコンテナ」を作れるか
という問題に帰着することがわかった。


ただ、タスクをそんなに同時多発的に生成しないというなら、この限りではないし、同時多発的に生成してもターゲットマシンが充分速いなら列挙ぐらいstd::listやstd::vectorをtraverseしたところでどうってことはないのだが。


あと、元来、描画順をコントロールするために作ったclassに、タスクの列挙みたいなことまでやらせるのは役割が違いすぎるという批判もあって、それもまあ一理あるので、ここでは設計の問題にはこれ以上踏み込まないが、タスクに一連のことが出来るタスクフレームワークのようなものを構築するのがここでの目標なので(中略)


ともかく、
・メモリを馬鹿食いしても良いので「高速に列挙できて、かつ、高速にinsert/erase出来るコンテナ」を作れるか
を考える。


std::listは(reverse iteratorでのtraverseが可能なように)双方向リストとして実装されているから、反復子を引数に渡してのeraseはlistの先頭からtraverseする必要はなくO(1)で済む。そこで、Task*からそれを保持しているlistの反復子への連想コンテナがあれば、eraseするのに困らない。結局、次のようになる。

boost::unordered_map<type_info*,std::list<Task*> > tasksList;

struct PseudoIterator
{
  std::list<Task*> container;
  std::list<Task*>::iterator iterator;

  void erase() { container.erase(iterator); }
};
boost::unordered_map<Task*,PseudoIterator> taskToIterator;


taskToIteratorでタスクの生存のチェックが出来そうに思えるが、それは間違いである。さきほども書いたがタスクを解放したあと同じアドレスが割り当てられることがあるからだ。生存チェックが必要になるコーディングスタイルは、やや書きにくいので、tasksListから都度欲しいタスク群を列挙させるほうが使い勝手が良い。


また、事前にsingletonであることがわかっているオブジェクトに対するアクセスは、getAllTaskではなく、次のように単純化されたメソッドを用意しても良いだろう。

template <class T>
T* TaskSystem::getTask();


■　タスクの消滅


タスクのOnDrawを呼び出し中に自分自身のタスクをdeleteすると、OnDrawの呼び出しのために用いていた反復子が不正になる。自分自身以外のタスクならいいのかということもない。(例えば、OnDraw呼び出しの前に次の位置を示すように反復子を事前に進めておいても、そのタスクが消去されると結局その反復子は不正になる。)


そこでタスクの消滅のためには、「描画用のcallbackとして保持しているタスクのlist」をtraverseしてOnDrawを呼び出したあと、死亡フラグが立っているTaskを掃除する必要がある。


そのときに、さきほどのtasksListからも該当タスクを除去する必要がある。実際のコードで示すと次のようになる。

Iterator it = tasks.begin();
while(it!=task.end())
{
  iterator nextIt = it++; // 事前にひとつ進める
  if ((*it)->isKilled)
  { // このタスクは消滅
     tasks.erase(it);
     taskToIterator[*it].erase();
     taskToIterator.erase(*it);
     delete *it;
  }
  it = nextIt;
}


■　カスタム版のIterator


ここまで来れば、isKilledフラグが立っているタスクは、getAllTaskで列挙されないようになっているほうが便利であることに気づくだろう。
getAllTaskを呼び出したときに、std::listをコピーするのは嫌だし、かと言って、カスタム版のstd::list::Iteratorを作るのもちょっと嫌だ。


C++0xならラムダ式を使えるのでstd::reference_closureを用いて(以下略)


■　C#でタスクを列挙させる場合


GC付きの言語なら、不正な参照にはならないので、上のようなことをしなくていいんじゃないかと言われるかも知れないが、それは少し違う。「タスク」の消滅は、isKilledフラグを立て、次のtraverseのときにそのタスクを掃除(解体)するというプロセスで行なわれる。


よって、(C++的な意味での)オブジェクトは生きているが「タスク」としては死んでいるという状態がありうる。そこで、C#で書く場合でもやはり、タスクシステムに対して型を指定して、その型の生きているすべてのタスクを列挙するenumeratorがもらえると便利である。(以下略)


■　タスクをcoroutineで実装する


(割愛)


■　タスクを階層化する


(割愛)


■　タスクプライオリティの変更を高速化する


「タスク」はタスク番号で管理されており、これによって描画順が決まることは既に述べたが、生成に際してタスクのlistの適切なところにinsertしてやる必要がある。


std::listなので(適切なところを探して)insertする時間はO(N)になるが、大量の弾幕を「タスク」として表示するようなゲームの場合、この時間も馬鹿にならない。これを高速化するために(中略)、同じ型のタスクであれば、同一タスクプライオリティを持つことが多いので同じ型のタスクを列挙してみてその一つ目のタスクがいま生成したタスクのタスクプライオリティと一致するなら、そのタスクの前方にinsertするという方法が考えられる。これは(中略)


もう少し別な実装として(中略)　この問題は結局、unordered_mapに対する列挙がどれほどの速度で出来るのかということに帰着するが、(以下略)


■　タスクシステムからタスクフレームワークへ


古典的タスクシステムをどう書き直すかを考えてきたが、タスクシステムに要求される機能が固定的ではないので、汎用的に書き下すのは結構難しい。それでも共通化できる部分は共通化してゲームライブラリとして再生産性を高めるのが(中略)


また、ここで製作したタスクシステム/タスクフレームワークをそのまま流用しないとしても、これらのシステムを実装する経験を通じて、タスクに対する理解が促進されることを著者としては願ってやまない。


ToDo : いずれわかりやすく書き直して、もう少し実装を練りなおした上でパフォーマンス測定などして実際にそれで簡単なゲームを作ってみたりして、次に出すゲームプログラミング本に詳しく書く。そのときタスクの並列実行についても書く。


■　タスクの並列化について


はてブで並列化について突っ込みをいろいろ頂戴していますが、この記事に書いたものは古典的なタスクシステムを近代的な手法で(C++ templateやC++0xやboostを自由に用いていいという仮定で)どう実装しなおすかについてまとめたものです。


今回紹介したタスクシステムを応用すれば、同一タスク番号のものを列挙することは出来るので、traverseのときに(例えば)同一タスク番号のものに対しては並列実行するように改造することは容易です。


ただ、並列実行させたい場合というのは、普通は何万とか何十万という個数のオブジェクトの衝突判定をしたいだとかそういう現実的なニーズがあることが多いので、そういう場合は、この記事のようなタスクシステムの延長で実装するんじゃなくて(タスクを呼び出すオーバーヘッドだけでも馬鹿にならないので)、それ専用のミドルウェアを開発したほうがパフォーマンス的に見ても勝ると思います。


関連記事 : カプコンの MTFramework(→ http://game.watch.impress.co.jp/docs/20070131/3dlp.htm )


■　追記


補足のため明日の記事に続く。
http://d.hatena.ne.jp/yaneurao/20090204