キミも未来のトビラをひらこう!!

公式LINEで相談♪

programmingSchool

できたを育むプログラミングスクール

レッスン21迷路生成アルゴリズムを学ぼう!

チャプター01はじめに

このチャプターのポイント

迷路を生成するアルゴリズムを学ぼう

今回は迷路生成アルゴリズムを学んでいくよ。 アルゴリズムとはコンピューターの計算方法のことだよ。 コンピューターが迷路を正しくつくることができるように、プログラムしていくよ。 今回のレッスンでは、迷路生成アルゴリズムの基本「棒倒し法」について学ぶよ。

何もないところから、複雑な迷路をつくるアルゴリズムを考えていくよ。 大きく2つの処理が必要だね。 1つ目は、外壁と等間隔で並ぶ内壁を描く処理 2つ目は、内壁を上下左右の1方向にランダムにコピーする処理スタンプ機能をつかって、効率よく描いていくよ。 また、同じ迷路でも効率の悪いいらない壁ができないようにするために、壁のできる方向を制御することがポイントだよ。 今回は1つのアルゴリズムについて学ぶけど、他にも有名な迷路アルゴリズムがあるよ。 では、実際に作っていこう!

チャプター02背景・スプライトを設定しよう

このチャプターのポイント

背景とスプライトの初期状態を設定しよう

・背景・スプライトの設定を確認しよう

このチャプターでは、背景とスプライトの設定を確認していくよ。

もしスプライトを消してしまった場合は…

自分で正方形を描くよ。 8×8の正方形のスプライト3つを描くよ。 まずは黒い正方形スプライトwallを描くよ。 wallは日本語でという意味だよ。 新しいスプライトボタンを描くをクリックして、ビットマップモードになっていることを確認してね。 なっていなければ、ビットマップに変換をクリックすればいいよ。 1600%にまで拡大して、黒で8×8の大きさになるように正方形を描こう。 正方形のサイズはコスチュームの下に数字で描かれているから確認しながら描き進めてね。 描けたら、赤でmeを、青でgoalを描いてね。

消していない場合はここから

次に、meとgoalの位置を整えていくよ。 動かすスプライト、meの位置をきめよう。

ゴールのスプライトとなるgoalの位置を決めよう。

ここまで設定できたら、動作を確認しよう。 グリーンフラッグを押して、meとgoalが配置されていればOKだよ。 黒い壁のスプライトについては次のチャプターで制御していくよ。 3つのスプライトが描けたら、もう一度サイズを確認しよう。 コスチューム名の下の数字が8かける8になっているか確認してね。 ここまで、みんなの画面でもやってみてね。

チャプター03迷路の外壁がいへきをつくろう

このチャプターのポイント

繰り返し処理を組み合わせ正方形を長方形状に並べよう

・スタンプを使いスプライトを複製しよう

このチャプターでは、迷路の外壁を描く機能を作っていくね。 スタンプという機能をつかっていくよ。 スタンプとは文字通り、スプライトをスタンプのように見た目をコピーする機能だよ。

似たような機能として、クローンがあるので違いについて説明するね。 スタンプの機能は、クローンとは違って見た目上同じものをつくるだけでスクリプトで動かすことはできないよ。 ペンと同じで消すブロックを用いて消すしか方法がないから注意してね。 処理の流れについて説明するよ。

まず、wallのスプライト定義ブロック「外壁」をつくろう。 画面を描画せずに実行するにチェックを入れてね。

壁の最初の位置を指定して、ペンから[全部消す]ブロックをつなげておこう。 毎回、前回書いたものをリセットするためだね。

つぎにスタンプを押しながら右と下にずれていく処理を作ろう。 壁の正方形が8かける8の正方形なので、9ずつずれながら繰り返しスタンプを押せばいいね。 x方向に9は右へずれること、y方向に-9は下にずれることを意味しているよ。

次に、複製をして左にずれる処理、上にずれる処理を作ろう。 複製したブロックの値を変更することをわすれないようにしよう。

グリーンフラッグがクリックされた時に外壁が描かれるようにしよう。

動作確認で必要になるかもしれないので、qキーを押したときにスタンプが消える処理を作っておこう。

ここまで完成したら、動作を確認してみよう。 グリーンフラッグを押して、外壁が長方形の並びで描かれていればOKだよ。 ここまで、みんなの画面でもやってみよう!

チャプター04迷路の内壁ないへきをつくろう

このチャプターのポイント

繰り返し処理を組み合わせ、迷路の内壁をつくろう

・内壁を等間隔とうかんかくに配置しよう

このチャプターでは、「棒倒し法」と呼ばれる迷路のアルゴリズムをつくっていくよ。 まずは、壁を等間隔にくいのように描く処理を作っていこう。

処理の流れについて説明するね。 右にずれながらスタンプを押す処理を、下方向にもずれながら繰り返せばいいね。 まずは、外壁をかきおわって左上にあるwall下に18、右に18ずらす処理を作ろう。

