« BricRoboでブロック並べを解いてみる(3) - アプリの仕組み | トップページ | あけましておめでとうございます »

BricRoboでブロック並べを解いてみる(4) - 迷路法をブロック並べに応用

前の章では複雑に線が入り組んだBricRoboモデルが出てきました。これに画面の絵を当てはめると次のよな図になります。ブロック並べのフィールドそのものですが、黒線は移動できる経路を示したもの。本来は一番右端に縦に黒線が1本ありますが、最後はそこに抜け出たいので、その場所をゴールとして、右側へ抜ける4本の経路を引いておきました。(これはあとでちょっと問題があるんですが)

Photo

そして、この配置は次の図のように、一番最初に迷路法を説明したときの四角が連なった迷路とみなすことができますよね。だから、この図を元にして、どうやってブロック並べを解いていくか、例を使って説明していきます。

Photo_2


最初はこんな配置だとします。一番左にローバー、4つのブロックは緑、黒、青、赤。みんな違う色のサークルの上にあります。-1の数字は、その場所になにも距離の値、迷路法で数字を入れていないことを表しています。

Photo_4


まずはスタート地点であるローバーの位置に0を入れます。

Photo_3


次に0の回りに1を入れていくのですが、黒線で繋がった場所にしか動けないので、黒線で0と繋がった枠に1を入れるとこんな感じ。

Photo_5


次に1と黒線で繋がった枠に2を入れます。するとこんな感じ。青ブロックのところに2が入りました。

Photo_6


次に2と黒線で繋がった枠に3を入れます。ここで注意しないといけないのは、青ブロックは要するに壁なので、青ブロックにある2は無視すること。そうしないと壁を突き破って進んで行けることになるので。

Photo_7


次に3と黒線で繋がった枠に4を入れます。緑ブロックも黒ブロックも3が入ってますが、それは壁なので伸びません。下の赤いサークルの3だけが右に伸びて4が入ります。

Photo_8


次に4と黒線で繋がった枠に5を入れます。赤ブロックにも5が入って、ブロックは全部埋まりました。もうブロックまでの経路はわかったのですが、一律の動作にしたいので、枠に数字が入れられなくなるまで続けます。

Photo_9


次に5と黒線で繋がった枠に6を入れます。

Photo_10


次に6と黒線で繋がった枠に7を入れます。あれ?右側の楕円のサークルに7が入ってしまいました。これがまだ細工が足りないところで、ここはゴールのサークルなんですが、特別扱いしてないので7が入ってしまいました。つまり経路の1つとして使ってしまったわけ。これはあとで条件を加えれば回避できるので、とりあえずほっときます。

Photo_11


次に7と黒線で繋がった枠に8を入れます。これで-1の枠はなくなり全部に値がはいりました。-1が消えたということはローバーがいけない場所はないということです。

Photo_12


さて、ローバーから一番近いブロックはどれかというと、数字を0から1つずつあげてブロックのある場所を探すと、それは2の入っている青ブロック。青ブロックの2から数字を1つずつ小さくしながら枠を辿るとローバーのところまで戻ってこれます。これがローバーから青ブロックまでいく経路。

Photo_13


経路が分かったので、青ブロックまで移動。

Photo_14


次は青ブロックを運ぶ場所を探します。やり方は一緒で、ローバーのいる位置を0として、これまでと同じ方法で数字を書き込んでいきます。するとこんなふうに枠に値がハマって、青サークルで一番数字が小さいところが青ブロックを運ぶ場所で、1から値を小さくしながら辿るとローバーのところに戻ってこれるので、これが青ブロックを運ぶ経路なわけ。

Photo_15


これで青ブロックの移動終了。あと緑と赤を運ばないと。

Photo_16


これまでと同じようにして、ローバーのいる場所に0をいれて、そこから全部の枠に数字を入れていきます。そうするとこんな感じになります。

Photo_17


黒以外で、ブロックとサークルの色が合っていないので、数字が一番小さいのは2の赤ブロック。次はこれを運ぶために経路は2から数字を小さくしながら戻るとこんな経路。

Photo_18


赤ブロックまでローバーを移動します。

Photo_19


ローバーのいる場所を0としてまた数字を埋めていきます。赤サークルで一番数字が小さいのは2の場所。そこが赤ブロックを運ぶ場所で運搬ルートです。

Photo_20


赤ブロックを運びます。だんだん面倒くさくなってきたね。あと緑ブロックだけ。

Photo_21


同様にしてローバーの場所に0を入れて回りを埋めていきます。この時、緑ブロックまでのルートは2つあります。4,3,2,と辿ってくると、2から1へは2通りあります。どちらも0まで戻ってこれるのですが、どちらを選ぶかは数字の探す順番できまります。いまのプログラムは下側が選ばれました。 で、緑ブロックまでのルートが見つかりました。

Photo_22


緑ブロックまでローバーを移動させます。

Photo_23


また、ローバーのいる場所を0にして回りの数字を埋めていきます。緑サークルで一番小さい数字の場所が緑ブロックを運ぶところ。経路も分かります。

Photo_24


緑ブロックを緑サークルまで運びます。

Photo_25


さあ、ブロックは全部運び終わったので、ゴールまでの経路を求めます。ローバーの場所を0として回りの数字を埋めていきます。するとゴールまでのルートが求まります。

Photo_26


ローバーをゴールまで移動させます。 これで終了。長かったね。

Photo_27


やることは同じで、

1.ローバーの場所から数字を埋めて、一番近いブロックを探す。
2.ブロックまで移動する。
3.ブロックの位置から数字を埋めて、一番近い同じ色のサークルを探す。
4.サークルまでブロックを移動する。

これを繰り返して、動かすブロックがなくなったら、最後はゴールまで経路を探して出ていく。
ローバーをターンさせたりブロックの向こう側に更に進めたり、そういう制御の難しさはぜんぜん考慮してないけど、一応、迷路法を使ってブロック並べは解けることは分かりました。

次は、数字を埋めたり、経路を探したりするのに、サークルに機能を持たせて、それをどうやって駆動して全体を動かしていくのか、の話ですかね。


>>BricRoboでブロック並べを解いてみる(5)

|

« BricRoboでブロック並べを解いてみる(3) - アプリの仕組み | トップページ | あけましておめでとうございます »

ETロボコン」カテゴリの記事

コメント

コメントを書く



(ウェブ上には掲載しません)




« BricRoboでブロック並べを解いてみる(3) - アプリの仕組み | トップページ | あけましておめでとうございます »