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

下のスクリーンショットは昔作った戦車ゲームです。

障害物のあるフィールドで、敵を撃破するか、敵よりも先に旗を取るかすれば勝ちです。逆に敵の弾に当たったり、敵に旗を取られると負けです。

ゲームと言ってはいますが、実際にはプレイヤーはキーボードもマウスも使いません。「戦闘開始」ボタンを押した後はただ眺めるだけです。

一体これは何かというと、いろんな人のプログラム同士を戦わせるものなんです。あらかじめ戦車のプログラムを作っておいて、それを実行します。ロボットコンテストみたいなものですね。

この昔作ったロボコン旗取りゲーム用の戦車アルゴリズムは迷路を解くアルゴリズムになっています。例えば下図のような地形でも戦車はちゃんと旗までの最短距離を移動します。

スタート時に壁を挟んで旗のある方を向いて配置していますが、

無駄な動きをすることなくちゃんと迂回して旗を目指します。

今作ってる「砲撃者たちへ」も戦車ですし、この戦車好きめ！な感じですがｗ、今回の話は「砲撃者たちへ」とは直接関係はありません。

単に障害物を避けながら目的地まで進む、という考え方の一例としてこの旗取りゲームの方法を紹介するのも面白いかなと思った次第です。

世の中にはこの手のアルゴリズムはいっぱいありますが、私の方法はいたってシンプルです。シンプル故に力技というのもいつものことですｗ

実は最初は誰もが最初に考えるであろう、まず進んでみて行き詰まったら別の行き方を模索するという方法で考えていました。で、自分が行き詰まりましたｗ
１手や２手戻ってやり直すぐらいならともかく、地形によっては何十手も戻ってやり直す必要があります。例えばこんな袋小路に入ってしまった場合などですね。

難しいロジックは理解できないんで、なんかもっと単純に解決できんもんかなー、世の中もっとシンプルに物事は解決するはずや！と悩んでたら、当時一緒に悩んでいたYマサキ君が「レールを敷いたみたいに旗まで寄り道せずにまっすぐ移動できたらいいんですけどねー」と。

「それや！Yマサキ君！！レールを敷けばいいんや！！」

まさに　ユーリカー！　な状態でしたｗ　裸で家に飛んで帰って、いや別に風呂に入っていたわけではないんですが、それぐらいの勢いで飛んで帰って、あっという間にコーディングできてしまいました。
それほどシンプルｖ

さて、その方法とは？　
勿体付けるほどのもんではないんですが、長くなったので次回に。