SSブログ

NSSetとライフゲーム(その8、evolve) [プログラミング - NSSetとライフゲーム]

ライフゲームの続き。
だんだん記述が丁寧になって単なるメモにしては重くなってきた。

今回は世代交替のプログラミング。NSSetの集合演算のおかげで簡単になる話。やっとNSSetを使うメリットの核心。

世代交替にはGoLSparceGameOfLifeのevolveメソッドで行うことにする。evolveメソッドは

- (BOOL)evolve
{
    NSMutableSet    *nextGenerationCells = [[self servivingCells] retain]; // (1)
    NSSet           *vacants = [self findVacants]; // (2)

    [self appendNewBornTo:nextGenerationCells fromVacants:vacants]; // (3)
    if ([aliveCells isEqualToSet:nextGenerationCells]
                        || ([aliveCells count] == 0)) {
        [nextGenerationCells release];
        return NO;
    }
    [aliveCells release];
    aliveCells = nextGenerationCells;
    generation ++;
    return YES;
}


まず(1)で、次の世代に生き残るセルを選んでその集合を作る。
次に(2)で、vacantsと呼ぶ、現世代に死んでいるセルで次世代に生まれる可能性のあるセルの集合を作っておく。
(3)にvacantsの中から実際に生まれるものを選んで1行目で作った生き残りに加える。
その後で現世代をreleaseし、次世代を現世代にしてgenerationをひとつ進める。

それではその中身。

まず生き残りを選ぶservivingCells。

- (NSMutableSet *)servivingCells
{
    NSMutableSet    *newCells = [[NSMutableSet alloc]
                            initWithCapacity:[aliveCells count]]; // (1)
    NSEnumerator    *eenum = [aliveCells objectEnumerator]; // (2)
    id              cell;

    while ((cell = [eenum nextObject]) != nil) {
        int	nc = [cell countNeighbouringOf:aliveCells]; // (3)
        if ((nc >= serviveMinimumNeighbourCount)
                    && (nc <= serviveMaximumNeighbourCount)) {
            [cell setSurvive];
            [newCells addObject:cell];
        }
    }
    return [newCells autorelease];
}
空の新しいNSMutableSetを作っておき(1)、NSEnumeratorを使って(2)生きているセルを順に隣の数が生き残る範囲にあるか調べる(3)。生き残ることになったセルにsetServiveを送ってから新しいNSMutableSetに加える。全部確認が終わったら新しい集合の方にautoreleaseを送ってそれを返す。そのまんまですな。 vacantsの方は
- (NSSet *)findVacants
{
    NSAutoreleasePool   *pool = [[NSAutoreleasePool alloc] init];
    NSEnumerator        *cellEnum = [aliveCells objectEnumerator];
    NSMutableSet        *vacants = [[NSMutableSet alloc]
                                        initWithCapacity:[aliveCells count]];
    id                  cell;

    while ((cell = [cellEnum nextObject]) != nil)
        [vacants unionSet:[cell neighbours]]; // (1)
    [vacants minusSet:aliveCells]; // (2)
    [pool release]; 
    return [vacants autorelease];
}
同じようにNSEnumeratorを使って生きているセルを順に、それぞれのセルの隣のセルをすべてvacantsというNSMutableSetに加える。そのとき、(1)の箇所のようにunionSetメソッドを使う。これでvacantsの中のセルは重複が無くなる。全部追加し終わったら(2)で現世代の生きているセルの集合との差集合を取る。これでvacantsの要素はすべて現在は死んでいるセルだけになる。 最後にvacantsの中から生き残るものを選び出して新しい集合の方に加える。
- (void)appendNewBornTo:(NSMutableSet *)newCells fromVacants:(NSSet *)vacants
{
    NSEnumerator    *venum = [vacants objectEnumerator];
    id              cell;

    while ((cell = [venum nextObject]) != nil)
        if ([cell countNeighbouringOf:aliveCells] == neighbourCountForNewBorn)
        [newCells addObject: cell];
}
同じようにNSEnumeratorを使ってvacantsの方を順に調べている。 ちょっと考えればvacantsの集合と言うのは実は不要である。vacantsを作るときに一つずつ生き残る条件を満たしたものだけ集合に加えれば良い。 まあ、そうなんだけどこの方がわかりやすい。もちろん効率は落ちるが。効率に関しては最後に議論するつもり。
nice!(0)  コメント(0)  トラックバック(0) 

nice! 0

コメント 0

コメントを書く

お名前:
URL:
コメント:
画像認証:
下の画像に表示されている文字を入力してください。

トラックバック 0

この広告は前回の更新から一定期間経過したブログに表示されています。更新すると自動で解除されます。