2010年10月2日土曜日

Android版「Army & Maiden」その2 高速化

各種仕事と平行作業で開発しているAndroid版の「Army & Maiden」ですが、ようやくエミュレーターと実機で、普通にプレイできる速度で動くようになりました。

「Army & Maiden」は、PCとAndroidのコンパチで動くライブラリを作りながら開発しています。

このライブラリは既に完成しています。そして、同じゲームのプログラムで、PCとAndroidコンパチでゲームが動いています。

データも完全に互換性を保っています。データに関しては、Zipで固めたデータを、Androidアプリの「res/raw」フォルダに放り込むだけで使えるようになっています。

このように、けっこう面白いライブラリ群ができています。



さて、このようなライブラリができたわけですが、全てが順調というわけではありません。

PCとAndroidでは基本スペックが違います。なので、低スペックのAndroid端末でも動くように、ゲームのルーチンなどを高速化する改良が必要になります。

PCとAndroidの主な違いは、CPUとメモリーとJVM(Java仮想マシン)です。

このうち、メモリーに関しては、既にPC版で16MB以内で動作するように作り込んでいます。なので残りはCPUと対VM用の改良ということになります。

というわけで、ここ数日間取り組んだ、対Androidアプリ用の高速化のまとめを書いておこうと思います。



●ZIP内ファイルの高速読み取りライブラリの作成

Androidの「res/raw」フォルダに入れたZIPファイルを普通に読み込もうとすると、リソースIDからインプット・ストリームを取得して、ZipInputStreamを使って内部のファイルを1つずつ走査していく必要があります。

この方式では、大量のファイルをZIP内から読み込む際には非常に時間がかかります(毎回走査しないといけないので)。

この問題を回避する1つの方法として、ファイルをZIPで固めずに、バラバラにresフォルダに格納することも考えました。しかしこの方法は「PCとAndroidコンパチ」という開発コンセプトから外れるので却下しました。

最終的に取った手法は、アプリ起動時に、リソース内のZIPファイルのヘッダー情報を走査してマップを作り、実際にアクセスする際はリソースのインプット・ストリームを、必要な分だけスキップして、対象のファイルだけを取り出すというものです。

ZIPファイルは、内部的には、「ヘッダ情報」「データ本体」「ヘッダ情報」「データ本体」…と続いています。

なので、初回に、この「ヘッダ情報」だけをまとめて読んで、必要な情報をメモリ上にまとめておき、必要に応じて、インプット・ストリームをスキップして、データ本体を解凍するようにしたわけです。

この改良前は、全ファイルの読み込みに数十秒掛かっていました。この改良で、実用可能なアプリになりました。



●デフォルト背景のキャッシュを持つように変更

Androidでは、ビットマップ描画の際のオーバーヘッドがかなり大きいです。

そのため、デフォルトの背景(毎回タイル描画していた)を、画像キャッシュとして持つようにして、描画回数を減らしました。

PC版だと、画面サイズ分の画像を持つので、けっこうメモリを食うのですが、PCだとそれほどメモリの制限もないので、まあいいやと割り切りました。

他にも、成績表などもキャッシュを持つように変更しました。



●画面外描画の厳密な禁止

前述の通り、Androidでは描画命令のコストがけっこう大きいので、ゲームルーチン側で判定して、描画命令を極力呼び出さないようにしました。



●低スペック・モードの切り替えスイッチの導入

設定ファイルに、低スペック・モードの切り替えスイッチを追加しました。

低スペックモードでは、sleepの時間を変えるなど、細かいところで、CPUに余裕がないことが前提のルーチンに切り替えるようにしました。



●移動アルゴリズムの改良

ユニットの移動アルゴリズムを改良して、コストを大幅に減らしました。計算回数を可能な限り減らして、処理時間を短縮しました。



●移動計算の時間分散処理に、1フレーム内の最大計算回数を設定

これまでは、単位時間内に、なるべく均等に処理を割り振るアルゴリズムにしていました。

この方式では、ユニット数が増えた時にAndroidで処理落ちすることが分かったので、1フレーム内に計算可能なユニット数の制限を設けました。

そうすると当然、単位時間をオーバーして計算が続くようになってしまいます。この場合でも、見た目には今までと同じようにユニットが動き続けるように、アルゴリズムを改良しました。

Androidでの処理速度が、考えていたほど速くなかったので、ここらへんはかなり書き換えが必要でした。



●ボトルネック部分を低スペック・プログラミングに変更

Androidの開発ツールには、Traceviewという各メソッドの処理時間を集計してくれるツールが付いています。

このTraceviewは、各メソッドの呼び出し元と、内部で呼び出しているメソッドを、親子関係のリンクで示してくれます。

また、処理時間順でメソッドをソートすることができます。さらに、計測した時間が帯グラフで表示されるので、どのメソッドがCPU時間のどの帯域を食いつぶしているのかが、一目で分かります。

このツールは、高速化を行う際には非常に便利です。

