シードフィルアルゴリズムでナビグラフのデータをつくる（その２）
前回の続きです。
前回はアプリでシードフィルアルゴリズムの動きを見ていきましたが、今回はソースコードに触れていきます。ただし、今回はアプリでみたプログラムのソースコードには触れません！えっ、なんでと思うかもしれませんが、アプリのプログラムはナビグラフが出来上がっていく様子をアニメーションで見せるための実装になっています。最初はシードを設定したらすぐにバンってナビグラフが出来上がったものが出てくるようにしてたのですが、面白くないのでアニメーションっぽくしてみました。実用レベルではわざわざアニメーションにする理由はないですし、アニメーションにしないほうがわかりやすいので、今回はシードを設定したらいきなりバンってナビグラフが出来上がったものが出てくるやつを見ていきます。
とりあえず大雑把に理解する
いきなりですが図解です。
これで終わりです。アプリの動きをみると一見難しそうですが、やってることは極めて単純です。
①シードの設置
まずはシードを設置します。このシードの位置がおかしいと変なことになります。例えばアプリで壁の外をタップしてみると、壁の外にナビグラフが出来上がります。また、ノードは壁からある一定距離のところじゃないと生成されないのですが、シードは壁から近くても置けてしまいます。そうすると太った人がこのシードにやってくるとお腹が壁にあたってしまいますね。正しい位置にシードを設置する必要があります。
②画面の分割
次に指定したノードの間隔で画面を縦横分割します。画面の縦横の分割線の交点にシードがあるようにします。これはシードを基準として上下左右方向にノード間の距離を取っていくことで対処できます。
③画面をノードで埋め尽くす
②でできた縦横の分割線の交点上にノードを作成します。
④あるノードを基準として上下左右のノードをチェック
まずは③でシードの上下左右を見てみましょう。シードと上下左右のノードの間には壁はありません。シードの上下左右のノードは有効です。次にシードの一つ下のノードを見てみましょう。こちらは上下と右のノードは問題ありませんが、左のノードは壁との距離が近すぎます。このノードに太った人がやってくるとお腹が壁につっかえてしまうでしょう。ゆえにノードとしては有効ではありません。
⑤有効なノードだけを残す
④で得られた有効なノードだけを残します。シードの周りのノードは上下左右が有効でした。そのあとはどうすればいいでしょうか。答えは、シードの上下左右のノードを基準として同じことを繰り返せばいいのです。
⑥エッジを作成する
④と同じような図ですが考え方も同じです。基準とするノードとその８方向のノードの間間のノードを調べ、各々のノード間で何もないかつ壁と近すぎなければエッジを作成し、間に壁がある、または壁と近すぎる場合はエッジを作成しません。壁と近すぎるのが問題の理由は④と同じで太った人が通るとお腹がつっかえてしまうからですね。
⑦すべてのノードでエッジを作成する
これは有効なノードをどの順番でもいいので片っ端から調べていけばいいです。すべて調べ終われば完成です。
以上が大雑把な理解です。少し細かいですが、一つ一つを追っていけばそんなに難しくはないと思います。ソースコードにも触れる予定でしたが、長くなってしまったのでソースコードは次回に持ち越します。
追記
その３を書きました。
新作アプリ作りました↓↓
