探索と地図作成

ランダムにさまようロボットでは、あまり得点できません。このページでは、さまよう段階から計画的な探索へ進む方法を紹介します。これは発展させるためのアイデアで、完全な解答ではありません。

自分の位置を知る

タイルの幅は 12 cm なので、GPS の位置からタイルがわかります。スタートの位置はワールドごとに違うので、すべてをスタートから測りましょう。

TILE = 0.12
startX, _, startZ = gps.getValues() # At the start of the game

def currentTile():
    x, _, z = gps.getValues()
    return round((x - startX) / TILE), round((z - startZ) / TILE)

ノート

GPS がなくても車輪のエンコーダーとジャイロで位置を推定できますが、誤差が積み重なります。

見たものを記憶する

タイルの辞書を用意して、各タイルについてわかっていること（どの辺に壁があるか、床は何か、訪れたかどうか）を記録しましょう。

tiles = {}
tiles[(0, 0)] = {"walls": {"N": False, "E": True, "S": False, "W": True}, "floor": "start", "visited": True}

エリア 2 と 3 では、壁が 4 分の 1 タイルの位置にあることがあるので、タイルだけではすべてを表せません。地図を 4 分の 1 タイルの解像度で保存したり、LiDAR の点群を使ったりすると、これに備えられます。

行き先を決める

壁に沿って進むだけではいけません。それでは、トークンの得点が高いフローティングタイルにはたどり着けません。よく使われる方法は次のとおりです。

1. 現在のタイルから、間に壁のない隣のタイルを一覧にします。
2. 未訪問のタイルがあれば、そこに進みます。
3. なければ、幅優先探索で、未訪問の隣接タイルを持ついちばん近いタイルを見つけ、そこに進みます。
4. そのようなタイルがなくなるか、時間が少なくなったら、同じ方法でスタートに戻ります。

穴は壁として扱いましょう。沼地は時間がかかり、同じ沼地に入るたびにさらに多くかかるので、価値があるときだけ入りましょう。

予想外のことに対処する

• 競技進行停止: ロボットは最後のチェックポイントに移動されます。L メッセージを受け取ったら、自分の位置を更新しましょう。
• 時間: G で残り時間を問い合わせましょう。地図を送ってスタートに戻るのに十分な時間を残してください。
• ノイズ: センサーにはノイズがあるので、壁やトークンがあると判断する前に、複数の読み取り値を比べましょう。

タイルから地図行列へ

地図行列は、タイルあたり 4 セルに 1 を足した大きさです。地図の r 行 c 列のタイルについて:

要素	行列での位置（行、列）
4 や 5 などの床のマーク	行 4r + 1 と 4r + 3、列 4c + 1 と 4c + 3
北の壁	行 4r、列 4c 〜 4c + 4
西の壁	列 4c、行 4r 〜 4r + 4

地図はどこから始めてもかまいません。Erebus はスタートタイルを使って行列の位置を合わせ、4 通りの回転を試します。行列のすべての値は地図作成のルールで説明しています。それから地図を提出しましょう。

サンプルワールドでテストしましょう。正解は地図作成のルールに載っています。結果は、コントロールウィンドウの履歴に Map Correctness として表示されます。