今日はプロデルで迷路を自動的に作るプログラムを作ってみます。
迷路を作る方法にはいくつかのアルゴリズムがありますが、今回は「穴掘り法」で作ってみます。
壁を掘り進めて通路を作る
これから作る迷路は、横16マス、縦20マスに敷き詰めたコマの上に、壁で仕切って通路を作ります。左上をスタートにして、通路をたどって、右下のゴールを目指します。壁の仕切りをランダムに決めることで毎回ルートが異なる迷路を作ります。
まずは迷路の通路を表現する「迷路」という変数名の2次元配列を用意します。迷路を作るときは、各マスの上側と右側が壁である状態を初期状態にしておきます。なお、コマの下側と左側の壁は、上隣りまたは右隣りのコマの壁と同じなので考えなくてもOKです。
その上で、ゴールから乱数によって上側か右側のいずれかの壁を開けて、スタートまで逆方向に掘り進めていくという処理をします。この時、乱数で決めた壁の先がすでに掘り進めたマスの場合や、迷路の上下左右の端でこれ以上掘り進めない場合は、壁を壊さずに戻っていき、未開拓のコマを掘り進めます。
このような処理には再帰を使います。上記のルールを繰り返すことで結果的に、スタートからゴールまで正しくたどり着ける迷路を作ることができます。
迷路の壁を記憶する
「迷路」配列には、上側もしくは右側の壁が開いているかどうか、また、すでに掘り進めたマスかどうかを記憶しておきます。今回は、配列の要素に次のような3ビットのビット表現で記録した整数を記憶しておきます。
0ビット目: 0なら上側の壁なし。1なら壁あり
1ビット目: 0なら右側の壁なし。1なら壁あり
2ビット目: 0なら未開拓のコマ。1なら掘り進めたコマ
プロデルでは0bと付けた後にビット表現を書くことで2進数表現で値を指定できます。ビット表現は桁ごとに0または1だけを並べて表現します。例えば、0ビット目から2ビット目がすべて1の場合は、0b111などと表記します。0b111は10進数では4+2+1で7となります。
迷路の話に戻すと、例えば、上壁,右壁,掘り進めたかどうかの状態の組み合わせによって次のようなビット表現で配列に記憶します。
| 状態 | 2進数 | 10進数 |
|---|---|---|
| 上壁があり,右壁がない,掘り進めた | 0b101 | 5 |
| 上壁があり,右壁があり,掘り進めた | 0b111 | 7 |
| 上壁も右壁もない,掘り進めた | 0b001 | 1 |
格納された整数について、特定のビット目へ0か1を設定したり、0か1かを判断するためには「論理和」名詞手順または「論理積」名詞手順を使います。「論理和」はビット演算でのOR演算です。「論理積」はビット演算でのAND演算です。
ビット表現におけるOR演算とAND演算についての詳しい説明は割愛いたしますが、ここでは迷路のコマの表現に必要な部分だけを簡単に解説します。
迷路(木,林)=迷路(木,林)と0b100の論理和
と書くと、0b100(4)は2ビット目が1なので、OR演算すると特定のコマが2ビット目が1に変わります。つまり掘り進めたコマに変わります。
迷路(木,林)は、迷路(木,林)と0x101の論理積
と書くと、0b101(5)のAND演算ですので1ビット目が0に変わります。つまり右の壁を開けます。また、0b110(6)は0ビット目が0となり、AND演算で上の壁が開きます。
また、AND演算はビットが0か1かを調べるためにも使います。
もし迷路(木,林)と0b010の論理積が2なら
と書くと、迷路(木,林)の1ビット目が1の時だけ、0b010(2)となります。これで上の壁が開いているかどうかを判断できます。
ビット表現の利点
今回はビット表現で情報を記憶しましたが、プロデルはオブジェクト指向プログラミングができるので、実はコマの情報をオブジェクトで格納する方法がわかりやすいです。
ビット表現することの利点は、情報を記憶するために必要なメモリサイズを大幅に節約できる点です。現在のように十分なメモリを持っている環境では、わざわざビット表現で節約する方が煩雑となりますが、レトロゲーム機のような小さなコンピュータでは、メモリ消費を少なくするためにこのようなテクニックを多用していました。今でも組み込みコンピュータやICカードなどで情報を扱うときに使う機会があります。
今回はプロデルでも昔のようにビット表現で情報を扱う方法で作ってみました。実用用途を想定しているプロデルでは活用する機会があるはずです。
完成したプログラム
このような方法で記憶した迷路をキャンバスに描画します。それぞれのコマについて線図形で壁を描いていきます。
動作環境:プロデル1.9.1164
メイン画面を表示する
待機する
メイン画面とは
ウィンドウを継承する
はじめの手順
初期化する
ーー貼り付けた部品に対する操作をここに書きます
描画する
終わり
初期化する手順
ーー自動生成された手順です。ここにプログラムを書き加えても消える場合があります
この実質大きさを｛600,750｝に変える
この内容を「迷路」に変える
初期化開始する
キャンバス1というキャンバスを作る
その位置と大きさを｛0,46,600,554｝に変える
その自動更新を×に変える
そのドッキング方向を「全体」に変える
自動配置パネル1という自動配置パネルを作る
その位置と大きさを｛0,0,600,46｝に変える
その移動順を3に変える
そのドッキング方向を「上」に変える
生成ボタンというボタンを自動配置パネル1へ作る
その位置と大きさを｛3,3,112,34｝に変える
その内容を「生成」に変える
その移動順を2に変える
初期化終了する
この設計スケール比率を｛144,144｝に変える
終わり
+迷路
【木】と【林】から、迷路を、作る手順
迷路(木,林)=迷路(木,林)と0b100の論理和
((迷路(木,林+1)=3または迷路(木+1,林)=3または迷路(木,林-1)=3または迷路(木-1,林)=3))の間繰り返す
【方向】は、1から4までの乱数
もし方向が1かつ迷路(木,林+1)=3なら
迷路(木,林)は、迷路(木,林)と0b101の論理積
木と林+1から迷路を作る
他でもし方向が2かつ迷路(木-1,林)=3なら
迷路(木,林)は、迷路(木,林)と0b110の論理積
木-1と林から迷路を作る
他でもし方向が3かつ迷路(木,林-1)=3なら
迷路(木,林-1)は、迷路(木,林-1)と0b101の論理積
木と林-1から迷路を作る
他でもし方向が4かつ迷路(木+1,林)=3なら
迷路(木+1,林)は、迷路(木+1,林)と0b110の論理積
木+1と林から迷路を作る
もし終わり
繰り返し終わり
終わり
描画する手順
キャンバス1をクリアする
盤面余白=10
通路幅=20
【迷路サイズ:座標】は{16,20}
【スタート:座標】は{1,1}
【ゴール:座標】は{迷路サイズの横,迷路サイズの縦}
木を1から迷路サイズの縦+2まで増やしながら繰り返す
林を1から迷路サイズの横+2まで増やしながら繰り返す
もし木が1または林が1または木が迷路サイズの縦+2または林が迷路サイズの横+2なら
迷路(木,林)=15
そうでなければ
迷路(木,林)=3
もし終わり
繰り返し終わり
繰り返し終わり
ゴールの縦とゴールの横から迷路を作る
キャンバス1へ線を描く
その位置と大きさは｛盤面余白+通路幅,盤面余白+通路幅*2,0,(迷路サイズの縦-1)*通路幅｝
その線色を黒に変える
その太さを1に変える
キャンバス1へ線を描く
その位置と大きさは｛盤面余白+通路幅,盤面余白+(迷路サイズの縦+1)*通路幅,(迷路サイズの横-1)*通路幅,0｝
その線色を黒に変える
その太さを1に変える
木を2から迷路サイズの縦+1まで増やしながら繰り返す
林を2から迷路サイズの横+1まで増やしながら繰り返す
壁横は、(林-1)*通路幅+盤面余白
壁縦は、(木-1)*通路幅+盤面余白
もし迷路(木,林)と0b001の論理積が1なら //上が壁
キャンバス1へ線を描く
その始点は｛壁横,壁縦｝
その終点は｛壁横+通路幅,壁縦｝
その線色を黒に変える
その太さを1に変える
もし終わり
もし迷路(木,林)と0b010の論理積が2なら //右が壁
キャンバス1へ線を描く
その始点は｛壁横+通路幅,壁縦｝
その終点は｛壁横+通路幅,壁縦+通路幅｝
その線色を黒に変える
その太さを1に変える
もし終わり
繰り返し終わり
繰り返し終わり
キャンバス1を更新する
終わり
生成ボタンがクリックされた時の手順
描画する
終わり
終わり
実行画面
まとめ
今回は、迷路を自動的に作るプログラムを作りました。
迷路を作るだけでしたが、さらに迷路上に自分の位置や軌跡を表示する部分や経過時間を表示するプログラムも加えて、ちゃんと仕上げれば、立派な迷路ゲームになりそうですね。
今回は、迷路の情報をビット演算で効率よく記憶する方法が中心でしたが、迷路を作るアルゴリズムを知る上で再帰処理が必要です。再帰については、過去の記事で説明しています。ゲーム作りにはもちろん実用的なプログラミングでも必要な考え方ですので、もしわからない方はぜひ知っていただけたら嬉しいです。
関連記事
2次元配列や再帰については、過去の記事で取り上げています。
プロデルがはじめての方は、公式ブログのプロデルで始める日本語プログラミング言語入門も併せてご覧ください。