ぷよぷよ再現チャレンジ ＃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つ古いものでした。
右上がりの階段型や、柄杓型で消えないバグがあります。
現在のバージョンはデバッグ済みなので、次の記事で最新版をアップします。

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

新しい方式

悔しがっててもしかたないから、つながったぷよの検索の部分に新しい方式を実装した。
今回のは、操作ぷよが落ちた時、消えたぷよの上段が落ちた時、それぞれでグループ分けをしなおすので、増えようが、分割されようが、座標が変ろうが関係ない。

まず、ぷよ全てにバラバラのグループ番号を付けてグループ用の配列に記録する。
↓
フィールド用の配列を参照して各グループの色情報を得る。
↓
グループ配列を上段から検索する。
検索ブロックの上下、右に同じ色のグループがある時は、若い方のグループ番号で結合する。
生き残ったグループ番号のメンバーを+1。
↓
検索終了後、メンバーが4以上になったぷよを消す。
↓
消えたぷよの上段を落とす。
↓
最初に戻る。（消えるぷよが無くなるまで繰り返す。）

処理の流れはこんな感じ。
失敗に終った方式から、グループで管理する部分を継承しつつ、インデックスの仕方と検索の仕方を変えた。
グループメンバーの座標を管理する必要がなくなったのと、グループナンバーが使用中かどうかのフラグも必要なくなったので、シンプルな形になった。

まだ、たまにおかしな動きがあるけど、格段に良くなった。
テストしながら直してゆこう。
どうか・・・致命的な問題がありませんように・・・。

http://u7.getuploader.com/game/download/54/%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%8312.zip

実行ファイルをアップしときます。
いつもどうりzipです。解凍してからexeファイルを実行してください。

デバッグ用のため落下ごとに一時停止します。
そのつど、なにかキーを押してください。

下は現在のソースファイルです。
前の方式で使ってた変数宣言が残ったままの生々しい感じで・・・。
http://u7.getuploader.com/game/download/55/%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%8312%E3%81%AE%E3%82%BD%E3%83%BC%E3%82%B9.txt

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

致命的な問題

つながったぷよの管理に致命的な問題を発見。
動作が変だったのはこのせいだ。
消えたぷよの上のブロックが落ちる時にグループ内のメンバーの座標が変る事を想定できてなかった。
それどころかグループが分断される事もあるじゃないか。

ああ、バカだ。俺。

どうやら管理の方法自体を1から考えなおさなきゃいけない。

くっそー！
悔しいなっ！

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

ぷよのグループ管理

ぷよが同色で並んだかどうかとか、同色でつながった数はいくつになったかとか、そういうのを把握するためにもう1つ配列変数を用意した。
前の、配列変数には座標上のぷよの色が記録されていたんだけど、今回のはグループナンバーが記録される。

処理の流れはこんな感じ。
例えば最初に赤が二つのペアを右隅に置くと、

～前略～
000000
000000
000002
000001

こんな感じになる。
同色であってもいったん、別のグループとして記録される。
その後、フィールド内を順に検索して、同色が隣り合っている場合は、片方のグループに結合してしまう。
その際に、互いのグループのメンバー数を足し、それぞれの座標も生き残る方のグループ番号が引き継ぐ。
結合されてしまった方のグループ番号は未使用のフラグになるので、いずれ新しく落ちてきたぷよに使われる事になる。

～前略～
000000
000000
000002
000002

検索によって赤が隣り合っている事が判明したので、グループ2番で結合。
次に緑、黄色の組み合わせをとなりにおとすと、

～前略～
000000
000000
000012
000032

こんな感じになる。
グループ番号は若い順に使用中じゃないものを見つけ次第、それを使用する。
これをくりかえして、メンバー数が4以上になったグループは消して、消えたマスの上のぷよをスライドさせる処理をする。

グループ管理に使う変数はまとめて構造体にした。
group.Index [gn]　　・・・そのグループ番号が使用中かどうかを表すフラグ
group.Color [gn]　　・・・そのグループの色
group.Member [gn]　　　・・・そのグループのメンバー数
group.MemberX [gn] [no]　　・・・グループメンバーのＸ座標
group.MemberY [gn] [no]　　・・・グループメンバーのＹ座標
gnはグループ番号
noはメンバーの番号


