kumaryu日記

_ ICFPプロコン 3〜6日目

俺だけ長いのは、3日目から熱を出してずっと寝っぱなし(orトイレに立て籠り)だったため。

ちゃんと仕事に復帰するまでがICFPCです。

まあ3〜6日目はどうでもいいんですが。

俺の戦略っつーか戦術は簡単過ぎるから他の人の戦術なんか怖くて見れないよママンとガクブルしてたのですが、ある程度元気になってサイト巡回してたら見えちゃうこと見えちゃうこと。

で、いろんな人の方策を見ちゃったら、皆俺くらいのことは最低限やったうえで超色々やってんだろーなーという想像程世界は広くなかった。

ので、ちゃんと書く気になった。

あれ、このくらいのことは最低限だからみんなかいてないとか…。

戦略

まあ大体真っ直ぐ走って、穴に落ちたり岩に当たらなきゃいいや。安全運転だけど基本ブッ飛ばすのでたまに事故ります。事故った時は次のクローンが上手くやってくれるでしょう。

火星人？火星人なんて存在しません。火星はそんな高等生物が生きていける環境じゃないですよ。そうコンピュータ様も言っています。え、さっき何かに当たった？プラズマですよ。事故事故。

…というわけで、基本方針は至って普通。

火星人

火星人を無視したのは当たった試しがないから。

まずサーバがv1.1の間は野次馬みたいに近づいてきて遠巻きにこっちの様子を見てるだけ。火星人は友達説浮上。

本性を現したのか過剰な友好表現なのかv1.2では見つかった瞬間一心に追いかけてくるので当たりはするんだが、目の前にもう居るときか事故的な状況でないと当たらない。

本当に一心に追いかけてくるのだが、奴の性能がこちらと同じか、より劣るなら普通に振り切れる。無理なのはこっちの加速が間に合わないときだがそんな状況で会ったら何しても無駄だって。

相手の性能がこちらより上の場合、何しても追い付かれる。考えるだけ無駄。

つまり火星人は無視していい、とした。

火星人じゃなくてレンズについたゴミですよ。

経路探索

決定ではなく探索、だが、特になにもやってない。

見つけた岩とクレーターは記憶しておくけどそれだけ。

結局余計な探索をしようにも、どの辺を探索して良いのかが分からなかったんだよねぇ。

一番知りたいのはゴール近くだし、普通に走って行けばその辺見えるわけだし。あと毎回どこから始まるかわからないしね。

経路決定

さてここからが本題だ。

どうやって進む方向を決めようかって話。

基本的には目的地に一直線に向かい、途中何かあれば避けるだけ。

1. まず目的地がないと話にならない。最初は目的地はおうち、つまりゴールだ。
2. 現在地点から目的地の間に障害物*1が無いか調べる。
3. あったらそれを避けられる場所に一旦目的地を設定。
4. 新しい目的地から前設定した目的地に向かうのに障害物がありそうなら、それを避けられる場所をその次の目的地として設定。
5. 逆に現在地から新しい目的地までに障害物がありそうなら、やっぱりそれを避けられる場所を新しい場所に設定。
6. これを再帰的に設定していけばとりあえず知ってる障害物は全部避けてるはず。そこを運転で通せるかどうかは知らんけどな！

難しくないよね。

で、現在地から目的地までに障害物があるかどうか調べる方法だけど。

現在地と目的地を結ぶ直線と、障害物の位置との距離を計算する。その距離が自分の半径(0.5m)+障害物の半径(+少々)以下だったら途中で当たるね。

この時すっとぼけて自分の後ろにある障害物を避けないようにそれは確認しておく。

あと避ける位置だけど。

余計な寄り道はせずに早くおうちに帰りたいので最短ルートを行く。

最短の経由地点は、障害物の位置から現在地から目的地に引いた直線へ垂直に引いた直線上の、障害物の位置から障害物の半径+自分の半径足した距離にある点、になる。

正確にはこれが二点あるからそのどっちか近い方を選べばいい。

これをやると障害物がでっかい時に、経由地点に行く途中で避けるつもりの障害物に当たっちゃうことがあるんだけど、それは再帰的に障害物判定と経由地点設定するので大丈夫。

さてこれで上手く避けられそうだなーと思いきや、実は一度に回避してる障害物が一個なのでまずい。

避けようとした先に障害物があったらどうなる？そこに行くのに邪魔な障害物だから避けようとするかもしれんけど、避けたところでたどり着けないじゃない。

なのでそういう場所には避けないようにした。避けたと思った先に障害物があったら、そいつの大きさ分もうちょい遠くへ避けてやることにした。そこにも何かあったらもうちょっと先まで…。

で、何も無いところに避けられたわ、となったらまた再帰的に経路決定してやれば密集地も乗り越える寸法です。

実際は避ける方向を最短方向にしたら行ったり来たりの無限ループになったので、常に左方向に避ける左回りルート、右方向に避ける右回りルートを検索してどっちか短い方を選ぶようにした。

かなり入り組んでると最短じゃなかったり、ゴールできなかったりするかもしれんけど、そこまで難しいマップは諦めようぜ。

