回心誌

世の中わがんね

CodinGameが楽しすぎて

休日を潰した。

Mars Landar のLevel 2に10時間以上は費やした。
工学系の知識があれば簡単なのかもしれない……自分なりのやり方をまとめる。

  • 平坦な土地の座標を調べる。ゴールがそこなので、まずこれをしないとはじまらない。
  • 「角度、出力が今のままだったら、nステップ後に座標や速度がどうなってるのか」の予測を計算すると便利。けっこう精確に予測できる。

自分は次のような式で計算した(python

# estimation
def estimate(x, y, hs, vs, f, r, p, step):
    rad = math.radians(r)
    ha = -math.sin(rad) * P
    va = G + math.cos(rad) * p
    xe = x + hs * step + step * (step - 1) * ha * 0.5
    ye = y + vs * step + step * (step - 1) * va * 0.5
    hse = hs + ha * step
    vse = vs + va * step
    fe = f - p * step
    return (xe, ye, hse, vse, fe, r, p)
  • 点と直線の距離の公式とか色々使って、壁までの距離を調べる。近づくにつれて壁に対して垂直になるよう角度を調整するとか、衝突回避に使える。
  • パワーは3か4の二択。火星の重力加速度が-3.711なので、調整しようとすると自然とそうなる。
  • 水平方向のスピードが大きすぎたら、進行方向と逆向きに傾きを付けてスピードダウン。
  • 垂直方向のスピードが大きすぎたら、パワーを上げて傾きを0度に近づける
  • 燃料が少ないのにこのままじゃゴールに着かなそうだったらパワー節約。特にLevel 2のテストケース1は燃料が足りなくなりがち。
  • 着地直前は特に速度を落とす。また、着地時には角度を0にしないと失敗する。
  • 条件分岐で調整すると、動きが不安定になりがち。漸進的に変化するようにした。
  • deep canyon対策で、凹んでいる部分を埋まっているものと想定。衝突回避はその想定に従って行う。
  • high ground対策で、着地地点の高度と比べて低くなったら高度を上げる。
  • 予測進路と壁との交点を予測して……とかもやったけど、けっこう難しかったので破棄。予測位置を使うと動きが不安定になりやすいので、それはそれで難しい。

何度もミスって細かい数値を微調整してレベル2はクリア。全ステージでkabos!
せっかく精度の高い予測ができているので、再帰的な予測とかもできたら面白そう。
衝突回避のモデルとしては、いくつかの選択肢から予測結果が良さそうなのを選ぶというのも見たことあるし、やってみたら面白そう。

ただ、Level 3のマップはそういうのではうまくいかなそう。場当たり的に動きを調整するだけではダメで、開始時にゴールまでの大まかなルートを計算させる必要がありそう。