シードフィルアルゴリズムでナビグラフのデータをつくる（その３）

前回の続きです。<a href="http://kondroid.hatenablog.com/entry/2015/04/08/011750">シードフィルアルゴリズムでナビグラフのデータをつくる（その２） - 無理な更新はお止めください。</a>kondroid.hatenablog.com

ようやくソースコードを見ていきます。早速始めましょう。
ソースコードはこちら。
https://github.com/kondroid00/MapEditorSample

いきなりですが核心部分です。

void MapGraphGenerator::createGraph(const Vec2 &seed,
                                    float nodeDistance)
{
    //ノード間の距離を指定
    m_NodeDistance = nodeDistance;
    
    //セルの作成してシードのセルを返す
    auto pSeedCell = createMapCells(seed);
    
    //シードセルに探索済みチェックを入れる
    pSeedCell->check();
    
    //Wall上にあるセル全てに探索済みチェックを入れる（無効化）
    checkCellOnWalls();
    
    //シードフィルアルゴリズムでセルを有効化する
    calculate(pSeedCell);
    
    //有効なセルに番号を打つ
    setMapCellsNum();
    
    //ノードとエッジを作成
    createNodeAndEdge();
}

MapGraphGeneratorというクラスがあり、その中のこのcreateGraphという関数が今回の肝です。引数にはシードの位置とノード間の距離を指定しています。m_NodeDistanceでMapGeneratorはノード間の距離をメンバ変数に持ちます。MES_Mapというクラスがあり（MESはプロジェクト名MapEditorSampleの略）、こいつのインスタンスがあらかじめ壁の情報をResources/Map/wall.mapから読み込ん（MES_Map::loadWallFile）でメンバ変数として持っており、MapGraphGeneratorはそれをコンストラクタで受け取って参照を持っておくことにしています。ちなみにMES_Mapはノードとエッジもメンバ変数（コンテナ）として持っており、それらもMapGraphGeneratorが参照を保持しています。そしてノードとエッジができたらMapGraphGeneratorが直接参照を使って情報を書き込むようにしています。とりあえずソースコードはこんな感じ。

class MES_Map
{
private:
    
    std::vector<Wall*> m_Walls;   
    std::vector<NavGraphNode<> > m_Nodes;
    std::vector<NavGraphEdge> m_Edges;
    ....
 
public:
    ....

    void loadWallFile(const std::string &wallFullPath,
                      float offsetX,
                      float offsetY);
    
    const std::vector<Wall*>& getWalls()const{return m_Walls;}
    std::vector<NavGraphNode<> >& getNodes(){return m_Nodes;}
    std::vector<NavGraphEdge>& getEdges(){return m_Edges;}
    ....

};

class MapGraphGenerator
{
    ....

private:
    
    const std::vector<Wall*> &m_Walls;    
    std::vector<NavGraphNode<> > &m_Nodes;
    std::vector<NavGraphEdge> &m_Edges;

    float m_NodeDistance;
    ....  

public:
    
    MapGraphGenerator(const std::vector<Wall*> &walls,
                      std::vector<NavGraphNode<> > &nodes,
                      std::vector<NavGraphEdge> &edges)
    :m_Walls(walls)
    ,m_Nodes(nodes)
    ,m_Edges(edges)
    {}
    ....

}

その２の③で画面いっぱいにノードが作られたと思うんですが、あれは最終形態ではなく一時的なノードです。最終形態は⑦で見たようなノードです。ここでこの一時的なノードをMapCellという構造体で表します。MapGraphGeneratorの内部ではこのMapCellを使って計算を行います。流れとしては

MES_Mapが壁の参照を渡し、ついでに空のノードとエッジの参照を渡す。
MapGraphGeneratorがMapCellを使って内部で計算をし、ノードとエッジにデータを入れる。
MES_Mapのノードとエッジにデータが反映される。

という流れです。ではMapCellを見てみましょう。

struct MapCell
{
    int num;
    cocos2d::Vec2 position;
    int x, y;
    
    //探索済みならtrue
    bool checked;

    //有効なセルならtrue
    bool affective;

public:
    
    MapCell(const cocos2d::Vec2 &position,
            int x,
            int y)
    :num(0)
    ,position(position)
    ,x(x)
    ,y(y)
    ,checked(false)
    ,affective(false)
    {}
    ....

};

MapCellのnumはただの通し番号です。ただ、その２の⑤の状態になってから初めて番号が与えられます。positionは位置です。xとyは左下をとした際の行と列の番号です。例えばその２の③のシード（赤い点）だとx＝３、y＝３になります。checkedはその２の④の過程で使います。④の一番上の赤い点は上下左右を探索しすべてOKだとわかりました。その後、今度は赤い点の右にあるMapCellが上下左右の探索を始めます。この時左側の赤い点はすでにOKだとわかりきっています。ゆえに調べることはしません。すでに探索済みのMapCellはcheckedをtrueにします。最後affectiveです。これはそのままMapCellが有効ならtrueにします。その２の④では一番上の４つの黒い点はtrueですが、下の二つの黒い点はfalseです。