定義ブロック「内壁」を用意して右にずれスタンプを押す回数は24回、それを下にずれながら17回繰り返すよ。 24回の繰り返しの中が右にずれながら押す処理、その1回が終わる度にx座標を-211に戻し、さらにy座標を下に18ずらす処理を17回繰り返しているんだね。

繰り返し回数について補足しておくね。 外壁は横方向にスタンプを50回押したので、51個並んでいることになるよ。 両端の2個を除いて、51-2=49がスタンプを押す前の白いマスの数だね。 道と壁で2マスセットなので、49割る2つまり24あまり1の24が繰り返しの処理の回数となるよ。 縦方向も同じように考えられるね。 あまりの1は左端にも道が必要だからだね。 むずかしいので、今すぐ理解できなくても大丈夫だよ。

最後に定義ブロック「内壁」グリーンフラッグがクリックされたときの処理につなげておこう。 ここまで完成したら、動作を確認してみよう。 外壁の内側に同じ間隔で、壁が並んで描かれて入ればOKだよ。 ここまで、みんなの画面でもやってみよう!

チャプター05迷路の内壁を完成させよう

このチャプターのポイント

迷路を生成するアルゴリズム「棒たおし法」の処理をつくろう

・棒倒し法を理解しよう

このチャプターでは、等間隔に並んだ壁の間を壁で埋めていくよ。

処理の流れについて説明するね。 前のチャプタで描いた全ての壁に対して、上下左右のどちらかに壁を書き足していくよ。 それだけでは、迷路として不完全なので、調整を加えていくよ。

まずは、内壁を書き終わった段階では、右下にいるwallのスプライトx座標を-211、y座標を151にする処理をつなげておこう。

この後、繰り返し処理の中でつかう定義ブロック「上下左右にスタンプ」をつくろう。 スタンプを押す方向をランダムにするための変数[乱数]をつくろう。 値は1~4の数字と対応させるよ。 時計周りで1が上、2が右、3が下、4が左と対応させるよ。

まずは左右にスタンプを押す処理を作っていくよ。 乱数はスタンプを押す処理の前で決定されているとして、[もし~なら]で条件を分岐させていけばいいね。 たとえば、右方向なら、9右にずれて、スタンプを押し、9左にずれて元の場所に戻ってくる処理となっているよ。 左右方向だから、x座標のブロックをつかっていることを間違えないように注意してね。

さらに、上下の処理もつくろう。 縦方向なので、y座標のブロックをつかうことをまちがえないようにしようね。 乱数に応じて、上下左右にスタンプを押す処理は定義ブロックとなったので、繰り返しの処理を作って行こう。

等間隔に並んだ壁と同じ繰り返し回数となるね。 まずは24回繰り返し、その作業を17回繰り返す処理としよう。

処理の中身は、乱数を作り、定義ブロックでスタンプを上下左右のどこかに描く。 続けて、x座標を18だけ右にずれる。 これを24回繰り返したのちに左に戻り、下にずれる。 あとは繰り返しだね。

ここまで完成したら、動作を確認してみよう。 上下左右に壁が描かれ、迷路のように壁が描かれて入ればOKだよ。 時間がかかるようであれば、ターボモードで試して見てね。 さあ!ここまで、みんなの画面でもやってみよう!

チャプター06動かせるスプライトをつくろう

このチャプターのポイント

迷路を移動するスプライトを、制御ブロックを用いて実現しよう

・スプライトの移動を制御しよう

このチャプターでは、描かれた迷路をスプライトがうごいていけるようにしていくよ。 制御のブロックをつかって上下左右にmeのスプライトをうごかせるようにしよう。

まずはグリーンフラッグが押された時の最初の位置をきめよう。 処理の流れについて説明するね。 上下左右のキーに応じて、それぞれその方向に進む処理をつくるよ。 押した方向に黒い壁がある場合には反対方向に移動させ、見た目上は移動がキャンセルされたという処理を4つ作っていくよ。

上下左右の動きをつくろう。 黒色にぶつかったときは、反対の座標分だけ動くようにすることで、動きを制限しよう。

色の指定は、次のように設定しよう。

  • 色:0
  • 鮮やかさ:0
  • 明るさ:0

ここまで完成したら、動作を確認してみよう。 グリーンフラッグを押して、迷路が描かれたあと、赤いmeのスプライトが上下左右に動かせること、壁の方向には動かせないことが確認できればOKだよ。 ここまで、みんなの画面でもやってみよう!

チャプター07迷路の精度せいどを高めよう

このチャプターのポイント

棒たおし法のアルゴリズムを理解して、迷路の完成度を高めよう!

制約条件せいやくじょうけんもうけて迷路の精度を高めよう

このチャプターでは、迷路の微調整びちょうせいをしていくよ。 迷路になっているけど、よく見ると無駄むだな壁があるんだ。