これで、呼び出し回数が多いメソッドを確認しながら、携帯Java用の低スペックな書き方にプログラムを書き換えていきます。



以下、低スペック向けプログラムへの書き換え方です。

○グローバル変数は、ローカル変数に参照を渡してから使う。

解説:ローカル変数の方が、アクセスが高速。

○2次元配列は、2次元目を1次元配列に参照を渡してから使う。

解説:2次元配列は、参照の回数が2回なので、1次元配列に渡して、参照の回数を1回にしてから利用する。

○3回以上呼び出されるオブジェクトのプロパティは変数に格納する。

解説:たとえばarray.lengthが3回以上呼び出されるなら、その値を変数に格納しておき再利用する。2回なら、可読性を犠牲にするほどではないので無視する。

○メソッドを極力呼び出さないようする。

解説:メソッドの呼び出しコストが高いので、インライン展開できるところはインラインで書き直す。可読性とメンテナンス性が下がるので、あまりやりたくない部分。

○メソッドは可能ならstaticメソッドにする。

解説:staticメソッドの方が呼び出しが高速。

○JDKのライブラリのうち、低速のものを自前で書き直す。

解説:配列のソートや文字列の置換など。後述。



基本的に、低スペック向けプログラミングを行うと、ソースの可読性とメンテナンス性は下がります。

なので、あまりやりたくない部分ではあります。

以下、その他の高速化(低スペックに関わらず、いつも行っている部分)を書きます。

・書き換えない変数は定数にして、static finalにする。

・floatは極力使わない。

・forループの終了判定部分には、アクセスコストの低い変数か定数を使う。

解説:「for (~;i < arr.length;~)」みたいなことはしない。「for (~;i < len;~)」とする。 ・キャッシュ可能な計算結果は、なるべくキャッシュを取る。



●GCを呼び出さないことでの高速化

これはAndroid版開発前にやっていたことです。Javaは、GCが出ないようにすれば、処理落ちは最小限に抑えられます。

そのために必要なのは、オブジェクトを極力生成しないことです。

また、作成する際も、オブジェクトの数は極力固定にして、一度作ったら処理落ちしてもよい時(画面の切り替えタイミングなど)まで廃棄しないようにします。

そして、オブジェクトがGCで確実に廃棄されるように、不要になったオブジェクトにはnullを入れます。

また、Javaの基本ライブラリのメソッドには、内部的にやたらとオブジェクトを生成するものもあります。そういったメソッドは、開発コストと効果を考えて、自前のメソッドに置き換えます。



●低速なAPIを、自前のAPIで高速化

いくつかのクラスのメソッドは、内部的にはかなり重かったりします。これらのソース・コードは、「Google Code Search」で検索して、どこに無駄があるのかを自分で確認して、置き換えるべきかどうかを判断します。

□Google Code Search
http://www.google.com/codesearch

以下、私が置き換えた命令です。

○配列のソート

Javaのオブジェクト配列のソートは、速度はともかくメモリーを非常に食います。内部的に、新しい配列の参照を作り、ソートに利用しているからです。なので、配列のソートを毎フレーム行うと、GCが出まくります。

そこで自前で、オブジェクトの新規作成を行わないソートクラスを作り、そのメソッドを利用するようにします。

また、Javaのオブジェクト配列のソートは、比較子内の比較メソッドで比較を行います。これは、オブジェクトのソートで非常に多数のメソッドが呼び出されることになります。

そこで、特定のオブジェクトの、特定のソート方法に特化したメソッドを作ります。これで、メモリを消費せずに、それなりに高速でソートを行うことができるようになります。

○文字の置換

Javaの文字列の置換は正規表現なのですが、これはコストが高いです。

代替クラスのJakarta langには、正規表現を使わない文字列の置換があるのですが、こちれは2つの点で改良の余地があります。

1つは、内部でStringBufferを使っていることです。スレッドの同期を取る必要がなければ、これをStringBuilderに置き換えることで若干高速化できます。

もう1つは、置換数のオプションがあることです。どうせ、全部置換か最初の1つ置換ぐらいしか使わないので、このオプションを取ったメソッドを作ることで、もう少し高速化できます。

・String.format

formatメソッドはかなり便利なのですが、これは内部的に重い処理を行っているのでゲームのループ内で使うことはできません。

今回のゲームでは、データを文字列で表示する部分があるので、このformatに一部準拠したメソッド(対応は「%s」「%d」「%+d」「%2~9d」「%.1~9f」)を作り、高速で文字列を置換するようにしました。



●回転表示を極力しないように変更

回転表示は、各ドットの描画位置の変換が入るので処理コストが大きいです。

そのため、低スペック・モードではキャラの回転表示をなしにしました(スイングではなく、ステップに動き方を変えました)。



その他もろもろ弄ったのですが、もうだいぶ忘れかけています。

取りあえず、備忘録として記録に残しておこうと思います。

0 件のコメント:

コメントを投稿