NSSetとライフゲーム（その2）

こないだの続き。

Conwayのライフゲーム（Conway's Game of Life）（wikipedia)は僕の大学の頃流行ったが、当時はパソコンなどなく、実際にプログラムすることは少なかった。剛の者のある友人は5mm方眼のノートに鉛筆で丸を入れてFペントミノ（Rペントミノと言う人もいる）の世代交替を1ページ1世代ずつ描いて追っていた。「途中で間違ってたらどないしょ」と言いながらノート1冊を使い切って２冊目に突入してしまってからはさすがに挫けていた。

会社に入ってVAX/VMS（みんな知らんだろうなあ）に繋がったVT220（もっと知らんだろうなあ）ターミナルのReGIS（うわー懐かし）というグラフィクス命令を使って書いてみたことがあるが、せいぜい40x30ぐらいの範囲しか表示できなかった。ReGISはとてつもなく面倒なエスケープシークェンスを使う命令だったが、ホットキーひとつで画面がオレンジ色の文字が並ぶキャラクタ端末と切り替わる。使い道はわかるよね。会社のVAXを使ってこんなことをしていたというのはもう時効だよな。

普通に書いたらまずセル領域の大きさを決めて、2次元配列を用意して、セルの世代交替をプログラムして、それを表示して、となるが、それでは最終的にどこまで広がるかを予測してそれに十分な領域を取らないといけない。

剛の者の友人と同じようにFペントミノの最後を見たいと思っていたが、大きな領域に広がるのでなかなか果たせなかった。
どうせひとつのパターンを追うだけなら領域はスパースだろうということで今回、領域面積を気にせず追える実装にしよう、そのためには領域全部を持つのではなく生きているセルだけを保持することにしよう、それには前回のメモのNSSetを使えば簡単になる、と考えた。

生きたセルを表すクラスGoLAliveCellを作る。GoLAliveCellのインスタンスは自分のいる座標と、何世代生き残っているか、という値を保持する。これをNSMutableSetに入れて、生きているセルの集合とする。この集合に含まれていないセルは死んでいるものと見なす。こうすればスパースな広い空間全部の状態を保持する必要がなくなる。

ここでコンテナに（NSArrayでなく）NSSetを使うことがキモ。こういう形式でセルを表すと同じ場所にあるセル（同じ座標値を持っているセル）が2個以上ないことを保証する必要がある。前回言ったようにNSSetは要素の重複を許さない。重複しているかどうかはNSSetが要素に対してisEqual:メソッドを投げることで確認する。従って要素になるオブジェクトにisEqual:メソッドを実装しておけば重複が無いことをNSSetが保証してくれる。isEqual:はNSObjectで定義がありポインタの値が同じ場合だけYESを返すので、これを書き換えて座標が同じ場合にYESを返すようにすれば良い。

さてinterfaceの登場と思ったがその前にちょっと準備。

2次元の座標はNSPointを使えばいいと思ったが、NSPointはOSの描画システムと結びついて座標をfloatで表現している。これは描画対象がスクリーン以外のもっと解像度の高いデバイスも含めた抽象化がされていることを直接反映している。スクリーンだけを考えるとオーバーヘッドが大きいように思うけど全く同じNSViewへの全く同じ描画がスクリーンにもプリンタにも使えるのは手間が省けてよろしい。

最初は、NSPointを使った方があとあと便利なのではないかと思って書いて行って、最後まで書き終わってしまってから特に恩恵に預かれないことに気がついた（遅い）。やっぱり目標にとって自然なintを使うことに変更した。intを使って2次元座標を表すのはFrameworkにそなわってないので作ることにする。といってもたいしたものではない。

2次元の座標をNSPointのまねをして

typedef struct GoLPoint {
	int	x;
	int	y;
} GoLPoint;

とする。頭の「GoL」は「Game of Life」のつもり。他の部分はNS云々とできるだけ同じにしておいた方が覚えやすい。

残りもまねをして

const GoLPoint	GoLZeroPoint;
BOOL		GoLEqualPoints(GoLPoint a, GoLPoint b);
GoLPoint	GoLMakePoint(int px, int py);

などを作っておく。

ついでにNSValueでオブジェクト化できるように

@interface NSValue (GoLPoint)
+ (NSValue *)valueWithGoLPoint:(GoLPoint)point;
- (GoLPoint)golPointValue;
@end

と言うようにカテゴリで拡張しておく。NSValueは簡単にCの構造体をオブジェクトにしてNSArrayなどの要素とすることができる。NSSizeやNSPointのオブジェクト化もはじめからNSValueに備わった形で実装されている。
ちなみにNSValueの実装は

@implementation NSValue (GoLPoint)
+ (NSValue *)valueWithGoLPoint:(GoLPoint)point
{
	NSValue *value = [NSValue value:&point
			withObjCType:@encode(GoLPoint)];
	return value;
}

- (GoLPoint)golPointValue
{
	GoLPoint	point;
	[self getValue:&point];
	return point;
}
@end

と、たったこんだけである。@encode()は構造体の定義を文字列の形で表したもので詳細はreferenceにあるが、この詳細を知る必要は無い。

また長くなってしまったので続きはまたこんど。