曲がった迷路その25 - 実装開始

一時はどうもいまいちなのでこのネタもフェイドアウトかなあ、と思ってたけどだいたい問題は片付いた。それほど難しい問題はなかった。ここまでくれば具体的に実装して考え方が正しいか確かめる段階に進められる。

実装

もちろん実装はObjective-C/Cocoaでやる。

名前を「Spaghetti Maze Creator」にした。「ぐちゃぐちゃ」「ぐにゃぐにゃ」したものの代表としてスパゲティの名前をいただいた。Objective-Cクラスの（名前空間代わりの）接頭辞は頭文字を取ってSMC。

主なクラス

単位壁

一つのbezier多項式で表される壁単位のインスタンス変数は

@interface SMCUnitWall : NSObject {
    SMCUnitWall *root;
    NSPoint     terminal;
    BOOL        needToSmooth;
    BOOL        isBranch;
    int         connecters;
    int         colorType;
}

イメージとしては図-30のような感じ。

terminalが壁の端点の一方の座標。rootは自分が繋がったもとの壁をさしている。connectersは自分に繋がっている（rootとしてさしている）壁単位の数を保持する。colorTypeは壁グループを表す変数でrootが持っている値を引き継ぐ。これを使って完成した迷路の壁を塗り分けようと思っているけど、ほんとうは壁すべてがこの値を持っている必要はない。 ほかの変数は名前の通り。

初期化は二通り。

- (id)initInField:(SMCWallField *)field withRoot:(SMCUnitWall *)rootWall;
- (id)initInField:(SMCWallField *)field withRoot:(SMCUnitWall *)rootWall terminalAt:(NSPoint)terminalPoint;

最初のはrootを指定してterminalの位置はポテンシャルと壁長さ分布に従って壁単位が勝手に決める。ふたつめはterminalの位置を指定する。

一つ目の引数のSMCWallFieldは壁全体を保持するクラス。

terminalFinder

単位壁を、端点の指定無しに作ったとき、端点を探すためのクラス。

@interface SMCTerminalFinder : NSObject {
    SMCSpecklePotential  *spot;
    NSPoint             anchor;
    float               dist;
    NSPoint             minimumPoint;
}
- (id)initWithPotential:(SMCSpecklePotential *)potential
            anchorPoint:(NSPoint)point
              andRadius:(float)radius;
- (NSPoint)minimumPoint;

スペックルポテンシャルと、rootの端点とレイリー分布から得られたroot端点からの距離をもらって初期化する。root端を中心にした円周上でポテンシャルの値が最小の位置をminimumPointメソッドで返す。探索は黄金分割法で行う。

wallField

SMCWallFieldのインスタンスは一つの迷路全体を表す。

@interface SMCWallField : NSObject {
    NSMutableArray              *walls;
    NSMutableArray              *terminals;
    SMCSpecklePotential         *spPot;
    SMCLayreighDistribution     *rand;
    SMCAntiCollisionPotential   *acPot;
    float                       collisionThreashold;
    float                       branchingProbability;
    int                         temporalColorType;
}

walls配列が壁単位を保持する。spPotはスペックルポテンシャル、randは壁長さ分布、acPotは衝突回避ポテンシャル、collisionThreasholdは衝突の閾値、branchingProbabilityは後で説明するけど名前の通り壁が分岐する確率である。

新しいSMCUnitWallのインスタンスを作るとき、必要なポテンシャルなどをこのSMCWallFieldに問い合わせて得るということにする。

branchingProbabilityは、新しい単位壁を作るときのrootとして、まだほかの壁に繋がっていないものから選べば分岐が起こらず、一つの曲線として伸びることになる。

最初はこれをwallsの中からisBranch変数がNOのものを選び出す、というやりかたで実装しようと思った。が、よく考えるまでもなく、これは非常に非効率的。

そこで新しい配列terminalsを作って、

1. 新しい単位壁を作ったらそれをterminalsに加える
2. そしてその単位壁がさしているrootがterminalsに含まれていたらそれを取り除く
3. terminalsの要素数が0以上ならそこから選べば分岐は起こらない

ということにした。冗長だけどこっちの方が速い。

