前回記事では、迷路の自動生成の様々なアルゴリズムを紹介しました。
「棒倒し法」を使って迷路を自動生成するプログラムを、Scratchで作っていきたいと思います。
今回は、Scratchでのプログラミングの前に、迷路の作り方の手順を確認していきます。
迷路ができるまでの3ステップ
キャンバス（2次元配列）を用意する
まずは、迷路全体を構成する「2次元配列（マス目）」を作ります。 この時、全体の幅（縦と横のマス数）は「5以上の奇数」にします。そして、一番外側のマス（外周）をすべて「壁（■）」にし、内側を「通路（□）」にしておきます。
（例：幅7、高さ7の配列の場合）
■■■■■■■← 外周は壁
■□□□□□■← 内側は一旦
■□□□□□■すべて通路
■□□□□□■
■□□□□□■
■□□□□□■
■■■■■■■
基準となる「棒」を配置する
次に、外周の内側に、基準となる壁（＝倒す前の棒）を1マスおきに配置します。
■■■■■■■
■□□□□□■
■□◆□◆□■←柱
■□□□□□■
■□◆□◆□■←柱
■□□□□□■
■■■■■■■
棒を倒して壁を作っていく
ここからが迷路づくりの本番です！
立てた内側の棒を順番に見ていき、「上下左右」のいずれかランダムな方向にパタンと倒して、新しい壁を作ります。
ただし、適当に倒すと道が塞がってしまうため、2つの重要なルールを守る必要があります。
⚠️ 重要なルール
1行目以外は「上」に倒してはいけない！
一番上の行にある棒(▲)は、上下左右どこに倒してもOKです。しかし、2行目以降の棒（◆）は「下・左・右」の3方向のどれかにしか倒せません。
すでに壁がある方向には倒してはいけない！
倒そうとした方向にすでに別の棒が倒れていて「壁」になっていた場合、重ねて倒すことはできません。別の方向を選び直します。
図解で見る「倒し方」の具体例
実際にルールを守って棒を倒していく流れを見てみましょう。
1行目の棒を倒す
1行目の棒（▲）は「上」に倒してもOKです。 左上の棒は「上」、右上の棒は「左」にランダムに倒したとします。
■■■■■■■
■□●□□□■←上に倒れた
■□▲●▲□■←左に倒れた
■□□□□□■
■□◆□◆□■
■□□□□□■
■■■■■■■
2行目以降の棒を倒す
2行目の棒（◆）です。
ルールにより「上」には倒せません。
左下の棒は「右」に倒してみましょう。
■■■■■■■
■□●□□□■
■□▲●▲□■
■□□□□□■
■□◆●◆□■←右に倒れた
■□□□□□■
■■■■■■■
重なりを防ぐ（ルールの適用）
最後に残った右下の棒です。
「上」には倒せません。
また、すぐ左のマスには先ほど倒した壁がすでにあるため、「左」にも倒せません。
したがって、「下」か「右」のどちらかに倒します（今回は下に倒します）。
■■■■■■■
■□●□□□■
■□▲●▲□■
■□□□□□■
■□◆●◆□■
■□□□●□■←下に倒れた
■■■■■■■
すべての棒を倒し終わったら、迷路の完成です！
ルール「上に倒すのは1行目だけ」を無視すると・・・
もし、このルールを無視してすべての棒を上下左右ランダムに倒してしまうと、迷路の中に「絶対にたどり着けない謎の小部屋」ができてしまうことがあります。
どういうことか、図解で見てみましょう！
失敗のシミュレーション
内側に4本の棒（柱）が立っている状態からスタートします。
■■■■■■■
■□□□□□■
■□◆□◆□■←柱
■□□□□□■
■□◆□◆□■←柱
■□□□□□■
■■■■■■■
1行目の棒を倒す（ここはルール通り）
左上の棒を「右」に、右上の棒を「下」に倒したとします。
■■■■■■■
■□□□□□■
■□◆●◆□■←右に倒した
■□□□●□■←下に倒した
■□◆□◆□■
■□□□□□■
■■■■■■■
2行目の棒を倒す（右下を左に倒す）
右下の棒を左に倒します。ここまではルール通りです。
■■■■■■■
■□□□□□■
■□◆●◆□■
■□□□●□■
■□◆●◆□■←左に倒す
■□□□□□■
■■■■■■■
ルールを無視してみる（左下を「上」に倒す）
ルールを無視して、左下の棒を「上」に倒してしまいます。
すると、どうなるでしょうか…？
■■■■■■■
■□□□□□■
■□◆●◆□■
■□●×●□■←上に倒す
■□◆●◆□■
■□□□□□■
■■■■■■■
図の真ん中にある「×」のマスに注目してください。
四方をぐるっと壁に囲まれてしまい、外から絶対に中に入れない、完全に閉じ込められた孤立空間ができてしまいました！
ついでに言うと、道の部分もぐるっと一周できるループ状になってしまい、迷路とは言えない形になってしまっています。
迷路づくりの世界では、すべての道がどこかで繋がっていて「無駄な空間がない」状態を「完全な迷路（パーフェクト・メイズ）」と呼ぶそうです。
2行目以降の棒が「上」に倒れると、1行目の棒が作った壁と手をつなぐ形になってしまい、このような「輪っか（ループ）」や「孤立した部屋」が発生しやすくなります。
だからこそ、「上に倒していいのは1行目（一番上の行）だけ！ 2行目以降は下か左か右！」というルールを守ることで、道が途切れたり閉じ込められたりしない、美しい完全な迷路を作ることができるのです。
おわりに
迷路の自動生成の仕組みが今回分かったので、次回はいよいよ、Scratchでプログラミングに落とし込んでいきたいと思います！
ゲームや仕組みをプログラミングするとき、いきなりブロックを積み上げるより、「どのように組み立てていくか」をしっかり設計してから進めると、プログラミングがスムーズに進みます。
これから何か作ろう！と思ったとき、「何を作るか」「どんな仕組みにするか」「ゴールはどこか」を決めて進めてみましょう！きっともっと楽しくものづくりができると思います！
