「アルゴリズム＋データ構造＝プログラム」とは良く言ったもので、データ構造はプログラムのもうひとつの顔である。
むしろ、私としてはデータ構造はアルゴリズムに包括されるもの、というふうに捉えているが、まぁこの際、そんなことはどうでも良いだろう。
そしてゲームになくてはならないデータ構造のひとつとして、いちばんにリスト構造を挙げるのは、多くの方の賛同を得られるのではないだろうか(スタックも重要だが、ゲームになくてはならないというよりもプログラムになくてはならない存在なので割愛する)。
さて、リスト構造とはなにかというと、簡単にいえば構造体をポインタでもって数珠つなぎにするデータ構造のひとつである。
こいつの便利なところは、簡単にデータを挿入したり、削除したり、つなぎかたを変えたりできることで、特に高速性が重視されるプログラムにおいては、利用されることが多い方法である。
そしてこのリスト構造とオブジェクト・プール構造は、同じタイプの構造体を扱うという点で酷似しており、相性がいい(というより、オブジェクト・プールの前身であるストラクチャ・プールはリスト構造と組み合わせるために考えたものであるから当然だ)。
このリスト構造という奴をゲームではどういう場面に使うのかというと、たとえば弾の管理だとか、敵の出現・消滅だとか、爆発パターンの出現・消滅だとか、とにかく考えうる、ありとあらゆる用途があり、こいつを統一的に扱うことができれば、これほど便利なことはないだろう。
しかしながら、これを使っていると時々困った問題に遭遇することがあるのだ。
例えば敵キャラをリスト構造で扱う時、或るタイミングで敵キャラが死んだとする。この敵キャラクターを、いきなりリストから外してメモリから消去してしまって、果たしていいものだろうか？
普通に考えればそれでも問題ないのだが、問題が発生する場面も考えられる。
例えば、(HPがなくなるなどして)敵キャラが死亡したと判定した後、しばらくの間、爆発しながら墜落する敵キャラを表示したいとする。
このとき、敵キャラ・タスクのすることは、墜落することと自分自身を表示しつづけることくらいだ。
基本的にはこの敵キャラはリストから外してもあまり問題はないだろう。そしてリストから外した瞬間にメモリを解放するのが解りやすい。だが、そうすると、墜落しつつある敵キャラクターを表示してくれるのは誰か(どのオブジェクトか)という疑問が発生する。
オブジェクト指向の精神で行けば、やはり「自分のことは自分で」処理すべきで、敵キャラクターを表示するのはやはりその敵キャラ・タスクが行うのが望ましい。
リストから削除した瞬間にメモリから敵キャラのオブジェクトを消滅(プールに返還)してしまうと、これらの処理はできなくなる。ということは、必然的にリストに接続され、アクティブな(死んでない)敵キャラも、リストに接続されていない死亡直後の敵キャラも、場合によっては必要なだけ生き長らえる義務があるとも言える。
つまりリストに接続されているかどうかと、オブジェクトが存在するかどうかは、同期しないのだ。
とすれば、本当に死亡の演出が終わって、オブジェクトが成仏してもいい状態になったらメモリを単純に解放するのが理想的かもしれないし、事実そうだろう。
しかしそうすると、今度はまた別の困った問題が発生する可能性も否定できない。
それは、たとえば敵キャラクタを指揮する隠れタスク(この場合はプレイヤーに見えないという意味での「隠れタスク」)のようなものがあったとして、この隠れタスクは、いつ消滅したらいいのかという問題である。
自分の指揮下にあるキャラクタがすべて死亡するか作戦を遂行し終わるかしたら消滅しても良い、というのは簡単だが、たとえば(というかほとんどどの場合)このタスクが配下のキャラクタにメッセージ送信することで司令を下しているとしたら、配下のキャラクタが死亡した場合、誰が教えてくれるのだろうか。
まぁ事態はそれほど複雑ではないので、実はこんな問題は現実には発生しない。なぜならば現実のアクションゲームやシューティングゲームはもっと単純な(口の悪い人間に言わせれば「稚拙な」)手段でプログラムされているので、厳密なメッセージパッシングをしなくても、外部変数で処理することで逃げるのは簡単だからだ。
しかし、敢えてオブジェクト指向的なアプローチでゲームを作ろうとする国後計画では、この問題に対するなるたけエレガントな回答がとりあえず欲しい。それで作ってみて、ダメダメなもんなら、外部変数に逃げることはいつでもできるじゃないか。
メモリ上で必要なくなったオブジェクトをガベージと呼ぶ。
そして、必要なくなったオブジェクトを検知し、自動的にメモリから削除する機構、これをガベージ・コレクタという。ガベージを削除する行為はガベージ・コレクションだ。
本当のガベージ・コレクションは、特定のオブジェクトを指すポインタすべてを記録し、そのオブジェクトを指すポインタがなくなった瞬間にメモリ削除機構として働くのだが、このような仕組みは言語仕様に大きく依存する。本格的なものを作りたければ、ポインタを独自のクラスとして実装するくらいしかテはない。
テンプレートが存在する現在、そうしたポインタクラスを実装するのはそれほど難しいことではない。
が、ポインタがクラスになっているというのは、少し恐いので、とりあえず現実的な手段として、Windows95のCOMのように、参照カウンタを使った方法で実装してみた。
以下が、該当部分のリストである。
template<class T>
class KListElement : public KPoolElement{
// リスト構造付きプールオブジェクトクラステンプレート
protected:
T *prev,*next;
public:
KListElement(){
prev = next = NULL;
}
~KListElement(){
remove();
}
void addNext(T *e)
{
T *tmp;
tmp = next;
next = e;
e->next = tmp;
}
T *getNext(){
return next;
}
remove(){
if(prev)prev->next = next;
if(next)next->prev = prev;
}
};
template<class T>
class KListElementGC : public KPoolElement{
// ガベージ・コレクション＆リスト構造付き
// プールオブジェクトクラステンプレート
protected:
T *prev,*next;
int refCount; // 参照カウント
public:
KListElementGC(){
prev = next = NULL;
refCount = 1;
}
~KListElementGC(){
}
void addNext(T *e)
{
T *tmp;
tmp = next;
next = e;
e->next = tmp;
e->prev = (T*)this;
refCount++;
e->refCount++;
}
void addRef(){
refCount++;
}
T *getNext(){
next->refCount++;
return next;
}
void remove(){
if(prev){
prev->next = next;
refCount--;
prev->free();
}
if(next){
next->prev = prev;
refCount--;
next->free();
}
free();
}
void free(){
refCount--;
if(refCount == 0 )delete this;
}
};
// 利用例
class CListTest : public KListElementGC<CListTest>
{
public:
int fig;
};
このリストでは、二つのクラステンプレートと、ひとつの利用例を示している。
KListElementクラステンプレートは、普通の双方向リンクを実現するためのクラステンプレートであり、KListElementGCクラステンプレートは、その疑似ガベージ・コレクタ付きのものである。
KListElementのほうについては、特に説明はいらないだろう。ごく普通のクラス・テンプレートだ。
しかし、KListElementGCについては注意が必要である。
まず、これを使う時には、delete演算子ではなくてfreeメソッドを使うという点だ。これはできればdelete演算子のオーバーロードによって擬似的に解決したかったのだが、delete演算子では渡されるポインタの型が不定なため不可能だった。
また、このクラスには参照カウンタがあり、これは生成時に1となり、ポインタをコピーするメソッドを呼ぶ(getNextなど)ほど参照カウンタが増えていき、freeを呼ぶとそれらが1づつ減り、ゼロになった時点でメモリから解放されるという単純な仕組みである。
これを使う時の注意は、getNextなどでポインタを取得したらかならずfreeすることである(ちょうどDirectXのプログラミングに似ている)。
そうすることによって、適切な時期に確実にfreeすることができ、メモリの無駄を解消すると同時に安全性まで確保できる。
また、なんらかの関数に渡すような場合には必ずaddRefを行い、必要なくなったらfreeするという操作が必要だ。
ここまで引っ張っといて無責任だけど、果たしてこれ、便利なのかねぇ？
STLの世界にはどうやら「ポインタクラス」という概念があるらしいから、ガベージコレクションを自動的にやるなんてのは常識なのかな(ポインタクラスをポインタのかわりに使い、コンストラクタ、デストラクタ、=演算子オーバーロードなどで参照カウントを制御すればほぼ完璧なガベージコレクタが作れると思う)。
わからん。
なんにせよ、STLはまだ資料不足なのでねぇ。
Direct3Dの時みたいに、英語文献がスラスラよめるほどそっちの方言には慣れてないし。とりあえずポインタクラスみたいなのを実際に作ってみるとするか。
ところでSTLのソースってもうそれ自身STLを使いまくってるから、門外漢のおれには理解不能。まぁイテレータまでテンプレートにしちゃうんだから、ポインタがクラステンプレートなんてのは当然かもね。いや、いいわけのつもりはないですが。
それで、このポインタクラスは、ご覧のような使い方をする程度であればたぶん実用に耐えると思ふ。
しかし実際にこのポインタクラスを使うことによるオーバーヘッドが、果たしてどのようなものになるかはまだわからない。
当然、実用に耐えるか否かはベンチマークに依存するわけだが、その話はまた次の機会にということで。
ところで国後って開発コード名を北方領土から取っているのはヤバいんではないかとの指摘がありました。
う、確かにそうかも。近いうちに名前を変えましょう。どうせコード名だしね。
それでわ。
|
|
|