NSSetとライフゲーム（その7、XLifeデータの読み込み）

ライフゲーム、今更の内容だけど続いてるでぇ。
今日は初期データの読み込みについて。特に「なんちゃってクラスクラスタ」の実装のこと。

さて、ライフゲームには初期データを与えなければいけない。そのための専用エディタを備えるのがスジだとは思うが、それは大変。今回の目的（NSSetの特徴を生かしてFペントミノの最後を見届ける）のためにそこまでする必要は無い。そこで巷にころがるデータファイルを読み込めるようにしよう。そうすれば人の書いてくれたエディタが使えるし、テキストエディタでもいいし。

ということでまず、超有名なXlife（どこがオリジナルかよくわからないけどたとえばここ）のデータを読み込めるようにする。Xlifeはちょっと古いけどX-windowで動くライフゲームで、エディタを含めた必要な機能がすべて揃った上にConwayのオリジナルの遷移規則以外も定義できたり、今回やってるのと同じような実質的に無限の広さをもつ領域を扱える。Xlifeも同じような考え方（生きてるセルだけ保持する方法）で作られていると思われるが、ソースを見ても良くわからない。なにせCでX-WindowなのでObjective-CとCocoa frameworkに比べたらずっとたくさんのコードが書き連ねられている。ソースを開くと白いけどね。

Xlifeの*.lファイルは

続きを読む

NSSetとライフゲーム（その6、NSImageなど）

何回か前に出たGoLSparseGameOfLifeWithImageのimageメソッドについて。このメソッドでは生きたセルの位置のドットに色を付けたNSImageを返す。

NSImageは実際の中身、例えばビットマップだったりBezierパスだったりするのを一手に引き受ける。そのため中身はNSImageRepという別のクラスに持たせる。NSImageはNSImageRepのインスタンスを複数持てる。いろんな形式の表現が保持できるようになっている。
今回はセル一つが1ピクセルになるようなビットマップを作ってNSImageに持たせることにした。ビットマップはNSImageRepのさらにサブクラスのNSBitmapImageRepというクラスがあるのでそれを使う。

NSImageには表示されるときの大きさに関する

- (id)initWithSize:(NSSize)aSize;
- (void)setSize:(NSSize)aSize;
- (NSSize)size;

がある。ここでのsizeは中身とは独立に設定できる。つまり持っているビットマップのピクセルサイズとは無関係な値にすることができる。NSImageRepには

- (int)pixelsHigh;
- (int)pixelsWide;

というメソッドがあって、ピクセルサイズを表す。NSImageのサイズとピクセルサイズが違っている場合、表示のときには補間されるようである。インスタンス変数のenlargeRatioはこの機能を使って1セル1ピクセルを拡大表示するようにした。ピクセルの位置によってアンチエイリアスのかかり方が違ったりするが、自分で書くと大変なのでこれでいいでしょう。

続きを読む

NSSetとライフゲーム（その5、NSColor）

ライフゲームの続きで、専用カラーテーブルの話。

カラーテーブルは人の作ってくれたのを流用できるようにしようと思ったが、きれいなグラデーションに限ってファイルに書き出せなかったりしたので、結局あきらめて自分で作れるようにした。いいものはなかなか只では手に入らないと言うことか。gnuよ、反論しない？

さて、それでは適当に作りますか。前回にちょっとだけ出たGoLColorTableは

@interface GoLColorTable : NSObject {
    NSMutableArray  *colorTable;
}
+ (NSArray *)supportedFileTypes;

- (NSColor *)colorAtIndex:(int)index;
- (int)numberOfColors;
- (BOOL)load:(NSString *)fileName;
- (void)save:(NSString *)fileName;
- (NSMutableArray *)colorTable;
...

としよう。インスタンス変数のcolorTableと言う配列はNSColorインスタンスを保持する。プロパティリストの形式でファイルを読み書きするようにしたい。

続きを読む

NSSetとライフゲーム（その4、セルの保持）

ライフゲームの続き。

前回作ったGoLAliveCellを生きているセルとして保持するNSSetを持っているクラスをGoLSparseGameOfLifeとする。ヘッダの最初は

