初めに

先日、小学４年生と１年生のいとこ達が遊びに来ました。
体を使った遊びは中々にしんどいため、ゲームでも作ってあげたらおとなしくしてくれるかな、と思いCUIで動く迷路ゲームを作成しました。
結果的には、いとこ達よりも彼らの母親の方がハマってしまい、結局ドッタンバッタン大騒ぎを止めることはできませんでした。

環境

Linux Mint 18 'Sarah' MATE 64-bit
Java 1.8.0_131
Google Chrome 61.0.3163.79（Official Build）（64 ビット）

迷路生成アルゴリズム

迷路を作るアルゴリズムは色々あるようですが、今回は穴掘り法（道延ばし法）と呼ばれるアルゴリズムを使います。
このサイトに色々なアルゴリズムが分かりやすく書かれているので、そちらを参照することをおすすめします。

前提

迷路は2次元平面上にあり、方眼紙の様な「マス」の集合だとします。
このとき、マスは「壁」か「道」のどちらかの役割を果たすものとします。
また、迷路の外側は全て道で埋め尽くされているとします。
そして、スタートからゴールへ続く道は1本のみとします。

穴掘り法（道延ばし法）

このアルゴリズムは、人間が手で迷路を作るやり方と似ています。
なので、道のランダム度合いは高くなります。
また、直線が少なくなりやすいので、大きな迷路を生成した場合、ごちゃごちゃした見た目になります。
以下にアルゴリズムの内容を示します。

迷路全体を壁にする。
迷路の外に接するマスを除いて、ランダムに選んだ1マスを道にする。
そこから道をランダムに（進もうとしている方向のマスの上下左右1マスが道でなければ）延ばす。
3を可能な限り繰り返す。
迷路の外側を除いて、既に道になっているマスからランダムに1マス選ぶ。
3-5を可能な限り繰り返す。

ステップ3だけちょこっと解説します。

■: 壁
□: 道
○: 進もうとしているマス
ー: 壁でも道でもどっちでも良い

ある道から左方向へ進もうとしているとします。
この時、その道から見て左側にあるマスの上下左右1マスが以下の様になっていれば、左に道を延ばすことができます。

ー　■　ー
■　○　□　←ココから道を延ばそうとしている
ー　■　ー

ところが、先ほどの図で壁だったマス（例えば○の上のマス）が1つでも道になってしまった場合、左に道を延ばすことができなくなります。
何故なら、「今延ばしている道」と「○に隣接している道」がつながってしまうからです。
2つの道がつながることを許してしまうと、ループするような道が生まれてしまい、スタートからゴールへの道が1本ではなくなってしまいます。

ー　□　ー
■　○　□　←ココから道を延ばそうとしている
ー　■　ー

ステップ6まで実行したら、後は迷路の外に接するマスの中からスタートとゴールにするマスを適当に選べば完成です。

実装

全てJavaを用いて実装しています。
先ほど説明した迷路生成アルゴリズムの部分を以下に示します（コード全部を見たい人はここ）。
なお、先ほどの説明で示した各ステップに対応する部分をコメントで示しています。

Maze.java

// 新しく迷路を作るメソッド
static void createMaze() {
    // [ステップ1]初期化
    for (int i = 0; i < mazeSize; i++) {
        for (int j = 0; j < mazeSize; j++) {
            wall[i][j] = true;
        }
    }

    // [ステップ2]ランダムに開始位置を選ぶ（1 〜 mazeSize - 2）
    Random rnd = new Random();
    row = rnd.nextInt(mazeSize - 2) + 1;
    col = rnd.nextInt(mazeSize - 2) + 1;
    wall[row][col] = false;
    rowStack.push(row);
    colStack.push(col);

    boolean continueFlag = true;

    // [ステップ6]以下、wall[][]全体を埋めるまで繰り返し
    while (continueFlag) {

        // [ステップ3,4]上下左右のいずれかに限界まで道を伸ばす
        extendPath();

        // [ステップ5]既にある道から次の開始位置を選ぶ（0 〜 mazeSize - 1）
        continueFlag = false;

        while (!rowStack.empty() && !colStack.empty()) {
            row = rowStack.pop();
            col = colStack.pop();

            if (canExtendPath()) {
                continueFlag = true;
                break;
            }
        }
    }
}

