BricRoboでブロック並べを解いてみる(1) – 迷路法とは

最近、水中ロボコンの開発にBricRoboというソフトを使いました! と書いたら、だんだんとFacebookやHPのアクセスが増えてきているので、ここらで、ロボット制御ではない分野で使うとどうなるか? という例を公開してみようかな、と。 じつは2016年のETロボコン(ロボットのソフトウェアコンテストがあるんですけど)のお題に、ブロック並べというのがありまして。 これ、真面目に考えるとどれぐらい手間が掛かるんだろうと試しに作ったことがありまして。走行経路を求めるのにBricRoboで解くとどんなふうにモデリングするのか、その事例です。
まず、最初にどんな方法で経路を解くかアルゴリズムを決める必要があるんですが、今回はやったことのあるやつで、電子回路の配線のアルゴリズムに使われる「迷路法」を採用してみることにします。
迷路法を知らない人は、うーん、どうしようっかなぁ。マインスイーパーみたいな感じで、始点からどんどん輪を広げていって、終点に到達したときの経路を反対に戻れば、それが最短経路ってやつなんですが。
ネットで検索しても、いい感じの図解が見つからないので、書いてみますか。
例えば、次の図のような迷路があったとします。赤が始点、青が終点。赤から青までの到達する最短経路を求めるとします。
1
赤の始点に0を書きます。上下左右にしか移動できないルールだとします。すると0の上下左右で空いているところに、+1した1を書き入れます。次に1の回りの上下左右で空いているところに、+1した2を書き入れます。これを青に到達するまでずっと続けると、青に到達したときには22が青に入ります。
2
今度は青の22から-1して21の場所を探します。探すときには順番を上下左右の順番に探すとしましょう。0になるまで探し続けると、その通ったルートが赤から青への最短ルートの反対向きということになります。
ということは、赤から青に行くときは、これを反対向きに進めば最短ルートで到達します。
3
このアルゴリズムは水面を輪が伝わって行くのに似ているので、水面法とか勝手に呼んでたんですけど、ネットでは迷路法って名前が付いてます。
ということで、くじけなければ、正月休みに最後のソースコード公開まで解説できると思いますけど、今日はここまで。
>>BricRoboでブロック並べを解いてみる(2) – ブロック並べ解法アプリ