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

まだまだ検索アルゴリズムの話

いや、１週間くらいでゲーム性の再現は出来るんじゃないかと思ってたんだけど、甘くないね。
消えるブロックの検索アルゴリズムはテトリスよりかなり高度なんじゃないかと。
今ならテトリスは挫折せずに再現できる気がする・・・。

で、検索アルゴリズムについて前回に引き続き。
このアルゴリズムは、上り下りの回数さえ適切なら、どんな形の並びでもきちんとグループ分け出来る。
ただし、その回数が問題だった。
前回、登り、下り、登りの３回で行けるみたいなこと書いたんだけど、ぜんぜん足りない（笑）
だいたい、フィールドの横幅しか考えてない時点で終ってる。
アルゴリズムが正しくても、使い方が間違っていた。
自分の頭の悪さにがっかりしたよ。

で、横６ブロック、縦１３ブロックで考えられるもっとも（アルゴリズムにとって）過酷な並びを考えてみた。
このアルゴリズムは、登り検索は右下方向に強く、左方向には１ブロックしか追えず、上方向にいたっては最弱で１ブロックも追う事が出来ない。
下り検索はその逆だ。
これは検索の流れを前回の記事で確認してもらえばわかると思う。
で、ことごとく検索方向を潰す最悪な並びを紙に書いて、完全に検索し終わるまで何往復必要か計算してみた。
その結果、８往復・・・。
もちろん実際にゲーム中にフィールドのブロックを全て使ってそんな並びで消す状況なんかありえないんだけど、これまでの制作の流れから過信は禁物と思い８往復を実装した（笑）。

いや、今のＰＣの性能は素晴らしいね。
その程度のループじゃ体感速度はまったく変らない。
僕が小学校のころＢＡＳＩＣで遊んでたＭＺ-2200と比較したらいったい何倍くらいの速さなんだろう（汗）。
今のＰＣだってＰＥＮ３の1Ｇｈｚくらいだったはずだから、ぜんぜん現役スペックじゃないんだけどね。

と言うわけで、アルゴリズムの出来としてはいまいちかも知れんけど実用十分てことで許してください。
とは、言ったものの、頭の中に他の方法（アルゴリズム）も浮かんでいるので、我慢できなくなったら試してみます。

最後に今回のアルゴリズムについて前回の記事で漏れがあった部分を補足説明しときます。

group.Member[ グループナンバー ]　と言う配列変数を定義して、各グループのメンバー数（つながったぷよの数）を管理しています。
インデックスの段階では通し番号なので当然この配列変数には全て1が入っています。
その後、登り下りの検索のなかでグループの結合が起こるたびに、group.Member[ 生き残ったグループ番号 ]　が+1、group.Member[ 吸収されたグループ番号 ]　が-1となります。
検索が終了すると、group.Member　を参照して、メンバー数が４以上になったグループを洗い出し、フィールド配列を検索してそのグループ番号が入っている座標を消します。
あとは出来た隙間の上に浮いているぷよを落下させて、新しい配列でまたインデックスからやり直します。
連鎖がおき続ける限り、この処理を繰り返すわけです。

このアルゴリズムは恐らくぷよぷよを再現する方法の中で最もと言っていいほど、シンプルで幼稚で効率の悪いアルゴリズムだと思います。
（しかも本当に完全かどうか自信もない・・・）
それでも作り始めた時点で、僕の頭にはこれの原型となるアイデア（前の方の記事で失敗に終ったやつ）しか無く、初心者が開発環境をインストールして２週間やそこらで作れるのはこの辺がいいとこかと・・・。
でも、それだけに、ここを読んでいる方に僕のような初心者の方がいるなら、わりと理解しやすいアルゴリズムだったんじゃないかとも思います。
現在は他の方法もぼんやり頭の中にあります。
それは検索ロボット型アルゴリズムと名づけたい感じのもので、つながったぷよを法則に従ってグループ結合しながらわたり歩き、最初の検索座標につながっている数を持って帰ってくるというものです。
イメージが伝わりにくいですかね、すいません（笑）。
これはこれで、はたして上手く行くのか試してみたい気持ちがあるので、そのうち作ってみるかもしれません。

では、実行ファイルを。
８往復（笑）検索バージョンです。
見た目上は何も進化してなくてすいません。
http://u7.getuploader.com/game/download/66/%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%8315.zip
変更箇所は検索部分のループだけなので、変更のあった検索関数のみソースのテキストファイルを同梱しています。
ダウンロード、実行に当たっての手順は＃14の記事などを参照してください。