FC2ブログ

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

迷路探索 左手法

こんにちは!

今週から迷路探索について書いていきます。
いよいよこのシリーズにも終わりが見えてきました。

さて、マイクロマウスの迷路探索では必要不可欠な要素がいくつかあります。
迷路を解くアルゴリズム、そして「スタート」と「ゴール」の認識です。

初めてマイクロマウスに挑戦する人はどうやってスタートとゴールを認識しているか、ということも分からないと思うのでそこから話を始めます。

クラシック競技では18cm×18cmを1区画として、縦16横16区画の計256区画があるということが既知の情報です。
これを上から眺めたとき、各区画は2次元の座標で表すことができます。

つまり、横軸をx、縦軸をyとすれば、角に当たる座標は、(x,y)=(0,0)、(0,15)、(15,0)、(15,15)というように表すことができます。

この時、例えば機体が南向きに進んでいるとします。
①(3,8)座標から前進した→進む先の座標は(3,7)
②(3,8)座標から右折した→進む先の座標は(2,8)

このように、現在の座標向いている方角、そして前進・右折・左折・反転のどの動作をしたかによって、座標を更新することがゴール認識への第一歩です。

プログラムもここの記述が最も苦戦するでしょう。
分かりやすいのは下線を引いた3つの条件から座標を更新するように記述していくことだと思いますが、工夫できることは多々あり、例えば向いている方角をビットシフトで処理するとif文が1/4になります。(私もバグが怖くてまだできていない…)

私の場合ここでバグが大量に発生しました。
2次元配列を用意して(map[16][16]とでもしましょうか)、向いている方角と行う動作で条件分岐させたのですが、配列のアンダーフロー・オーバーフローを除く処理を書いてなくて大変な目にあいました^^;
比較の時に、map[x-1][y]などを使うときは、その前にif(x!=0)などを入れましょう


とりあえず、ここまでで座標の認識ができるようになったとしましょう。
プログラムは大変ですが機体を走らせてモチベーションを維持しつつ頑張るのです。

座標の認識ができるようになったら、if(現在座標がゴール座標)のようにゴール処理をすればゴールできるようになります。
そして、ここで登場するのが左手法です。
左手法を使う目的は座標の認識がうまくいっているということを知るためです。このアルゴリズムは「なるべく左に行く」という簡単なものなので、座標の認識ができればゴール処理にたどり着けるでしょう。いきなり上位のアルゴリズムを動かそうとすると、アルゴリズムのバグなのか座標認識ができていないのか…と迷走することになるので、左手法でうごかしてアルゴリズムが正しければゴールできるという前提を獲得しておきましょう。

さ、左手法の記事ではなかった気がしますが今週はここまでです!
次週は無駄なくゴールまで探索する優秀なアルゴリズムの足立法について見ていきましょう。
ではでは($・・)/~~~

コメントの投稿

非公開コメント

時計
カテゴリ
最新記事
12月14日開始
RSSリンクの表示
リンク
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。