@interface GoLSparseGameOfLife : NSObject {
    NSMutableSet    *aliveCells;
    int             generation;
}
- (id)initCells:(NSArray *)pointArray;
- (int)generation;
- (int)numberOfServives;

- (BOOL)evolve;
...

みたいな感じ。セルを保持するNSMutableSetと世代数をインスタンス変数に持つ。

初期化は座標値GoLPointをNSValueに入れたNSArrayであるpointArrayを貰ってその位置のセルを生成してSetに詰める。numberOfServivesと言うメソッドは名前の通りでSetの要素数を返すだけである。

evloveメソッドが動作の中心となる。これが呼ばれるとひと世代進めたセルに中身を書き換えてgeneration変数を一つインクリメントする。次の世代が生成できたときevolveメソッドがYESを返す。次の世代が生成できなかったときNOを返すが、今回の実装ではこれはセルが全部死に絶えるか変化が無いときだけである。本当なら準定常状態でもNOを返すべきだろうけどチェックが難しい。

続きを読む

NSSetとライフゲーム（その3、ハッシュ）

さらにこないだの続き。

前回の下準備をして、生きたセルを表すGoLAliveCellを

#import "GoLPoint.h"

@interface GoLAliveCell : NSObject {
    GoLPoint        pos;
    int             age;
    unsigned int    hash;
}
- (id)initAt:(GoLPoint)position;
...

としよう。GoLAliveCellはその位置と何世代生き残っているかをインスタンス変数に持つ。位置は生まれたときに決まり、その後動かないとする。hashについては後でまとめて説明する。こうしておけばセルの領域は2^32x2^32（32ビットアーキテクチャで）の広さとなる。はじっこがどうなるかは命令セットの詳細やコンパイラに依存するが普通、整数演算の桁溢れは無視するので、上の実装で端の処理に特別なことをしなければ領域はトーラスになる。

GoLAliveCellには周囲との関係を表す

続きを読む

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を使えば簡単になる、と考えた。

続きを読む

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

MacOSXのFoundation frameworkにはNSSetというクラスがあって、これがまた面白かったのでメモを残しておく。

NSSet（とNSMutableSet、NSCountedSet）は数学の集合の概念を実装したもので、実際に集合演算に対応するメソッドが含まれている。JavaにもSetというクラスがあるが、これとほぼ同じもの（パクリらしいけど）。

NSSetのメソッドのうち

unionSet:（NSMutableSet）合併集合をとる
minusSet:（NSMutableSet）差集合をとる
intersectSet:（NSMutableSet）共通集合をとる
anyObject（NSSet）集合が空でないかどうか調べる
isSubsetOfSet:（NSSet）部分集合であるかどうか調べる
isEqualToSet:（NSSet）集合として同一かどうか調べる
member:（NSSet）要素に含んでいるかどうか調べる
set（NSSet）空集合を返す
count（NSSet）要素の数を返す

などは集合演算そのまんま。
要素にNSSetを含めることもできるから、集合の集合、なども表せる。
NSArray（配列）と違うところはNSSetの要素には「順番に意味が無い」ことと「重複が無い」ということがポイント。

ある要素が含まれているかどうかを調べるときNSSetとNSArrayでは探し方が違うのでスピードが違う、とreferenceに書いてある。

NSSetでは要素の重複はないが、重複を許す場合NSCountedSetを使う。これはNSMutableSetを継承しているのではじめからMutableである。countForObject:である要素がいくつ含まれているかを調べることができる。NSCountedSetはいわゆるbagである、とreferenceに書いてある。ナップサック問題（Wikipedia）の実装にはNSCountedSetが使えるよ、ということ。

こんなの僕の若い頃には無かった。20年前のコレクションクラスといえば配列、それと2次元配列...以上、だった。今の若い人はいいねえ、こんな面白いおもちゃがあって。

これを使って、最短ではないが最も簡単でかつ特徴ある実装を目指してConwayのライフゲームの実装をしてみよう、と思う。
字ばっかりなので続きはまたこんど。