..........うーん、長い。
ですから、ここからは巻きでいきます。これ以降についてはソースコード内にコメントを書いておきましたのでそちらを読んでみてください。MapGraphGenerator::createGraph内の以下の４つの関数

createMapCells
checkCellOnWalls
caluculate
createNodeAndEdge

について軽く説明しておわりにします。

１． createMapCells
その２の③のぽつぽつを作ります。ぽつぽつはMapCellのオブジェクトになってMapGraphGeneratorのメンバ変数m_MapCellsにポインタが格納されます。戻り値はシードのMapCellオブジェクトのポインタです。引数が位置だったのでオブジェクトのポインタになって戻ってきたってことですね。

２．checkCellOnWalls
これが必要だと気づくのに時間がかかったんですよ。壁の上にあるMapCellどもをaffective＝falseのままチェック済み（checked＝true）にしちゃいます。これがないとその２の⑤で壁を通り抜けちゃいます。おそらく次のcaluculateの実装にもよると思うんですが、とにかく今回は必要なんです。で、問題はどうやって線分で表現される壁のうえに点で表現されるMapCellが乗っかっちゃってるかを調べるかなんですが、線分と点の距離を求めて、その距離が結構小さい（今回は1e-12）ければ乗っちゃってるってことにしてます。floatを使う以上誤差が出ちゃうから決して==で判定してはいけません。ソースみてね。（追記）floatなのでこれじゃ精度がまずいですね。他にも色々問題があるので少し考えます。
３．caluculate
シードフィルアルゴリズムそのものの実装で今回の目玉です。まず引数は起点となるMapCellのポインタです。って言われてもピンとこないでしょうから、その２の③のシード（赤い点）を引数に入れてみましょう。その２の③ではシードの上下左右は間に壁もなく近くに壁もないので４つともすべて有効（MapCell : affective == true）です。有効だったらどうするか。今度はその４つのMapCellを起点にして同じことを繰り返せばいいのです。そこでこの関数のしょっぱなにcontainerを用意してその中にこの４つのMapCellのポインタを打ち込みます。そしてこの関数の最後でcontainerから値を取り出して、そいつを起点にまた自分自身caluculateを呼び出しています。いわゆる再帰呼び出しというものです。ここで呼び出されたcaluculateはまた内部でcaluculateを呼び出し、またそのなかでcaluculateを呼び出しと延々と続いていきます。じゃあいつこの関数は止まるのか。containerの中身がなくなった時すなわち、すべてのMapCellが探索済み（checked == true）になった時です。このcheckedがなければ無限ループになると思います（試してないけど...）。この関数が終了すればMapCellのaffectiveがtrueとfalseのふた組のMapCellどもに分かれ、affective == trueのMapCellどもがその２の⑤のポツポツがになります。

４．createNodeAndEdge
これでラストです。ﾊｧﾊｧ。片っ端からMapCellを調べて行って有効（affective == true）なら処理をします。どういう処理かって？その２の⑥をごらんください。サンプルコードはネストがひどくて見る気が失せそうですが、その２の⑥をやってることは確かです。さらにこの関数の内部でノードとエッジを作成し、MapGraphGeneratorのメンバ変数（コンテナ）m_Nodesとm_Edgesにそれぞれ格納しています。二つはMES_Mapのノードとエッジのコンテナの参照なので、この関数を抜ければMES_Mapはノードとエッジの完成品を持ってることになります。

これで解説は終わりです。素直に疲れました。
ついでにアニメーションの方も軽く解説しておきます。まずアニメーション用なのでMES_Mapにノードとエッジを作って返していません（笑）。caluculateのところがcreateNodeCycleOnceになってupdateで呼ばれています。次に探索するMapCellをMapGraphGeneratorのメンバ変数のキュー（m_CellsQueue）に格納し、そこから起点を取り出す仕組みです。また有効化されたMapCellはMapGraphGeneratorのメンバ変数のコンテナ（m_AffectiveCells）に格納されます。m_AffectiveCellsはまずシードから格納されていきます。MapCellも自分の八方向にあるMapCellのポインタを保持しています（m_CellList）。これはエッジを描く時に必要です。次にcreateEdgeCycleOnceでエッジを描いていきます。これは簡単で、m_AffectiveCellsから一つづつMapCellを取り出し、そのMapCellが保持しているm_CellListから取り出したMapCellとでその２の⑥を調べ、OKならエッジを描画するだけです。m_AffectiveCellsはシードから格納されているのでシードからエッジが広がるように見せることができます。

さらに疲れました。とりあえずソースコード見てみてください。
以上です。

新作アプリ作りました↓↓<a href="http://kondroid.hatenablog.com/entry/2015/05/08/184904">新作アプリ「イカタコ戦争」をリリースしました！！ - 無理な更新はお止めください。</a>kondroid.hatenablog.com