ダウンロードはこちら
新しいビットマップ イメージ

パズドラに関するアプリはさらに増え今ではコンボを計算するアプリは合計で3つとなった。

その中で、自分の作ったルート解析君はあまりに遅い。
比較アプリ名は避けるが、現時点で無料のほうのコンボ計算アプリは、同じ全経路検索でウチの約4～6倍の早さということが分かっている。
有料のほうは、全経路検索ではないらしいので比較はできないが最近上から落ちてくるドロップも考慮してくれるようになったらしく、コンボ効率は更に上がっている。


そこで、計算速度改善のため抜本的な見直しを行った。


１、iPhone用に作るのではなくパソコン用に作る。 
まず一番計算速度に影響するのが、CPUのスペックである。動作周波数そのまま速度に比例する。モバイル機器のCPUはせいぜい1.5GHzとかそんなものなので、パソコンのスペックには到底かなわない。
そしてパソコンのCPUですら今では頭打ち。そこで登場するのがGPGPU技術！
これはグラフィックボードの演算能力を使ってCPUより高速に計算するというもの。

２、GPUで計算する。
現在のグラフィックボードの能力は凄まじく、1枚あれば3.7TFlofs(テラフロップス)計算できるものもある。
これはメニーコアCPUの3～100倍とも言われている。
つまるところ、単純に演算能力の高いデバイスの能力をフルに使って、ガンガン計算させようというものだ。究極の計算高速化手段だがなんとも外国人っぽい発想である。
私は１年くらい前から、シミュレーションのプログラムを高速に動かすためにGPGPUの研究を続けていた。今ちょうどHLSLを使ってGPGPUを手軽にできるHSP向けプラグインの開発をしていた所であったため、プラグイン開発と並行してパズドラルート解析の高速化バージョンを作ることとなった。
（結果的に、GPGPUソフトの開発で必要と思われる機能がうまくピックアップできプラグイン開発に昇華できた）

３、計算アルゴリズムの改善
今までは、コンボの計算アルゴリズムは非常に複雑なものであった。

１つの画面内に６×５マスの３０個のドロップがある。
その中で、横３つが同じ色である、又は縦３つが同じ色である場合に、その３つのドロップをコンボ発生フラグ1とする。
次にコンボ発生フラグのあるドロップで、ドロップが縦横でつながっている、かつ同じ色ならば、それが１コンボとして計算する。
繋がっていない同色なら別コンボとして計算する。
ここで一番重要なのが「つながっている 」か判定することだ。これには塗りつぶしのアルゴリズムを使って判定していたのだが、これでは毎回コンボ発生時にコンボの数だけ塗りつぶしを実行することになり、非常に時間がかかる。

そこで、あらかじめ全てのコンボ発生パターンを記録したコンボシートなるものを作成することにした。
３０ドロップを１列に直線に並べる。１つのドロップは、コンボ発生フラグ有る無しの２つのどちらかの状況しかとりえない。
このとき、３０個のドロップのコンボ有る無しがとる全ての場合の数は2の30乗、つまり1073741824パターンである。
この1073741824パターンで、コンボがいくつ発生するか、全体攻撃がつくかどうかを記録したもの、それがコンボシートである。

・・・つまり、塗りつぶしの部分が要らなくなったということである。（予め計算してある。）

他にも、同色ドロップから始まる事実上全く同じといえるルートを計算から除外したり、細かい所でアルゴリズムの改善が行なわれた。


４、使用言語の変更
iPhoneアプリではインタプリタ型のHSPをつかていたので、どうしても速度に不安があった。
今回、主要な計算部分はGPUでやっているし、CPUでやらないといけない部分に関してもC++で作成してある。
だいたいHSPとC++の速度差は10倍くらいである。



という徹底した計算高速化を追求した。
そして以上の改善より、なんとアプリ版より
1086倍も高速になった！！！！！
 それもグラフィックボードがnVidia GT520の時である。これがハイエンドのものとなればさらにもう10倍は早くなろう！
これがGPGPUの威力である。
 新しいビットマップ イメージ
これはルート長16マスの設定で、1億パターンを計算し結果は47秒であった！！


他にも解析中の「計算中・・」という文字がずっと動かなくてフリーズかと思われないよう、進行度合いを表示するようにした。


さてここでこのソフトの注意点がある。
・プログラマブルシェーダーに対応していないグラフィックボードでは動かない。
（OSはXP以上、対応シェーダーモデル3.0以上 ）
・最大テクスチャサイズが4096未満のものは起動しない
・計算中はGPUに非常に負荷がかかるため、動画再生やウィンドウの移動などがカクカクになる
・負荷がかかりすぎると画面が落ちる可能性がある（スペックの低いグラボだと）

と言ったもので、前者２つはかなり古いグラフィックボードで起こると予想されるが、一応少し前のノートパソコンのオンボードですら動く レベルである。
core iシリーズのIntel HD Graphicsでは確実に動くであろう。

４つめの画面落ちだが、設定で安定動作機能も付いているので低速になるがそれを試してみれば必ず動くはずだ。
設定で高速計算機能もつけた。レジストリをいじってGPUのパワーをフルに引き出せる秘技だ。これで通常解析の1.2～1.5倍は早くなうだろう！


またこれはα版である。 まだまだ、不具合が多い可能性があるので、ルートの検索結果がおかしいなどという不具合があればコメント欄にぜひ報告してほしい。
検索結果は、コンボ数の多い順ではある。


最後に完成版までに搭載する機能のピックアップだ。以下のものを予定している。
・起動時の高速化
・検索条件の設定（何色優先など）
・グラフィックの更新
・計算高速化
・ベンチマークのツイッター公開機能？？


上から最優先課題として搭載していく予定だ。