迷路を通り抜けて目的地まで最短距離で進む その２

前回のあらすじ：

Yマサキ君「レールが敷いてあれば・・・」
ワシ「そうか、レールを敷けばいいんや！」


というわけでレールを敷く話ですｗ
迷路の中を手探りで進むのではなく、あらかじめ通る道を決めてやればいいんだ、という発想です。
このためには目的地である旗の場所から道を作って行くことになります。
まず旗がぽつんとあるとします。

この旗の回り８方向のマス目のどこかに戦車がいるとすると、戦車は旗の方向に１歩進むことになります。ですので旗の回りにこんなレールを敷きます。

旗から２回り離れたマス目はどうかというと、旗を目指すのではなく、ここで置いた赤の矢印を目指すレールにします。例えば左上の矢印を目指すレールはこうなります（水色の矢印）。

ミソはゴールである旗を目指すのではなく、に常に１つ隣の（１回り内側の）目標に向かうレールを敷くということです。こうすることでプログラムはとっても単純になります。ぐるぐるループを回すだけになりますので。

障害物の所は除外して、移動できるマスについてのみ順に全てこうやってレールを敷いていくとこうなります。

まるで磁力線ですが、まさに磁石に引かれるようにマップのどこに戦車を配置しても旗のところに吸い寄せられて行きます。

この程度のロジックだとよっぽどマップが広大でない限り処理速度は問題にならないので、動く敵の位置に応じて毎回レールを敷きなおしても大丈夫です。そうしてやれば敵を追いかけるロジックにそのまま適用できます。何れにしても戦車は単に現在地にある矢印を読み取ってその方向に移動するだけです。
（註：実際には戦車は前進と後退しかできないので、読み取った矢印の向きによっては移動ではなく旋回するケースもあります。具体的に言うと戦車の向きと読み取った矢印の向きが一致していなければ旋回処理です。）

矢印の向きを逆にすれば敵から逃げるロジックにもなります。


ところで「最短距離で進むは言いすぎじゃね？」と思ったなら、はい、その通りです。レールを敷設するロジックがいい加減だと多少遠回りしてしまうケースも出てきます。
ただ、本当に最短距離で走らせようとするとコードがめんどくさいことになりますので、戦車戦ロボコンではいい加減なコードのままでやりました。それでも旗取りで負けたことはないです。（砲撃で負けたことはありますがｗ）

壁に当たってから方向転換するロジックだと概ね下図の赤線の軌跡での移動になります。
レール敷設方式だと青線の軌跡になります。

後になってググってみたら、迷路を解くアルゴリズムの考え方は基本はこんな感じみたいです。もう少し複雑でしたが、移動結果はほぼ同じようでした。