こんにちは、しゅうです。今回はパンではなく自作麺を作ってみました。細く切るのが難しく、二郎感が出ました笑ちなみにメンマと味玉も手作りしましたっ
前回まで行ったことは、以下の三つです。
- Pi:Co Classic3の組み立て
- プログラムの書き込み
- センサとタイヤの調整
そして、前回の記事の最後に今までの調整を終えたところで左手法で走らせてみました。今回は迷路解析に用いられる手法について解説いたします。
迷路解析手法
迷路を解く手法は複数ありますが、今回は三つ挙げます。前回行った左手法、拡張左手法、そして足立法です。
左手法
初めて迷路に挑戦する時、皆さんはどういう風にゴールまでたどり着こうと試みますか？闇雲に走り回るといずれはゴールするかもしれませんが、非常に効率が悪くなってしまいます。そこで、効率を上げるために壁に左手(右手でも大丈夫)を当てながら歩いていくといずれ出口にたどり着きます。次の図にその過程を示します。ここではスタートは左下にあり、ゴールは右上にあります。経路は赤い矢印で表現されています。
サンプルプログラムにはこの左手法がモード1に書き込まれています。ただし、次の図のようにゴールが中央にある場合はゴールにたどり着けない可能性が大きいです。
ここで拡張左手法が役に立ちます。
拡張左手法
この手法は、一度通った道や行き止まりなどを記録し、仮想壁を設置します。次の図でその様子を示します。緑色の太線が仮装壁を表しております。
これにより、左手法では走破できなかた迷路も攻略できるようになりました。
足立法
この手法では、スタート地点とゴール地点が最初から分かっていることが前提になります。即ち、常にゴールに向かって走り、袋小路や既に通った道にも対応可能です。さらに、この手法に置いてはスタート地点から現在地までにかかった歩数も記録します。
ここで記録された歩数は、歩数マップと呼ばれるものとして記録されます。この歩数マップを用いることで、ゴールまでの最短経路も算出することができます。
実はこれを自動運転などの技術に用いて、「A*(エースター)探索」とも呼ばれています。
まとめ
今回は迷路を解くための手法を説明しました。これらのアルゴリズムは、Pi:Co Classic3のSampleProgramに含まれております。search.cというファイルに書かれているのでみてみてください。
次回はタイヤ周りの調整（再び！）と音階の鳴らし方について解説します。