視線判定（しせんはんてい）と DDA

あなたの担当　この章は、bot の中で使う計算の説明です。使うだけなら → 壁ごしに撃たない

撃つ前に確かめたいことは、たいてい 1 つです。

いま、敵はちゃんと見えているか？

壁の向こうにいる敵を撃っても、弾は壁に当たって終わりです。この「見えているか」を調べるのが**視線判定（Line of Sight、略して LOS）**です。

使うだけなら 1 行

見える = line_of_sight(state.map.grid, state.me.x, state.me.y, state.enemy.x, state.enemy.y)

True なら、自分と敵を結ぶ直線の上に木箱も鉄ブロックもありません。水たまりは視線をさえぎりません（弾が飛び越えるので、見えているのが正しい）。

def update(state):
    want = angle_to(state.me.x, state.me.y, state.enemy.x, state.enemy.y)
    見える = line_of_sight(state.map.grid, state.me.x, state.me.y,
                           state.enemy.x, state.enemy.y)

    return {
        "drive": "forward",
        "steer": want,
        "fire": 見える and state.me.can_fire,
        "barrier": False,
    }

これだけで、弾の無駄撃ちがかなり減ります。ここから先は「中で何をしているのか」の話です。

素直にやると、なぜ失敗するのか

いちばん思いつきやすいのは、直線を細かく刻んで、その点が壁かどうか調べる方法です。

# ✗ これは使ってはいけません（理由は下）
for i in range(0, 100):
    t = i / 100.0
    x = state.me.x + (state.enemy.x - state.me.x) * t
    y = state.me.y + (state.enemy.y - state.me.y) * t
    if state.map.grid[int(y)][int(x)] != 0:
        見える = False

動いているように見えます。でもこれには、致命的な欠陥があります。

刻む数を変えると、答えが変わるのです。

刻む数	結果
100 分割	壁の角をまたいで「見える」
200 分割	角の上に点が乗って「見えない」

壁をかすめる線では、点と点のあいだに細い壁がすっぽり収まってしまいます。刻みを細かくすれば減りますが、ゼロにはなりません。

これはこのゲームでは致命的です。同じ試合が端末によって違う結果になってしまうからです（決定論）。だから仕様では、等間隔サンプリングによる近似を禁止しています。

DDA — 1 マスずつ、飛ばさずにたどる

正しいやり方は「通るマスを 1 つも飛ばさずに、順番にたどる」ことです。これを DDA（Digital Differential Analyzer）と呼びます。使っているのは Amanatides & Woo という人たちが 1987 年に発表した手順です。

考え方はとても単純です。

いまいるマスから、次にまたぐ境界線は縦か横かを比べて、近いほうへ 1 マス進む。

視線判定のDDAが、自分Sから敵Gへの直線が通るマスだけを1つずつ、飛ばさずにたどっていく5行5列の方眼の図

手順

自分のいるマスと、敵のいるマスを求める
進む向き（X は右か左か、Y は上か下か）を決める
次の縦の境界までの進み具合 $t_x$ と、次の横の境界までの進み具合 $t_y$ を求める
次をくり返す
- いまのマスが敵のマスなら → 見える
- いまのマスが木箱か鉄なら → 見えない
- $t_x \le t_y$ なら X 方向へ 1 マス、そうでなければ Y 方向へ 1 マス進む

「進み具合」 $t$ は、始点から終点までを 0 から 1 としたときの割合です。 $t_x$ と $t_y$ を比べて小さいほうへ進むので、先にまたぐ境界から順に処理されます。だから 1 マスも飛ばしません。

ここにも「同時」の問題がある

$t_x$ と $t_y$ が ぴったり等しくなることがあります。視線がマスの角をちょうど通るときです。

視線がマスの角をちょうど通るとき、X方向に進むかY方向に進むかで通るマスが変わる図

どちらへ進んでも幾何学的には正しいのですが、通るマスが変わります。だから、ここでも先に決めておきます。

跳弾の角衝突とまったく同じ考え方です。「どちらでもよい」場面に選択の余地を残さない、というのがこのエンジンの一貫した方針です。

安全側に倒す

ループには 64 回という上限があります。フィールドは 20 × 15 なので、まっすぐ端から端でも 35 マスほど。64 回あれば足ります。

それでも上限に達したときは、False（見えない）を返します。「分からないときは撃たない」ほうが、誤射より安全だからです。

計算の重さ

line_of_sight は TypeScript で書かれた組み込み関数ですが、呼ぶと 60 命令が命令数バジェットに加算されます。「組み込みだから無料」にはなっていません（計算量の話）。

実測すると、上の「見えているときだけ撃つ bot」は 1 tick あたり平均 113 命令でした。上限は 150,000 なので、まったく問題ありません。

書き方	1 tick の平均命令数
`line_of_sight` を毎 tick 1 回	113
毎 tick BFS で経路探索	1,157

視線判定は、経路探索より 10 倍ほど軽いと覚えておくとよいです。「まず見えるか調べて、見えないときだけ経路を探す」という順番が効きます。

def update(state):
    見える = line_of_sight(state.map.grid, state.me.x, state.me.y,
                           state.enemy.x, state.enemy.y)

    if 見える:
        # 見えているなら、まっすぐ狙えばよい
        want = angle_to(state.me.x, state.me.y, state.enemy.x, state.enemy.y)
        return {"drive": "stop", "steer": want, "fire": True, "barrier": False}

    # 見えないときだけ、重い経路探索を使う
    path = find_path_bfs(state.map.grid,
                         (state.me.grid_x, state.me.grid_y),
                         (state.enemy.grid_x, state.enemy.grid_y))
    if len(path) < 2:
        return {"drive": "stop", "fire": False, "barrier": False}

    nx, ny = path[1]
    want = angle_to(state.me.x, state.me.y, nx + 0.5, ny + 0.5)
    return {"drive": "forward", "steer": want, "fire": False, "barrier": False}

つぎに読む

見えないときにどう回りこむか → 経路探索と計算量
見えている敵に当てる → 偏差射撃
壁ごしに当てる → 跳弾のしくみ