たとえば、ロの字型になってしまっているところもあるね。 また、3個縦や横に続いているだけで孤立こりつしてしまっているものがあるね。 どちらも、行き止まりが少なくなるため、迷路を簡単かんたんにしてしまうことになるね。 これらを解消かいしょうしていくよ。 処理の流れについて説明するね。 大きく分けて2つの制限をかけていけばいいよ。

  1. すでに壁が描かれている場合は、壁を描かずに、別の方向に描く処理
  2. 上下左右の1方向、今回は上方向には壁を描かない処理

1.の処理で3個左右や上下に並ぶ壁は解消されるね。 3個の孤立がなくなるということは、全ての壁が孤立しなくなるということだね。 2.の処理によって、ロの字も解消されるね。 4個の等間隔の壁からロの字をつくろうと思うと、少なくとも1つの壁は上に描く必要があるからだよ。 24回繰り返し壁を上下左右に描くとき、ある場所で右、次に左方向に描くという処理を制限したいね。 前回どちら向きに描いたのかを記録するための変数「前回」をつくろう。

早速処理を作っていこう。 乱数がつくられたあとに、前回が右の2、今回が左の4ではないまで乱数を作る処理を入れる。 さらに、上下左右のどの方向に描いたかを記録するための処理を入れよう。

[~ではない]に入る条件は、前回が2かつ今回の乱数が4の場合だね。

繰り返す処理は、乱数を生成する処理だね。

ここで一度動作を確認してみよう。 左右方向に3個孤立するブロックはなくなったね。 でも、まだロの字は出現してしまうね。 これを解消していこう。 さらに乱数の範囲を2~4に変更してみよう。

ここまで完成したら、動作を確認してみよう。 ロの字がなくなり、全ての壁が、外壁にまでつながっていることが確認できればOKだよ。 このままだと、一番上に壁がないね。 これを解消していこう。 一度、24回繰り返しの処理を外そう。

外したブロックを複製して、[もし~なら,でなければ]にそれぞれはめて、先の処理は、乱数の範囲を1から4に変更しよう。 変更したら、[24回繰り返す]の中に戻そう。

条件は[y座標=151]ならを、変数「前回」は、繰り返し処理に入る前に初期化0にしておこう。 ここまで完成したら、動作を確認してみよう。 1番上にも壁が描かれることが確認できればOKだよ。 ここまで、みんなの画面でもやってみよう!

チャプター08クリア時間を表示しよう

このチャプターのポイント

迷路を解いた時間を記録して、ゴールした時に表示させよう

・タイマーブロックを用いてクリア時間を表示させよう

このチャプターでは、迷路を解くのにかかった時間をクリア時間として計測する仕組みをつくっていくよ。 タイマーを利用するよ。

処理の流れについて説明するね。 タイマーをリセットして、meとgoalの位置に到達したときにタイマーの値をクリア時間とすればいいね。 ゲームをクリアした瞬間のタイマーの値となる、変数「クリア時間」をつくろう。 goalのスプライトにタイマーをリセットして、そのあとはずっとの処理を入れておこう。

繰り返す処理は、meのスプライトまでの距離が0になるまでクリア時間をタイマーにしつづけよう。

距離が0になったら、このスクリプトを止めよう。

迷路が全面にあるため、クリアした時にだけ表示させよう。 ここまで完成したら、動作を確認してみよう。 クリア時間を迷路の邪魔にならない左下に配置して確認してね。 グリーンフラッグを押したらクリア時間の表示は消えること、ゴールをするとクリア時間が表示されることを確認できればOKだよ! みんなの画面でもやってみよう!

チャプター9最後に

・まとめ

最後に、このレッスンで学習したことをおさらいしてみよう。 このレッスンで、迷路を生成するアルゴリズムについては理解できたかな? 複雑そうな迷路も単純なルールを決めることで生成できるんだね。 おさらいしておこう。

まず、外壁と等間隔に並ぶ内壁を描いたね。 これはもう繰り返し処理に慣れてきたみんなにとっては、解説を見なくてもできるようになっているかな? 次に、上下左右にランダムに壁を描く仕組みを作ったね。 処理の流れが分かりやすくなるように、定義ブロックにしたことも大事なポイントだね。 最後に、すでに描かれているところがランダムに選択された場合はやり直しとなる処理を作ったね。 [~まで繰り返す]をつかうと、ある条件を満たすまでずっと繰り返させることができるんだったね。

今回は「棒倒し法」を学んだよ。 他にもいくつか方法があり、方法によって迷路の特徴が異なってくるんだ。 興味があれば自分で迷路生成アルゴリズムについて、学んでみよう! このレッスンを終えたみんなは、Scratch以外のプログラミング言語も始める準備が整ってきていると言えるね! Scratchをマスターして、他の言語にも挑戦していこう!