はじめに
スマホゲームで障害物ありの最短経路を求めたくなって、A*探索を使ったのですが、めちゃくちゃ重くなったので、それへの対策と効果の記録。
前提条件
- A*探索にはこれを使用した。
- ゲームのルールは、障害物のある部屋で敵が主人公を追いかけてきて、主人公が捕まったらゲームオーバーになる、
- 主人公と敵は将棋盤のようなマス目を1マスずつ進む。
- 敵は500msごとに、主人公の現在地から最短経路を算出して、追いかけてくる。
- この条件で20×20のマスで遊んだところ、移動のたびに最短経路を算出しようとして重くなり、ゲームがカクついてしまった。
- 原因はA*探索に時間がかかっていること
やったこと
移動のたびに計算をしない
最初は500msごとに最短経路を算出していたので、それをやめました。最短経路は4回に1回計算して、それ以外は以前に計算した結果を使用する。つまり、4回に3回は最短ではない経路を進む可能性がある。
結果は、多少は改善されたが、そもそものゲームのルールが崩れるので不採用。
ゲーム開始時に全ルートの計算を行ってその結果をキャッシュする
ゲームがカクつかなければよいので、最初に全ルートの計算を行い、その結果をキャッシュし、最短経路の算出にはキャッシュを使うようにした。
結果は、ゲーム内のカクつきは改善されたが、ゲームが開始できるまで10秒ほど計算に時間がかかってしまったので不採用。しかし、計算結果をキャッシュする方式は有効なので、以降は全ルートの計算をいかに早くするかを検証した（目標は2秒以内）。
全ルートの計算の無駄をなくした
全ルートの計算における無駄をなくした。具体的には、A→B→C→Dという最短経路を見つけた際には、B~D間、C~D間そして逆のD~A間の最短経路は算出したものしてキャッシュ化した。
結果は、多少は改善されたが、ゲーム開始まで6秒ほどかかってしまうのでやはり不採用（正確にはこれだけでは不十分）。
結局…
計算の最適化はここまでにして、開発時に事前に計算した最短経路をJSONとして保持し、それを読み込む方式にした。全ルートの計算のJSONの容量は800KBくらいで、デコードさえしてしまえば全ルートの最短経路が使えるのでこれが現状のベタープラクティス。
しかしこの方式だと、 マス目の数、障害物の配置が変わると、最短経路を計算しなおしてJSONも入れ替えないといけない という問題点が残るので、引き続き調整は行いたい。
もし、知見がある方がいたらぜひアドバイスいただきたいですm(_ _)m