コンテンツにスキップ
CodeTank Arena ドキュメント

経路探索と計算量

あなたの担当　この章は、bot の中で使う計算の説明です。使うだけなら → 見えない敵を探す

壁にさえぎられて敵が見えないとき、回りこむ道を探すのが経路探索です。 このゲームには 2 つの道具が用意されています。

path = find_path_bfs(state.map.grid, (2, 3), (17, 12))    # 幅優先探索
path = find_path_astar(state.map.grid, (2, 3), (17, 12))  # A*

どちらも返ってくるのは マスの並びです。

[(2, 3), (3, 3), (4, 3), (4, 4)]   # 最初は自分のマス、最後がゴール

たどり着けないときは 空のリスト [] が返ります。 必ず len(path) を見てください。

使う

Section titled “使う”

path[0] は自分がいまいるマスなので、進むべきは path[1] です。

経路をたどって近づく
def update(state):
    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": True, "barrier": False}


    nx, ny = path[1]
    # マスの中心を狙う（+0.5 を忘れると、マスの角へ向かってしまう）
    want = angle_to(state.me.x, state.me.y, nx + 0.5, ny + 0.5)
    return {"drive": "forward", "steer": want, "fire": True, "barrier": False}

BFS と A* のちがい

Section titled “BFS と A* のちがい”
find_path_bfsfind_path_astar
見つける道最短最短
探しかた近いマスから全方向へ広げるゴールに近づきそうな方を先に試す
広げるマスの数多い少ない
1 マスあたりの手間軽い重い

どちらも最短経路を見つけます。 ちがうのは探しかただけです。

BFS — 波紋のように広げる

Section titled “BFS — 波紋のように広げる”

スタートから「1 歩で行けるマス」「2 歩で行けるマス」…と順に広げます。 水面に石を落としたときの波紋のイメージです。

ゴールに当たった時点で止まるので、その道が最短だと保証されます。

広げる順番は 右 → 下 → 左 → 上 に固定してあります。 順番を変えると、同じ長さの道が複数あるときに別の道が返ってしまうからです。 ここも「どちらでもよい」場面を作らないための決めごとです。

A* — ゴールの方角を当てにする

Section titled “A* — ゴールの方角を当てにする”

A* は「ここからゴールまで、少なくともこれくらいはかかるはず」という見積もりを足して、 見込みのよいマスから先に調べます。見積もりにはマンハッタン距離（縦横の歩数）を使っています。

そのぶん、広げるマスの数は BFS より減ります。

「組み込みだから速い」は成り立たない

Section titled “「組み込みだから速い」は成り立たない”

ここがこのゲームでいちばん面白いところです。

find_path_bfs は Python ではなく TypeScript で書かれています。 ふつうなら「組み込み関数なので一瞬。使い放題」となるはずです。

このゲームでは、そうなっていません。

これはわざとです。 組み込みが無料だと、「毎 tick 全部探し直す」書き方と「1 度探して覚えておく」書き方の差が どこにも表れません。計算量という考え方が学べなくなります。

測ってみる

Section titled “測ってみる”

このページのコードを実際に 4 試合走らせて、1 tick あたりの命令数を測りました。

書き方1 tick の平均いちばん重い tick
毎 tick BFS で探し直す1,1571,795
毎 tick A* で探し直す8942,568
10 tick に 1 回だけ BFS（あとは使い回す）2131,847
経路探索なし（line_of_sight だけ）113113

読みどころが 2 つあります。

1. A* は平均では軽いのに、いちばん重い tick は BFS より重い。 探すマスは減るのですが、この実装は「未処理リストからいちばんよいものを選ぶ」のに リストを端から端まで調べています。リストが長くなると、1 回の取り出しが高くつきます。 「探すマスが減っても、1 マスあたりが重くなれば意味がない」—— アルゴリズムの教科書に必ず出てくる話が、そのまま数字になっています。

2. 覚えておくだけで 5 倍以上軽くなる。 経路は 1 tick（0.1 秒）で大きくは変わりません。 10 tick に 1 回だけ探し直して、あとは覚えておいた道を使えば、平均 1,157 → 213 になります。

経路を覚えておく
path = []
残り = 0


def update(state):
    global path, 残り


    # 10 tick に 1 回だけ探し直す
    if 残り <= 0 or len(path) < 2:
        path = find_path_bfs(
            state.map.grid,
            (state.me.grid_x, state.me.grid_y),
            (state.enemy.grid_x, state.enemy.grid_y),
        )
        残り = 10
    残り = 残り - 1


    if len(path) < 2:
        return {"drive": "stop", "fire": True, "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": True, "barrier": False}

global は「この変数は関数の外のものを使う」という宣言です。 これを書かないと、path は毎回まっさらに戻ってしまいます。

バジェットは 150,000

Section titled “バジェットは 150,000”

1 回の update で使える命令数の上限は 150,000 です。

上の表を見返すと、いちばん重い書き方でも 2,568。上限の 2% も使っていません。

超えてしまったときは、その tick は前回の入力が維持されます。 1 試合で 3 回までは許され、4 回目で行動停止になります。

使い分けの目安

Section titled “使い分けの目安”

敵が見えているならline_of_sightだけでよく、見えないときは道が変わらなければBFSで経路を覚えておき、毎tick正確に出したいならBFSかA*を使うという使い分けの図

まず line_of_sight、見えないときだけ経路探索。 この順番にするだけで、たいていの場面は軽くなります。

つぎに読む

Section titled “つぎに読む”