ぷよぷよ再現チャレンジ ＃14

今度こそ検索アルゴリズム出来たんじゃない？

前回の記事で『完成！』とか言っといて、非常に恥ずかしいのだけど、普通に穴がありました。
今度こそ大丈夫だと思います。
ではアルゴリズムの流れを。
前回のは忘れてください（笑）


～インデックス～
フィールドのぷよ全てに上段・左優先で通し番号をつけます。
これは必ず最初に１回行う処理で、この番号がそのままつながったぷよのグループ番号になります。

～登り検索～
配列内を下の図の順番でブロックごとに検索します。

①→→→→→→
②→→→→→→
③→→→→→→
④→→→→→→
～以下略～

各ブロックごとの検索は以下のように行います。
①右となりのブロックが自分と違う番号で、かつ同じ色ならば、小さい方の番号で結合する。
②下のブロックが自分と違う番号で同じ色ならば、自分の番号で結合する。

～下り検索～
配列内を下の図の順番でブロックごとに検索します。

　～以上略～
←←←←←←④
←←←←←←③
←←←←←←②
←←←←←←①

各ブロックごとの検索は以下のように行います。
①左となりのブロックが自分と違う番号で、かつ同じ色ならば、小さい方の番号で結合する。
②上のブロックが自分と違う番号で同じ色ならば、自分の番号で結合する。


登り検索も下り検索も、検索の進行方向と逆に伸びる枝には１ブロック分しか追いつけないので、検索の進行方向と逆方向に２ブロック以上の長さで枝分かれするぷよのつながりは追いきれない。
これは、つまり片道分の検索が対応できるのはフィールドの横幅２ブロック分までだということを意味してるんじゃないだろうか。

実際２ブロック幅ならどんな形にぷよが並んでも、登り検索１回でグループ分けが完了する。
ところが３ブロック幅だと、例えばコの字につながった場合などで登り検索だけでは対応できなくなる。

111
001
511

こんな感じで、上の図の５の部分が検索からもれてしまうのだ。
この問題は下り検索を加えることで解決できる。
しかし、今度は４ブロック幅までは問題ないのだけど、５ブロック幅になると検索からもれるケースが出てくる。

00000
00000
10112
11102

例えば上の図の2の部分がそれだ。
これに対応するためには、もう一度登り検索を行わなければならない。

つまり、このアルゴリズムはフィールドの横幅が２ブロック増えるごとに、登り検索と下り検索を交互に追加して対応するアルゴリズムと言える。
ぷよぷよのフィールドは横幅が６ブロックなので、登り下り登りと３回検索する必要があるのだ。
もしも、８ブロック幅のぷよぷよを作りたいなら、更に１回下り検索を追加すれば対応できるはずだ。


いやー、こんだけ解説してまた穴があったら立ち直れないかも・・・。

実行ファイル置いておきます。
フォルダ内にソースコードのテキストファイルも入っています。
http://u7.getuploader.com/game/download/60/%E3%81%B7%E3%82%88%E3%81%B7%E3%82%88%E5%86%8D%E7%8F%BE%E3%83%81%E3%83%A3%E3%83%AC%E3%83%B3%E3%82%B8%EF%BC%8314.zip
上のリンク先、下のほうの「同意します」をクリックでダウンロードできます。
ポップアップブロックされる場合はウィンドウ上の情報バーをクリックして「ファイルダウンロード」を選んでください。
zipファイルなので、解凍してからフォルダ内のexeファイルをダブルクリックで実行されます。
操作方法は前回（＃13）の記事を参照してください。
４つ以上つながったのに消えない！って言うようなバグを発見した場合は、消えなかったつながり方をコメントで報告いただけると助かります。

僕の方もデバッグしながら、今後の方針を考えたいと思います。