で、ながながと書いてきて、なんだけども、現在バグバグである（笑）
グループの結合処理を行うごとに、とりあえず1～10までのグループデータを表示させて、原因を探索中。
うまくグループ分けできてる時と、そうじゃない時があって、その分岐要因がわからないのよ。

いちお、デバッグ中のバージョン置いときます。
操作は前回と一緒。
落下するごとにデータを表示して一時停止しますんで、そのつどなにかキーを押してください。
毎度ですがzipなんで解凍してから実行してください。

http://u7.getuploader.com/game/download/50/%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%8310.zip

引き続きバグ取りしますＷ
地味に時間のかかる作業なので、ブログの更新が遅れるかも・・・

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

プログラムの設計について

睡眠時間を削りながら、僕なりにぶっ飛ばして作業してきたんで、一つ一つの処理についてはあまり触れてこなかったんだけども、よく考えたらブログのタイトルからしても僕のようにＣ言語やプログラミングを始めたばかりの人も見ていると思うので、少しだけ説明しとこうと思う。
もちろん僕の復習も兼ねる。
ベテラン・プログラマーの方には「何を今さら」的な内容だと思うんだけど、僕にとっては最新のトピックスなので偉そうな説明を笑って許してちょーだい。

で、例えば落下するぷよの回転について。
えっと、まず、今回の場合、厳密に言うと回転では無いです。
座標を中心点を軸にして回転する公式とかを使ってるわけじゃないってこと。
ぷよの場合、上下左右の４方向の要素しかないんで、んな面倒なことは必要ない。

落下スタート時点で下になってるぷよを軸にして、上のぷよをＺキーが押されるたびに配置換えしてるだけ。
下のぷよを①、上のぷよを②、最初の縦に並んだ状態を状態０として、

状態０　状態１　状態2　状態3
②　　　　
①　　　②①　　　①　　　①②
②

こんな感じで①を中心に②の配置を状態別に決定している。
ぷよの状態を表す変数を用意してＺキーが押されるたびに1を足してゆく、んで４になっちゃったら０に戻す。
僕のプログラムでは操作に対する座標の移動は①に対してのみやっていて、あとは状態変数の値から②の座標を求めるようになっている。
まず、これが原則になるルールね。

そして、それを踏まえた上で、例外状況の処理を考える。
どういった例外が考えられるだろうか。

例えば、状態０で左に壁がある時にＺキーが押された場合。
そのまま、状態１に移行すると②が壁の中に入ってしまう。
そういった時にどういう処理をするか、ルールをあらかじめ決めておかないと実際プログラムを書く時に迷ってしまう。
僕のプログラムでは、この場合①と②を入れ替えて状態３になるように処理している。
手元に実物が無いので、本物がどういう処理をしているかはわかんないけど、まったく同じにしたければ調べて同じになるようにルールを決めれば良い。
ここで言いたいのは例外状況や決まりを、あらかじめ洗い出して、どう処理をするか決めておく事が大切だと言う事だ。
そうじゃないと今回作っている程度の規模のプログラムでさえ、途中から何処で何をしようとしていたかを把握できなくなる。
で、バグった時に前々回の僕の記事のように混乱するわけだ（笑）。
それでも解決できれば良いのだけど、そうじゃない時は何時間も間違い探しをしているうちにモチベーションが下がって投げ出してしまうかもしれない。
設計をあらかじめ考えて書き出しておくことは大切だなあと、本当に思った。































































































































「試しにぷよを再現してみるか」ってボンヤリ考え出したころからのメモ。
ほとんどが色が同じで隣り合っているぷよを配列内でどうやって検索するのが効率的か検討する内容だ。
こういう工程が僕は一番楽しい。
解決法を発見できた時の達成感は名作ゲームをクリアできた時に匹敵するくらいだ。
って言うか、これがほぼ固まってしまうと、プログラムを書くこと自体は作業のよう。