🦅

スマホで最短経路探索を使うとアプリが重くなる問題への対処メモ

2020/10/14に公開

はじめに

スマホゲームで障害物ありの最短経路を求めたくなって、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