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)

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です