branchingProbabilityはwallsから選ぶかterminalsから選ぶかの確率を指定する。wallsにはすべての単位壁が入っているのでそこから選べば常に分岐する、というわけではないけど、壁の数が増えればwallsの要素数に対するterminalsの要素数の比はどんどん小さくなる。

RandomDistribution

ちょっと大袈裟だけど乱数を発生させるクラスのインターフェイス。

@interface SMCRandomDistribution : NSObject
- (id)init;
- (id)initWithSeed:(unsigned int)seed;
- (int)intValue;
@end

@interface SMCUniformDistribution : SMCRandomDistribution
- (float)floatValue;
- (float)float2PiValue;
@end

@interface SMCLayreighDistribution : SMCUniformDistribution {
    float   sigma;
}

- (id)initWithSigma:(float)sigmaValue;
- (void)setSigmaValue:(float)sigmaValue;
- (float)sigmaValue;
@end

ひとつめはunixのrandom()関数を呼ぶだけのクラス、ふたつ目はそれから[0,1]区間の浮動小数点数を作る。みっつ目はレイリー分布の浮動小数点数を返す。ふたつ目みっつ目はそれぞれ内部でそのひとつ前を呼んでいる。

こんな重いものにする必要は全然ないだけど、まあとりあえず。

SpecklePotential

スペックルパターンのポテンシャルを保持するクラス。

@interface SMCSpecklePotential : NSObject {
    MCUniformDistribution   *uniform;
    SMCBiCubic              *bc;
    float                   cutOff;
    NSSize                  areaSize;
    float                   *potLattice;
}
- (id)initWithFieldExtent:(NSSize)fieldExtent andFietureSize:(float)featureSize;
- (float)potentialValueAt:(NSPoint)point;

potLatticeにfloatの2次元配列を持つ。init...で2次元配列の大きさと、featureSizeをもらってfloat配列を埋める。FFTの実装はFFTWライブラリを使う。NSPointで指定された位置の値をバイキュービック補間を使って返す。

BiCubic

バイキュービック補間を行うクラス。

@interface SMCBiCubic : NSObject {
    float       *floatMap;
    NSSize      areaSize;
    float       *coefarray;
    gradient    *gradarray;
    NSPoint     lastPoint;
    float       lastValue;
    gradient    lastGradient;
}
- (id)initWithFloatMap:(float *)map andSize:(NSSize)size;

補間すべきfloatの2次元配列を指定する。たくさんインスタンス変数を持っているけど、最初のふたつ以外は計算の中間結果保持のためのもの。

AntiCollisionPotential

壁衝突回避のポテンシャル。

@interface SMCAntiCollisionPotential : NSObject {
    float   height;
    float   radiusSquared;
}
- (id)initWithPeackHeight:(float)peakHeight andRadius:(float)radius;
- (float)potentialValueAt:(NSPoint)p;
- (void)addToPotential:(SMCSpecklePotential *)potential at:(NSPoint)point;

テント型の高さと範囲をもらって初期化する。NSPointで指定された位置の値を返すのと、自分をSpecklePotentialへ指定された位置に足す、ということをやる。

iterationTerminator

迷路完成の判断をする。

@interface SMCIterationTerminator : NSObject {
    SMCWallField    *field;
    float           qvalueRatio;
    int             qvalueBase;
    int             failures;
    NSMutableArray  *candidates;
    float           maxNumberOfCand;
}

- (id)initWithField:(SMCWallField *)wallField;
- (BOOL)doIterate;

doIterateメソッドでひとつの新しい単位壁を追加する。rootになる壁をランダムに選んでそこに追加することを試す。まわりのポテンシャルの値が大きいと失敗するので、root壁を選び直す。失敗が多くなってqValueRatioに比例した回数を超えると、アルゴリズムを切り替えてスペックルポテンシャルを走査して低いところを探索する。その位置をcandidates配列に保持する。candidates配列からランダムにひとつ取り出してそれに一番近い壁をrootにして新しい壁を追加しようとする。candidatesがカラになるか、やはり失敗回数がある回数を超えるとdoIerateはNOを返して、終わる。

いっきにおおまかな実装をすませてしまったが、それほど難しいところはないので、あとはディテールを詰めて問題が出たら修正、ということにしよう。