2D迷路データとその解を自動生成する(2):「穴掘り法」による迷路データ生成

「どんな迷路を、どのようにつくるか」について、述べていきます。

ここでは、(1)大きな構造の生成、(2)実際のMapに与えるdata生成、(3)細部の構造の生成、という 3段階のうち、まずは「(1)大きな構造の生成」についてを解説します。

準備のために、2D座標空間上の点を表すPointクラスを用意します。

//点を表すクラス
Point = enchant.Class.create({
    initialize: function(){
     this.x = 0;
     this.y = 0;
     switch(arguments.length){
     case 1:
         this.x = arguments[0].x;
         this.y = arguments[0].y;
         break;
     case 2:
         this.x = arguments[0];
         this.y = arguments[1];
         break;
     }
    },

    toString: function(){
     return "("+this.x+","+this.y+")";
    }
});

では、大きな構造としての(見た目以前の)迷路を生成・表現するMazeクラスを実装していきます。

ここでは、迷路ゲームを作る場合に良く用いられている、「穴掘り法」と呼ばれるアルゴリズムを基本にしています。 この開発にあたっては、Ishida So氏の「迷路自動生成アルゴリズム」のページを参考にさせていただきました。併せて参照されることをおすすめします。

Maze = enchant.Class.create({
    /**
      @param {Number} mazeWidth 迷路全体の横幅
      @param {Number} mazeHeight 迷路全体の高さ
     @param {Number} complexity 迷路内の分岐の多さ
   */
    initialize: function(mazeWidth, mazeHeight, complexity){
     this.mazeWidth = mazeWidth;
     this.mazeHeight = mazeHeight;
     this.sx = Math.floor(rand(mazeWidth-4))+2;//スタート地点のx位置、迷路の左右端にならないように調整
     this.sy = Math.floor(rand(mazeHeight-4))+2;//スタート地点のy位置、迷路の上下端にならないように調整

     this.mazeData = new Array(mazeHeight); //迷路データを格納する配列
     this.route = []; // 迷路上のすべての「道」を格納する配列

     this.empty = 0;
     this.block = 1;

     this._createMaze(complexity); //迷路データの生成
    },

   /** 
     指定されたx,y位置に「道」を掘る
   */
    _dig: function(x, y){
     this.route.push(new Point(x, y));
     this.mazeData[y][x] = this.empty;
    },

    _createMaze: function(complexity){

           // 迷路の配列を、迷路外周(最上段・最下段・左端・右端)は「道」とし、
           // それ以外はすべて「壁」として初期化する。
           // 基本的に、「壁」を掘ることで迷路を作るので、
           // 迷路外周を「道」にしておけば、迷路外まで掘らずに済むのでアルゴリズムを単純化できる。

     for(var i = 0; i < this.mazeHeight; i++){
         var data = (i == 0 || i == this.mazeHeight - 1)? this.empty : this.block;//迷路の最上段と最下段は常に「道」とする
         var mazeRow = new Array(this.mazeWidth);
         mazeRow[0] = this.empty; //迷路の左端は常に「道」とする
         mazeRow[this.mazeWidth-1] = this.empty; //迷路の右端は常に「道」とする
         for(var j = 1; j < this.mazeWidth - 1; j++){
          mazeRow[j] = data;
         }
         this.mazeData[i] = mazeRow;
     }
     
     var direction = new Array(4);

     //「道」を掘るスタート位置
     var sx = this.sx;
     var sy = this.sy;

     //はじめに、スタート位置を掘る
     this._dig(sx, sy);

     for(var j = 0; j < complexity; j++){ //迷路内の分岐の回数だけ繰り返し
         var start = this.route[rand(this.route.length)]; //すでに掘ってある場所から任意の場所を選んで分岐の開始点を設定。
         sx = start.x;
         sy = start.y;

         while(true){
                        //「道」がループしないような「掘れる方向」をチェック。
                       // 堀った道が別の道に突き抜けないように、2つ先まで調べる。
          direction[0] =// 「上」方向には掘れるか？
          this.mazeData[sy-1][sx] != this.empty && amp;
              this.mazeData[sy-2][sx] != this.empty ;
          direction[1] =// 「右」方向には掘れるか？
          this.mazeData[sy][sx+1] != this.empty &&
              this.mazeData[sy][sx+2] != this.empty ;
          direction[2] =// 「下」方向には掘れるか？
          this.mazeData[sy+1][sx] != this.empty &&
              this.mazeData[sy+2][sx] != this.empty;
          direction[3] =// 「左」方向には掘れるか？
          this.mazeData[sy][sx-1] != this.empty &&
              this.mazeData[sy][sx-2] != this.empty ;

                        //穴掘り可能な方向の候補を配列に格納
          var candidate = [];
          for(var i = 0; i < 4; i++){
              if(direction[i]){
               candidate.push(i);
              }
          }
          if(candidate.length == 0){
                           //これ以上掘れない場所なので、穴掘り作業を中断。今回の開始点を穴掘り開始点の候補から削除。
              delete this.route[start];
              break;
          }

                        // 穴掘り可能な方向からひとつの方向をランダムに選ぶ
          switch(candidate[rand(candidate.length)]){
          case 0://「上」に掘る
              this._dig(sx, sy-1);
              sy -= 1;
              break;
          case 1://「右」に掘る
              this._dig(sx+1, sy);
              sx += 1;
              break;
          case 2://「下」に掘る
              this._dig(sx, sy+1);
              sy += 1;
              break;
          case 3:// 「左」に掘る
              this._dig(sx-1, sy);
              sx -= 1;
              break;
          }
         }
     }

     // 迷路の外周を壁で埋め直す
     for(var i = 0; i < this.mazeHeight; i++){
         this.mazeData[i][0] = this.block;
         this.mazeData[i][this.mazeHeight - 1] = this.block;
     }
     for(var j = 1; j < this.mazeWidth - 1; j++){
         this.mazeData[0][j] = this.block;
         this.mazeData[this.mazeWidth-1][j] = this.block;
     }
    },

    /** そこに壁があるかどうかを調べる
      @param {Number} x 調べる場所のx位置
      @param {Number} y 調べる場所のy位置
    */
    hitTest: function(x, y){
     return (0 <= y && y < this.mazeData.length &&
                0 <= x && x < this.mazeData[y].length &&
                this.mazeData[y][x] != this.empty);
    },

    ....略.....
});