主要な変数の説明は以下の通りです。

int mazeSize: 生成される迷路（正方形）の1辺の長さ。
boolean[][] wall: 迷路全体の状態。trueで壁を、falseで道を表す。
int row: 「道にしようとしているマス」の行。
int col: 「道にしようとしているマス」の列。
Stack rowStack: 「既に道にしたマス」の行を積んだスタック。
Stack colStack: 「既に道にしたマス」の列を積んだスタック。

主要なメソッドの説明は以下の通りです。

extendPath(): 先の説明におけるステップ3, 4を行う。
canExtendPath(): 「道にしようとしているマス」が本当に道にできるかどうかを判定する。

「既に道にしたマス」をスタックに積むことで、ステップ3を適用しうる道はもれなくチェックすることができます。

実行結果

実行結果はこんな感じです（mazeSize = 30）。

左下の「**」がプレイヤー、右上の「GO」がゴールを表しています。
wsadキーでプレイヤーを上下左右に動かすことができます。
ゴールすると、賞賛と共にクリアタイムが表示されます。
実際にやってみると複雑に分岐しているので結構難しいです。

JavaScriptとHTMLでの実装

ブラウザで遊べるようにJavaScriptとHTMLでも実装してみました。
基本的にはJavaでの実装と同じです。
迷路の描画方法はこのサイトを~~パクりました~~参考にさせてもらいました。

ブラウザ版の実行結果

実行結果はこんな感じです（mazeSize = 50）。

左下の青いブロックがプレイヤー、右上の赤いブロックがゴールを表しています。
矢印キーでプレイヤーを上下左右に動かすことができます。
ゴールすると、賞賛と共にクリアタイムがダイアログに表示されます。
上部の入力欄から迷路の大きさを自由に変更できます。
スマホでの動作は考えていません。
~~ちなみにここから遊べます。~~

今後の課題

~~Windowsで気軽に遊べるようにGUIにしてexeファイルにまとめたい。~~時代はWebらしいのでブラウザで遊べるようにしました。
~~見た目がごちゃごちゃしてるので、直線の道を増やしたい。~~ごちゃごちゃしてる方が迷路として面白い気がするのであえてこのままで。
~~現状だとwsadキーを押した後にエンターキーを押す必要があるので、wsadキーだけで動かしたい。~~ブラウザ版は矢印キーで遊べるようにしました。
ハイスコアとかを表示したい。

参考URL等

自動生成迷路　http://www5d.biglobe.ne.jp/stssk/maze/make.html
GitHub　https://github.com/hey-cube/maze
[JavaScript] 不思議なダンジョン迷路をHTML+JavaScriptで作る　http://www.yoheim.net/blog.php?q=20151202
~~HeyCubeの迷路　http://www.coins.tsukuba.ac.jp/~s1411396/index.html~~

最後に

いとこ達との別れ際、「あのゲームはもうできないの？」と聞かれました。
そこで、ウェブ上でダウンロードして遊べるようにすることを約束しました。
という訳で、いずれこの迷路はダウンロードして遊べるようにします。

自分が作ったものに興味を示してくれる人がいると、やっぱり嬉しいですね。

（2017/09/08追記）
ダウンロードして遊ぶという方式にはしませんでしたが、いとこ達が自宅で遊べるようにブラウザ版を作成しました。

（2018/03/24追記）
当時はJavaScriptなんも分からん状態だったのですが、今見返すと酷いですね・・・。
アルゴリズムはともかく、JavaScriptのコードは参考にしないでください。

小学生のいとこのためにJavaで作った迷路ゲームを簡単に解説する

初めに

環境