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

つながったぷよの検索アルゴリズム　完成！

前の記事の検索方法に穴があった。
配列内を左上から順に検索した後、右下から逆方向にもう一度検索して、グループを結合する事で解決。
これで、同色でつながったぷよを検索してグループ分けする部分は大丈夫じゃないかな。
30分くらいプレイした感じだと、変な動きは無かった。

必要に応じて『苦Ｃ』を見て勉強してたんだけど、こういうのをアルゴリズムって言うのだね。
方法論自体は言語が変っても通用する。
今回の場合、配列内で隣接した同じ数値をグループ分けするアルゴリズムってとこか。
色や形を合わせるタイプの他の落ち物パズルゲームにも応用できそうだ。
こうなると、本物がどんなアルゴリズムを使っているのか知りたくなるなあ。
頭のいい人が考えたら、もっとシンプルで条件分岐や計算の少ないアルゴリズムを考え出すんだろうか？

と言うわけで、このアルゴリズムを解説しておくね。
もっといい方法を知ってる方は、惜しまずに教えてください（笑）

例として、フィールド配列がこんな感じの時を想定する。

～前略～
000000
000100
011100
224130

上の段から順に、1ブロックずつ右にチェックして、ぷよがあったら通し番号をつけてゆく。
するとグループ配列内はこうなる。
各番号のメンバー数はこの時点では全て1だ。
（わかりやすくするために色をつけてます。）

000000
000100
023400
567890

これをまた上の段から順に右方向へ1ブロックずつチェックしてゆく。
1以上の数字が入ったブロックを見つけたら、そのブロックの右となりをチェックし同色の時は小さい方の番号で結合する。
その後、下のブロックをチェックし、同色の場合、検索ブロックの番号で結合する。
結合が行われた場合、それぞれのメンバー数を足し引きする。
右下のブロックまで検索が終るとこうなる。

000000
000100
021100
557190

2の入ったブロックが赤なのに隣と結合されて1になっていないのがわかる。
前の記事の時点では、これが検索の穴だった。
そこで、今度は逆に下の段から順に左方向へ検索する。
で、左となりの場合は若い番号で、その後上下方向は検索ブロックの番号で、同色があったら結合する。
するとこうなる。

000000
000100
011100
557190

見事にグループ分け出来た。
これでメンバーが4以上のグループは消す。
上の配列ならグループ1番が消えるわけだ。

色んなパターンで検証してみたけど、この方法で大丈夫だと思う。
Ｈ型や階段型の配列がきちんとグループ分けされれば問題ないんじゃないかな。

と言うわけで実行ファイルをアップ。
デバッグ用の一時停止は無くなってます。
あと、余りに一瞬で消えてしまって、連鎖だかなんだかわからないので、消える時に0.5秒のウェイトが入っています。
http://u7.getuploader.com/game/download/56/%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%8313.zip
いつもどうりzipなんで、解凍してフォルダ内のexeファイルをダブルクリックしてください。
フォルダ内に入っているテキストファイルがソースコードです。

操作
矢印キーの左右と下で、ぷよ移動
Ｚキーで回転


まだ動きが怪しいので、引き続きデバッグします。
が、取り合えずこれで当初の目標地点にほぼ到達できたんじゃないかと。
ちなみに昨日が誕生日で、ブログタイトル通り35歳になりました。

～追記～
間違えて実行ファイルのバージョンが1つ古いものでした。
右上がりの階段型や、柄杓型で消えないバグがあります。
現在のバージョンはデバッグ済みなので、次の記事で最新版をアップします。