2014/11/27 円の接線とA*とAVL tree

アメリカは、感謝祭の連休に突入した。僕も、授業があとは残すところ学生さんの発表を聞いてテストを採点するだけになったから、やっと一息ついたって感じ。

それで、またYSFLIGHTとScenery EditorとPolygon Crestのコードに手を入れる時間ができたので、上がってきているバグレポート対策とか始めようと思ったのだが、その前に、自動操縦の機体が対空砲の射程内に迷い込んで撃墜されるのがあまりにもかわいそうな気がしてきたので、対空砲の射程を避けて目的地まで飛ぶパスプラニングのコードを書こうと思った。

別にそんなに高度なことをするつもりは無かったので、とりあえず、射程円の半径に入らないようなコースを計算できればそれでいい。そのためには、現在地点から、目的地に向かう間の射程円を避けて飛ぶルートを考えるので、とりあえず、ある点を通って、円に接する直線を求めて、必ず円の接線よりも外側を飛ばそうと思った。接線を求めるコードなんて、前に書いたのがあったろう、と、思ったのだが、どうも再利用できるような形にしてなかったようで、見つからない。基本的に僕はC/C++の標準のみに依存して、再利用の価値があると思われるコードは、自分のクラスライブラリ(YS-Class Library)にまとめていくのだが、そこに入ってない。仕方ないから、久しぶりに円の接線を求めるコードを書いて、クラスライブラリに追加した。

そこで、射程円がひとつの場合、とりあえず射程円を避けて目的地まで飛ばす方法は考えたから、あとは、これを、射程円が複数の場合、また、開始位置が既に射程円内に入っている場合、に拡張すればいいだけ。なのだが、実は、案外これが難しい。ゆっくり計算していいなら、あらゆる場合の全探索とかやってもYSFLIGHTに出てくる対空砲の数を考えると、大したことは無いのだが、これを、60分の1秒のフレームの、さらにごくわずかな時間内に計算させようと思うと、オーダーがNの2乗になるような方法は使えない。100％最適なコースじゃなくても、それなりに使えそうなコースを割り出すのでもいいんだけど、と、思っていろいろ考えたのだが、結局いい方法が思いつかなかった。

仕方ないから、ちょっと経路探索のアルゴリズムを勉強して実装してみることにした。どういうアルゴリズムを使ってみようかと思ったのだが、以前、学生さんがA* (A-star)なる最短経路探索アルゴリズムを実装していたので、学生さんにできるなら、僕にもできるだろうと思って、これを実装してみることにした。YSFLIGHTを作ってて、何がいいかというと、何か新しいことをしようと思うと、今まで使ったことが無いアルゴリズムとかデータ構造が必要になるので、勉強になるのがいい。

そして、Wikipediaに載ってるアルゴリズムをそのまま実装してみた。ところが、「openSetの中で、コスト関数fの値が最小のものを見つける」というところでひっかかる。このopenSetは、毎ステップごとに要素が減ったり増えたり、あるいは、既に入ってるもののコスト関数を更新しなくてはならない。が、ここでどうやってopenSetを覚えておくのか工夫しないと、openSet内の要素の個数Nの2乗のステップがかかることになる。単純な配列を使って、常に中身がSortされた状態に維持しようと思うと、最小要素を見つけるのは1ステップ、新しい要素を追加する場所を見つけるにはlogNステップ、要素を削除するにはNステップがかかる。それが、要素個数回発生するので、オーダーとしてはNの2乗になってしまう。openSetの要素個数がそんなに増えないならいいんだけど、果たしてどうか？

実験プログラム画面。緑が見つけた経路。
黒が障害物。ライトブルーがclosedSet。ピンクがopenSet。

とりあえず、単純な配列を使ってやってみた。すると、openSetは、探索した範囲の外周のノード数分増えるようだ。なるほど、openSetはこれから探索しようとする領域の境界なわけだから、そうなるのか。だけど、これだと、場合によっては結構大きな個数になりそうだ。400x300の格子の対角線を障害物無しで2008年物のMacBook Proに計算させたら約120ms。飛行経路の探索だとどうせそんなきびきびターンできないから、解像度を落としてもいいけど、たとえば、そのうちタクシーパスを自動計算させるために使おうと思ったら、このレベルだとまだ遅い。

