せっかく書いたのに消すのももったいないので残すことにするが、内容も結論もなんともつまらないし、誤りも多々含まれていると思われるので、何言ってんだこいつと思いながら読んだほうがいい。
また、後日記事の内容が変わる可能性もある。
■ タスクシステム
昔、C/C++とDirect Xをひと通り覚えて何かゲームでも作ってみるかと思った時、『弾幕 最強のシューティングゲームを作る！』(松浦健一郎・司ゆき, 2009)という本を購入してSTGゲームの作り方を学んだ。
この本の想定読者層は、まさに当時の私のようなC/C++プログラミングが書けるゲームプログラミング初心者を想定しているようで、ゲームプログラミングの入門書として大変参考になった。（ただし、この本ではSTGゲーム部分のみを扱っているため、この本だけでゲーム単品を作るのは難しいとも思う。）
そして、この本で私はタスクシステムを知った。
タスクシステムについての説明は偉大な先人方を参照されたい。次のサイトには大変お世話になった。
タスクシステムの解説は次のサイトが大変実用的にまとめている。
タスクシステム解説 - Ideals and Reality http://d.hatena.ne.jp/alwei/20110117/1295290033
実際の簡単な実装と運用は、次のサイトがわかり易く解説している。
TNKソフトウェア - 11:タスク処理を実装する http://www.tnksoft.com/reading/classgame/engine/01/011.php
また、実用的なタスクシステムの実装には次のサイトが役に立つかもしれない。
近代的タスクシステムの構築 http://d.hatena.ne.jp/yaneurao/20090203
■ メモリ確保済みタスクシステム
昔はいさ知らず、現代のC/C++ではその利便性からSTLでタスクシステムを実装することが多いと思う。特にPCゲームでは、メモリや速度などの面を見ても何ら問題は無いだろう。
しかし、本で紹介されていたタスクシステムは少し変わった実装をしていた。
タスクの最大サイズと最大数を指定して、その分のメモリを予め確保するというものだ。
著書の文中では単にタスクシステムとしか書いてなかったため、これを勝手に「メモリ確保済みタスクシステム（MATS: Memory Allocated Task System）」と呼ぶ。
MATSは、内部でアクティブリストとフリーリストの２つのリストを持ち、初期化した時にはフリーリストに全てのタスク（の入れ物）を保持しておく。
タスクを追加する際は、フリーリストからタスクの入れ物を取り出してその中にタスクを格納し、アクティブリストに加える(fig.1)。
格納したタスクを得るときは、アクティブリストの要素を順に返すというわけだ。
タスクを削除するときはアクティブリストからフリーリストへタスクを戻す。
fig.1 メモリ確保済みタスクシステムへのオブジェクト(TaskA)の格納
さて、実際のゲームではタスククラスから派生させた様々なオブジェクトをタスクリストに格納する。当然、オブジェクトのサイズにばらつきが出てくる。このタスクリストでは、格納するオブジェクトのサイズのうち最も大きなサイズをタスクのサイズとしているため、それ以外のサイズのオブジェクトをタスク内に格納するとその差分の無駄メモリが生じる。これが数百個ともなれば大きなサイズの無駄メモリが生じる。なぜ、一番大きなサイズに合わせてメモリを確保するのだろうか。
それは本の内容と関係がある。
STG（特に弾幕系と呼ばれるもの）では弾を秒間何百回と生成、削除する場面がありうる。もし弾をstd::listなどで管理していた場合、生成、削除が繰り返されるうちにどんどんメモリが分断されてメモリ枯渇が起こる可能性がある。そのため、タスクシステムにデフラグの機能が必要な場合がある。（もっとも、2Dゲームでは現代のPCでメモリが枯渇するような場面はまず無いように思う。）
一方、予めメモリを確保するこのタスクシステムではメモリ分断の恐れは無い。幾らタスクを生成、削除しても、予め確保した分のメモリしか使わない。デフラグも不要だ。
このような立場からみると、一見無駄が多いように見えるこのMATSは実はなかなかスマートな実装だといえる。
ただし、このMATSを実際に運用するには課題も多い。
基本的に特定のタスクを探し出すには線型探索となり、スマートポインタも使えない。そして当然、使い方を誤れば必要以上にメモリを食い潰してしまう。
利用方法は限定されるが、しかし運用方法でカバーできる部分も多く、有用な場面はあると思う。
■ 書籍のMATSの厳しすぎる制約
ここからが私が記録に残したかったことである。
つい先ほど有用な場面はあると書いたばかりだが、この本で実装されたMATSはそのまま実用できるような代物ではない。
それについて記すために、まず著書でどのように実装されているかを説明する必要がある。
本では、タスクとリストを次のように定義している。（この記事の説明に必要な部分だけ記した）
class Task
{
private:
Task *Prev, Next;
// デフォルトのnew/delete演算子を無効
void* operator new(size_t t) {}
void operator delete(void* p) {}
public:
Task(TaskList* list);
virtual ~Task();
};
class TaskList
{
private:
// タスクリストが使う全メモリ領域
char* Buffer;
// タスクの最大サイズと最大数
size_t TaskSize;
size_t TaskCount;
Task* ActiceTask;
Task* FreeTask;
public:
TaskList(size_t size, size_t count);
~TaskList();
void* New(size_t size);
void Delete(void* p);
};
そしてこれらの主な実装は次のようになっている。
Task::Task(MallocedTaskList* list)
{
Prev = list->ActiveTask->Prev;
Next = list->ActiveTask;
Prev->Next = Next->Prev = this;
}
Task::~Task()
{
Prev->Next = Next;
Next->Prev = Prev;
}
void* TaskList::New(size_t size)
{
assert(size <= TaskSize);
if(FreeTask->Next == FreeTask)
{
return NULL;
}
Task* task = FreeTask->Next;
FreeTask->Next = task->Next;
return task;
}
void TaskList::Delete(void* p)
{
Task* task = (Task*)p;
assert(task->Prev != NULL);
task->Prev = NULL;
task->Next = FreeTask->Next;
FreeTask->Next = task;
}
注目すべきはタスクのコンストラクタ・デストラクタとタスクリストのNew・Delete関数である。
タスクを追加するとき、まずタスクリストのNew関数を呼び出しフリーリストからタスクをもらう。
そのタスクの領域にてタスクのコンストラクタを呼び出し、タスクをタスクリストのアクティブリストに追加する。タスクを削除するときはこれを逆順で行う。
しかし、この一連の手順は上記の実装では実現できない。タスクリストのNew関数で貰ったタスク領域にてタスクのコンストラクタを呼び出す手続きが実装されていないためだ。
そして著書では、さらに次のように実装を行った。
// グローバル変数
TaskList* MoverList;
class Mover : public Task
{
public:
void* operator new(size_t n)
{
return MoverList->New(n);
}
void operator delete(void* p)
{
MoverList->Delete(p);
}
Mover();
};
まさかの実体参照である。
確かにこれで一連の手順は実装された。次のようにしてタスクリストへ追加・削除することができる。
Mover* mover = new Mover(); delete mover;
しかしその結果、タスクは決められたタスクリストに強制的に格納される。タスクリストもグローバル変数として管理するほかなく、生存範囲が広すぎて大変に手間がかかる。
予めプログラム全体のクラス設計がしっかり出来ていればともかく、世の中のプログラムは悉く途中で設計が変わる。そうしたプログラムを書きながらの設計では、このタスクシステムは実際に使うにはとても制限が厳しすぎる。
■ なぜこんなことになったのか
結論からいうと、New関数とタスクの生成を橋渡しするためには、通常のC/C++の文法ではこう記述するほかないからである。
New関数内部で一連の手続きを完結させることは難しい。
テンプレートを使えばタスクリストからタスクの実体である派生タスクのコンストラクタを呼ぶことができる。ただし、派生タスクのコンストラクタに渡したい引数の数、種類が常に同じとはならないだろう。すると、そのパターンの数だけ分岐やNew関数のオーバーライドが生じる。どんなマゾヒストでもこの分岐だらけのソースコードを管理したくはないだろう。
そもそも、これではポリモーフィズムが完全に失われている。タスクリストがタスクの実体を把握する必要はないし、そんな必要は無いほうがいい。
別の記述方法として、タスクのインスタンスをどこかで生成してからタスクリストへpushするといった方法もあるだろう。その場合、MATSは実体をリスト内のメモリに格納するため、pushする度にインスタンスをディープコピーする必要がある。
毎秒100個のインスタンスが生成・消滅するようなゲームでこのメモリコピーのオーバーヘッドがどれほど影響するかはわからない。また、リストに加えるためだけに同じインスタンスが2つ生成されるとなると、バグの温床になりかねない。
そして私がたどり着いた結論は、new演算子に引数としてタスクリストを渡す手法だ。
■ placement new のオーバーロード
placement new/delete（配置new/delete）は大抵の場合使わないほうが良いとされる。確かに周知された機能ではないだろうが、知っておいて損はないと思う。（New演算子 - Wikipedia）
今回注目すべきは、このplacement new をオーバーロードして利用する際、その引数は任意に取れる点である。
つまり、今回の場合はこのようにすれば上記の問題が解決する。
class Task
{
public:
void* operator new(size_t n, TaskList* list)
{
return list->New(n);
}
};
リストに対してタスクを追加するときは次のように記述する。
TaskList list(MAX_SIZE, MAX_COUNT); Task* task = new(&list) Task(&list);
これで任意のタスクリストにタスクを追加することができる。なんと簡単な方法だろう。（newとコンストラクタそれぞれに同じ引数を指定しなければいけないのが少し気持ち悪いが）
ただし、ここで更に問題が生じる。placement newを呼び出すことはできるが、placement deleteを呼び出す事はできない。すなわち、placement deleteを次のように定義してもこれは動作しない。
class Task
{
public:
void* operator delete(void* p, TaskList* list)
{
return list->Delete(p);
}
};
delete(&list) task; // 動作しない
解決方法としては、iteratorを作成してそこから list.erase(iterator) などとして操作するのがいいと思う。もちろん、これよりベターな方法はあると思う。
iteratorの実装については実装例を見てもらいたい。
この実装の問題点は、独自ルールすぎることである。
あまり認知度の高くないplacement newをさらにオーバーロードしてタスクリストを引数に取るようになっておりdelete演算子は使えないなど、書いた本人以外にだれがわかるものか。
結局、これを利用する機会はごく限られているだろう。
すなわち、生成・削除を大量に繰り返すタスク（とそれを管理するリスト）を一人で実装する場合である。
最後に、今回のMATSの実装例を載せておく。
MallocedTaskSystem
あの本を読んでプログラムを組もうとしてこのタスクシステムの制約に苦しんだ人がいれば、何かの参考になる可能性があるかもしれない。
まったく頭のなかの整理は追い付いていないが、とりあえず文章として残しておくのはここまで。
