迷路を作るアルゴリズムは色々あるようですが、今回は穴掘り法（道延ばし法）と呼ばれるアルゴリズムを用いています。 このサイトに色々なアルゴリズムが分かりやすく書かれているので、そちらを参照することをおすすめします。
迷路は2次元平面上にあり、方眼紙の様な「マス」の集合だとします。 このとき、マスは「壁」か「道」のどちらかの役割を果たすものとします。 また、迷路の外側は全て道で埋め尽くされているとします。 そして、スタートからゴールへ続く道は1本のみとします。
- 迷路全体を壁にする。
- 迷路の外に接するマスを除いて、ランダムに選んだ1マスを道にする。
- そこから道をランダムに（進もうとしている方向のマスの上下左右1マスが道でなければ）延ばす。
- 3を可能な限り繰り返す。
- 迷路の外側を除いて、既に道になっているマスからランダムに1マス選ぶ。
- 3-5を可能な限り繰り返す。
ステップ6まで実行したら、後は迷路の外に接するマスの中からスタートとゴールにするマスを適当に選べば完成です。
全てJavaを用いて実装しています。 主要な変数の説明は以下の通りです。
- int mazeSize: 生成される迷路（正方形）の1辺の長さ。
- boolean[][] wall: 迷路全体の状態。trueで壁を、falseで道を表す。
- int row, col: 「道にしようとしているマス」の行と列。
- Stack rowStack, colStack: 「既に道にしたマス」の行と列を積んだスタック。
- int usrRow, usrCol: 「ユーザーが現在いるマス」の行と列。
- int goalRow, goalCol: 「ゴールがあるマス」の行と列。
「既に道にしたマス」をスタックに積むことで、分岐しうる道はもれなくチェックすることができます。
- Windowsで気軽に遊べるようにGUIにしてexeファイルにまとめたい。
- 見た目がごちゃごちゃしてるので、直線の道を増やしたい。
- 現状だとwsadキーを押した後にエンターキーを押す必要があるので、wsadキーだけで動かしたい。
- ハイスコアとかを表示したい。