これは、openSetの持ち方を変えないとだめだな。それで、前から実装してみようと思ってた、Self-Balancing Binary Treeなるものを試してみることにした。実は、これまでも似たようなデータ構造が欲しいと思った場面は過去に何度もあるのだが、その都度、別の手持ちのデータ構造を駆使してなんとか対応してきた。ちょうどいい機会だからこのデータ構造を作って理解しておくと、今後いろいろ楽になる。

そのSelf-Balancing Binary Treeにはいくつか種類があるようだったけど、AVL treeというのを聞いたことがあって、これも、Computer Scienceの授業の学生さんが課題でやってたから、学生さんが一週間でできるものなら、僕なら1〜2時間もあれば書けるだろう、と、思ってやってみた。

そんなの、ネット上に落ちてるコードを使ったらって？そんなことしたら勉強にならないじゃない。

とりあえず、Wikipediaに載ってるアルゴリズムをそのまま実装してみた。コード書きつつ「本当か？本当にこんな単純なアルゴリズムでできるのか？」と、思ったのだが、本当に動いた。で、いくつもバランスが取れてるかのチェックとか、並び順のチェックとか、ランダムに数値を足したり削除したりするテストとか書いたけど、本当に動いているようだった。

そして、スピードがどんなものかテストするために、二百万ノードを適当に追加して時間を計測してみたら、9秒。遅い。二百万ノードぐらい一瞬で終わるかと思ってたのに。まだ、すべて正しく実装されていれば、本来は必要ないはずのチェックとかも途中に入っているとはいえ、アルゴリズムが単純な分、そんなに無駄を削ぎ落とす余地は無いような気がした。

 ダンキン・ドーナツで考えること1時間ぐらい。最適化のオプション(/O2)使うの忘れてた。

テンプレートクラスだから、ほっとけばメンバー変数のアクセス関数なんかはinline展開してくれるはずなんだけど、/O2つけてなかったら、ただの関数になるから、そりゃ遅い。そして、/O2つけたら、2Mノードが3秒未満。まあ、そんなもんか。10Mノードを追加してみたら24秒。その後、念のために入れていたチェックを削ったりして、19秒まで速くした。10Mノードの削除は20秒。多分、バランスの再計算をもっと減らすことができて、あと1割ぐらい速くなるのではないかという気がするけど、まあ、実用的には問題なさそうなレベルになった。

Astarの方も同じぐらい速くなるかと思ったら、こっちは60〜80ms。こっちは、/O2オプションをつけても、そこまで速くならなかった。

だが、それはまだopenSetの持ち方をAVL treeに切り替える前だから、切り替えればさらにスピードアップ、の予定だったのだが、60〜80ms。変わんないじゃん。ということは、どこか別のとこにオーバーヘッドがあるのか。予想がはずれたなあ。ちなみに、ThinkPad X230Tでやったら、30〜45ms。どっちも1スレッドなんだけど、クロック周波数以上の差が出るのは、キャッシュとかの違いなのかね。

Astarの方は、YSFLIGHTに組み込むのはもう少しスピード上げてからがいいかな。これがうまいことできるようになったら、対空砲陣地だけでなく、地形を回避して目的地まで自動操縦で飛ばすとか、いちいちScenery Editorでタクシーパスを指定しなくても、自主的にタクシーパスを計算できるようになったりする予定。

そのようなわけで、経路探索を円の接線で済ませようと思ったら、そこまで甘くなくて、Astarアルゴリズムを実装したら、予想外に遅かったため、AVL treeで高速化しようと思って実装したところで、実は単に/O2オプションを追加してなかっただけで、しかも、AVL treeを駆使してもAstarのコードは大して速くならなかった、という感謝祭の連休のスタートだった。

あ、そうか。互いに重なり合う射程円をまとめて一個の円にするという方法で、互いに重ならない円の集合にすれば接線法でもいけるのか。(今思いついても遅い！）