運転

どこを走るか決めたらあとはちゃんと走るだけ。

普通にフィードバック制御で、決めた速度に足りなきゃアクセル、過ぎればブレーキ、丁度良ければそのまま走行する。

向きも同じように左右をコントロールしてやる。

目標との向きが一定以上離れてたら急旋回を使う。とりあえず適当に15度以上にしたがまあよさげだったのでそれで。あんまり小さい角度で使うとはげしくあっちこっち向きそうだからね。

そういやこれらの制御コマンドを送るのは、サーバから状態情報が送られてきて必要な計算が終わり次第すぐ。それだけ。

マニュアルでもお奨めされてたし、あんまり細かい制御は性に合わん。

角度制御はまあ向きたい方向向けばいいのであんまり考えることはなかった。

ところが速度が問題だ。

とりあえず全力で走ってみるとそりゃあもう落ちる。曲がりきれるわけもないせまいところを通ろうとして落ちてみたり、ゴールを通り過ぎてくるくる回ってみたり。

なのでちゃんと目標地点に着きそうな速度で走るようにした。

まず、通り過ぎて行ったりしないようにしたい。

通り過ぎるのは目標地点の方向を向く前にすごいスピードでどこか行くから。

じゃあ丁度着くスピードにしてやればいいんだ。

まずあと何秒あれば目標地点を向けるのか。これは向きがあと何度ずれてるのかを最大旋回速度で割ればいい。旋回にも加速度とか表示されないだけであるんだが、細かいことは気にしない。

で、一定速度vを維持したときのt秒後の速度ベクトルVは

V = (v*cos(r0+t*RMAX), v*sin(r0+t*RMAX))

これをtについて0からTまで積分してやって現在位置を足すとT秒後に到達している位置が計算できる。あ、Tは目標に向き直るのにかかる時間ね。

ちなみにcosとsinの積分が出来なくてしかも数学の教科書もどこにしまったのか分からなくなっている俺にやさしく答えを教えてくれた心のチームメンバーが居るのはここだけの話。つか俺チーム結局一人だけどさ、真面目に数えたらどう数えても失格になるほど心のメンバーいるんですが。誰もメンバーなってくれなかったけど。

あー、それはさておき。じゃあ、計算して出た位置と目標地点を一致させるような速度vを計算して設定してやればいいだけだ。まあこれは簡単ですね。

これで通り過ぎずにきちんと走れるように…うーん、本当か？

これの問題点は、気付いた時にはもうスピードを落としきれないような近い目標地点があると破綻するってこった。加速度が無限大だったら問題ないんですけどね。

対策として、大抵問題になるほどスピードが出るのは直線のあとのシビアなカーブなので、大体真っ直ぐぶっ飛ばしてたら、目先の目的地でなく、目的地からその次の目的地に向かうのに必要なスピードに落としておく、ということをやっておいた。

もちろん目先の目的地がおうちの場合は別で猫まっしぐらだ。その次に向かう場所などない。

残念ながら加速度とかは加味していないので、ながーい直線の後で急カーブとかあると直線をチンタラ走ったりするんだが、本当はこれ三日目に直したかったなぁ。

ブレーキの加速度が計算してあれば十分速度が落とせる距離まで全力ダッシュできたのに。

加速度は2回連続でアクセル状態だったとき、その速度の差分/時間の差分で計算してる。ブレーキの加速度も同じだが、こっちは計算できる機会が少なそうなのが悩みどころ。

どちらも提出時点では使用していない。

諦めたこと

密集した障害物を避けるのに、近い岩をまとめてでかい障害物にする。

でかい障害物をやっぱり円で近似したためにあっという間に全部くっついて超でっかくなった。

最低限楕円にすべきだと思ったが、向きとか難しいのでやめた。

マップをグリッド分割してA*。

遅すぎて話にならなかった。マップを階層化してA*するかと思ったが、上の階層で正しい経路が選べないので止め。

この辺りはまだまだ未知の領域ですねぇ。勉強したいところ。

手入力最強説。本番で操作するプレイヤーの腕次第という超運ゲーなのでやめ。

他にやったこと

一日目にクライアント側にもGUI作ったよ！

目的地とか表示できると何考えてるのか分かりやすくていいですね。 提出用コードとは切り離されていますので提出してません。

二日目にマップをランダム生成させたよ！

サンプルマップが簡単すぎて本番マップはこのくらい難しいんじゃないかと。

しかしランダムは難しすぎました。ちょっとでも密度の濃いマップを作ろうものなら全く歯が立ちません。

結局本番マップはどんなレベルなんだよ。

まとめ

文章で書くと長いけど、Rubyで書いたら通信とかぜーんぶ合わせて500行以内の小さいものですよ。

実際送ったコードにはA*のクラスとか使ってもないのに入ってたから500行は越えてたけど。三日目が生きてれば整理したんだけどなぁ。

ゲーム作ってた経験(いやまだ製作中ですよ)がちょっと役にたった。衝突判定とかね。

こんな感じのAI動かす簡単なゲーム作りたいと思ってたのにやられて悔しい。

集団のAI書いてみたいんだよなー。