本連載の40回目で迷路ゲームを作ってみました。スプレッドシートに迷路データを作り、迷路の中をスクロールして楽しめるものでした。とは言え、迷路データを作るのはなかなか大変です。そこで、今回はプログラミングで自動的に迷路を生成してみましょう。

  • 迷路を自動生成してみよう

迷路の自動生成の方法

古くからゲームの世界では迷路の自動生成の手法が行われてきました。ゲームを面白くするためだけでなく、迷路のマップを保存する記憶容量を節約するためだったりすることもあったようです。面白いですね。

さて、迷路を作成する手法にはいくつかの方法があります。ここでは最も単純に迷路を作成する「棒倒し法」を紹介します。棒倒し法を利用した迷路の生成はとても単純です。次の4ステップで作成できます。

（1）迷路を全部通路として初期化する。
（2）迷路の外周を壁にする。
（3）迷路全体に1マスおきに壁を配置する
（4）上記で壁を配置した場所ごとにランダムに上下左右いずれかの方向に壁を作る

それほど難しくありませんが、言葉だけだと分かりづらいので、ステップごとに作成の様子を確認してみましょう。

まず、手順（1）で迷路のマップとして、21×21のマスを用意します。ここでは、通路を0、壁を1として表現する二次元配列変数を作ります。当然ですが、以下のように21×21のマスが全部通路となります。

  • 迷路を初期化したところ

    迷路を初期化したところ

続いて、手順（2）で迷路の外周に壁を作ります。

  • 迷路の外周に壁を配置したところ

    迷路の外周に壁を配置したところ

そして、手順（3）で2マスおきに壁を1つ配置します。

  • 迷路の2マスおきに壁を1つ配置

    迷路の2マスおきに壁を1つ配置

最後に手順（4）で2マスおきに、上下左右のいずれかに壁を一つ配置します。すると、迷路が作成できます。

  • 迷路が作成できたところ

    迷路が作成できたところ

プログラムを作ってみよう

なんとなく作り方が分かったでしょうか。実際にプログラムを作って確認してみましょう。なでしこ簡易エディタにアクセスしたら、以下のプログラムを書き込んで実行してみましょう。

21の迷路作成して迷路表示。

●(列数の)迷路作成とは
　　# 迷路データを全部0で初期化 --- (*1)
　　迷路は[]
　　Yを0から(列数-1)まで繰り返す
　　　　迷路[Y] = []
　　　　Xを0から(列数-1)まで繰り返す
　　　　　　迷路[Y][X] = 0
　　　　ここまで
　　ここまで。
　　# 外周を壁にする --- (*2)
　　Nを0から(列数-1)まで繰り返す
　　　　迷路[N][0] = 1
　　　　迷路[N][列数-1] = 1
　　　　迷路[0][N] = 1
　　　　迷路[列数-1][N] = 1
　　ここまで。
　　# 2マスに1つ壁を配置する --- (*3)
　　Yを2から(列数-3)まで繰り返す
　　　　Xを2から(列数-3)まで繰り返す
　　　　　　もし(X%2=1)または(Y%2=1)ならば続ける。
　　　　　　迷路[Y][X] = 1
　　　　　　# 上下左右のいずれかを壁にする --- (*4)
　　　　　　（4の乱数）で条件分岐
　　　　　　　　0ならば、迷路[Y-1][X] = 1💧。
　　　　　　　　1ならば、迷路[Y+1][X] = 1💧。
　　　　　　　　2ならば、迷路[Y][X-1] = 1💧。
　　　　　　　　3ならば、迷路[Y][X+1] = 1💧。
　　　　　　ここまで。
　　　　ここまで
　　ここまで。
　　それは迷路
ここまで。

●(迷路を)迷路表示とは # --- (*5)
　　壁幅=13
　　列数＝迷路の要素数。
　　Yを0から(列数-1)まで繰り返す
　　　　Xを0から(列数-1)まで繰り返す
　　　　　　V = 迷路[Y][X]
　　　　　　灰色に線色設定。
　　　　　　もしV＝0ならば、白色に塗り色設定。
　　　　　　違えば、茶色に塗り色設定。
　　　　　　[X*壁幅, Y*壁幅, 壁幅, 壁幅]に四角描画。
　　　　ここまで。
　　ここまで。
ここまで。

すると、プログラムを実行するたびに異なる迷路を生成します。

  • 簡易エディタで実行してみたところ

    簡易エディタで実行してみたところ

少し長いのですが、少しずつ見ていけば、それぞれの部分はそれほど難しくありません。ゆっくり見ていきましょう。

まず(＊1)の部分では迷路データを0(通路)で初期化します。(＊2)の部分では迷路の外周を1(壁)にします。

そして、(＊3)の部分ですが、ここでは2マスに1度だけ実行するように条件をつけて繰り返し実行します。条件に注目すると「(X%2=1)または(Y%2=1)」となっています。％の記号は割り算の余りを求める演算子です。2で割って余りが出る、つまりXやYの値が奇数であればそれ以降の処理を実行しないという意味になります。そのため、(＊4)の処理は2マスに 1度実行されます。4の乱数を生成し、その結果によって上下左右のいずれかを1(壁)にします。

この迷路生成の手法が「棒倒し法」と呼ばれる理由がこの(＊4)の部分です。2マスに1度、上下左右のいずれかに棒を倒すように壁を作っています。

作った迷路データでゲームが遊べるようにしよう

なお、ここで作った迷路は21×21の小さな迷路です。奇数の値を指定しさえすれば、どれだけでも大きな迷路を作れます。「21の迷路を作成」の部分を「55の迷路を作成」と変えると、55×55の大きな迷路を作成します。

さらに、せっかく作った迷路をCSVデータで出力するようにも工夫してみましょう。ほとんど同じプログラムになるので、こちらに作成したプログラムを配置しました。ここで作成したデータを40回目の迷路ゲームに貼り付ければゲームとして遊ぶことができます。気になった迷路が自動生成できたら貼り付けて遊んでみましょう。

  • 55×55の迷路を生成したところ

    55×55の迷路を生成したところ

まとめ

以上今回は自動で迷路を生成する方法を紹介しました。それほど難しくないのでちょっとした頭の体操になったでしょうか。実際に答えを見ずに自分でプログラムを作ってみると楽しいと思います。

ただし、今回紹介した棒倒し法で作る迷路には欠点もあります。必ずゴールにたどり着けるとは限らないということです。なぜならランダムに壁を配置しているだけだからです。あまり確率は高くありませんが、袋小路を作ってしまう可能性があります。

その点を考慮しつつ、連載40回目で紹介したように、壁やゴールの位置を微調整すると楽しいゲームになると思います。試してみてください。

自由型プログラマー。くじらはんどにて、プログラミングの楽しさを伝える活動をしている。代表作に、日本語プログラミング言語「なでしこ」 、テキスト音楽「サクラ」など。2001年オンラインソフト大賞入賞、2004年度未踏ユース スーパークリエータ認定、2010年 OSS貢献者章受賞。技術書も多く執筆している。直近では、「シゴトがはかどる Python自動処理の教科書(マイナビ出版)」「すぐに使える!業務で実践できる! PythonによるAI・機械学習・深層学習アプリのつくり方 TensorFlow2対応(ソシム)」「マンガでざっくり学ぶPython(マイナビ出版)」など。