2015/12/28更新

[JavaScript] 不思議なダンジョン迷路をHTML+JavaScriptで作る

このエントリーをはてなブックマークに追加            

こんにちは、@yoheiMuneです。
今日は、生成するたびに変化する迷路をJavaScriptで作ってみたいと思います。

画像


完成版はこちらです

今回作成した迷路は、以下のGithubにアップしています。気になった方はご参照いただけたら幸いです。

ソースコード

- maze.html
- maze1.js


サンプルアプリケーション

迷路 http://yoheim.net/work/01_maze/maze.php



迷路の作り方

迷路の作り方はいろいろとあるみたいですが、今回は比較的簡単な「棒倒し」というアルゴリズムでの迷路作成を行いました。
棒倒しの考え方については以下のサイトがわかりやすかったので、そちらをご参照ください。

- 迷路自動生成アルゴリズム



迷路の作り方(JavaScript編)

上記の内容をHTMLとJSで表現したいと思います。JavaScriptについては150行もないくらいでできてしまいます。
<!-- html -->

<!-- 迷路を表現するエリアを作る -->
<div id="maze"></div>

<!-- 迷路を描画する -->
<script>
    var maze = new Maze(20);
    maze.create({algorithm: Maze.ALGO.STICK});
</script>
// JavaScript
(function () {

    // 配列をシャッフルする
    function shuffle (o) {
        for(var j, x, i = o.length; i; j = Math.floor(Math.random() * i), x = o[--i], o[i] = o[j], o[j] = x);
        return o;
    }

    /**
        迷路を表現するクラス
    */
    window.Maze = function (size) {
        // 壁と通路の関係上、サイズは奇数にしとく
        this.size = (size % 2 === 0 ? size + 1 : size);
        this.box = [];
        this.$maze = document.querySelector("#maze");
    };

    /**
        アルゴリズムタイプ
    */
    Maze.ALGO = {STICK: 1};

    var p = Maze.prototype;

    /**
        迷路を表示する
    */
    p.show = function () {
        var snipet = '';
        for (var i = 0; i < this.size; i++) {
            for (var j = 0; j < this.size; j++) {
                if (this.box[j][i] === 0) {
                    // 壁
                    snipet += '<div class="w"></div>';
                } else {
                    // 通路
                    snipet += '<div class="p"></div>';
                }
            }
        }
        this.$maze.innerHTML = snipet;
        this.$maze.style.height = (this.size * 10) + 'px';
        this.$maze.style.width  = (this.size * 10) + 'px';
    }

    /**
        迷路を作る
    */
    p.create = function (options) {
        options = options || {};
        if (options.algorithm === Maze.ALGO.STICK) {
            this._createByStick();
        }
        this.show();
    }

    /**
        迷路を作る(棒倒し)
    */
    p._createByStick = function () {

        // 初期化
        // まずは壁と通路を交互に作成する
        this.box = [];
        for (var i = 0; i < this.size; i++) {
            var row = [];
            this.box.push(row);
            for (var j = 0; j < this.size; j++) {
                // 最初の行と最後行は壁
                if (i === 0 || (i + 1) === this.size) {
                    row.push(0);
                // 最初の列と最後の列も壁
                } else if (j === 0 || (j + 1) === this.size) {
                    row.push(0);
                // 奇数行は全部通路
                } else if (i % 2 === 1) {
                    row.push(1);
                // 偶数行は壁と通路を交互に配置
                } else {
                    // 壁と通路
                    row.push(j % 2);
                }
            }
        }

        // debug
        // ここでreturnすれば、棒倒し前の状態を見ることができる
        // return;

        // ここから壁倒しで迷路を作る
        for (var r = 0; r < this.box.length; r++) {
            // 最初と最後の行は対象外
            if (r === 0 || (r + 1) === this.box.length) {
                continue;
            }
            // 壁がある行のみを対象
            if (r % 2 === 1) {
                continue;
            }
            // 行を取り出す
            var row = this.box[r];

            // 最初の行のみ、上下左右倒してOK(重なるのはNG)
            var direction = ['top', 'bottom', 'left', 'right'];
            if (r >= 4) {
                // 最初以外は、上には倒しちゃだめー
                direction = direction.slice(1);
            }

            for (var i = 0; i < row.length; i++) {
                // 端っこは対象外
                if (i === 0 || (i + 1) === row.length) {
                    continue;
                }
                // 壁のセルのみを対象に処理する
                if (i % 2 === 0) {
                    // 棒を倒す方向をランダムに並べる
                    direction = shuffle(direction);
                    // ランダムにした方向で1つずつ棒を倒してみて、重ならなければOK
                    // 重なる場合は(breakしない)、次の方向に棒倒しを試みる
                    for (var j = 0; j < direction.length; j++) {
                        if (direction[j] === "top") {
                            if (this.box[r-1][i] === 1) {
                                this.box[r-1][i] = 0;
                                break;
                            }
                        }
                        if (direction[j] === "left") {
                            if (this.box[r][i-1] === 1) {
                                this.box[r][i-1] = 0;
                                break;
                            }
                        }
                        if (direction[j] === "right") {
                            if (this.box[r][i+1] === 1) {
                                this.box[r][i+1] = 0;
                                break;
                            }
                        }
                        if (direction[j] === "bottom") {
                            if (this.box[r+1][i] === 1) {
                                this.box[r+1][i] = 0;
                                break;
                            }
                        }
                    }
                }
            }
        }
    }
})();
こんな感じで棒倒しの迷路を作ることができました。比較的少量のコードでこういうものが作れるのって、フロントエンド技術の強みだなぁと思う今日この頃です。



最後に

今日はHTML+JavaScriptで不思議なダンジョン(=毎回変わる迷路)を作る方法をブログに書きました。今回は棒倒しを使いましたが時間があれば他のアルゴリズムも使ってみたい次第です。
ところで今回急に迷路を作った理由は、ゲームを作りたいわけではなく、機械学習(その中でも強化学習)で迷路を解くプログラムを書きたくて、それが解く迷路を作ってみた次第でした。ということで次のブログでは、機械学習を用いて迷路を自動的に解くことについて書きたいと思います。

最後になりますが本ブログでは、機械学習・Python・フロントエンドなどを中心に情報を発信しています。気になった方はぜひ、RSSTwitterをフォローして頂けますと幸いです ^ ^。

最後までご覧頂きましてありがとうございました!





こんな記事もいかがですか?

RSS画像

もしご興味をお持ち頂けましたら、ぜひRSSへの登録をお願い致します。