2D迷路データとその解を自動生成する(5):「ポテンシャル法」で迷路を解くための実装

先に「2D迷路データとその解を自動生成する(2):「穴掘り法」による迷路データ生成」のエントリで説明したMazeクラスに対して、_initAnswerメソッドを追加します。

このメソッドを実行することで、

• stepMap 迷路上のそれぞれの地点がスタート地点から何歩で到達できる場所なのかを示す2次元配列
• stepList スタート地点からの同じ距離ごとに、迷路内地点のリストをまとめた2次元配列
• pathStepTotal この迷路上に「道」のセルがいくつあるかを数える変数

というようなインスタンス変数が作成され、利用できるようになります。

_initAnswerのコードは以下のとおりです。

_initAnswer: function(){

    var COLLISION = 0;
    var NOT_INITIALIZED = -1;

    // この迷路に「道」のセルがいくつあるかを数える変数
    this.pathStepTotal = 0;

    // stepMap として、迷路上のそれぞれの地点がスタート地点から何歩で到達できる場所なのかを示す2次元配列を作成する。
    // 迷路外周(最上段・最下段・左端・右端)と、迷路上の「壁」の部分に「COLLISON(衝突)」の値、
    // 迷路上の「道」の部分には「未初期化状態」の値を代入しておく。

    this.stepMap = new Array(this.mazeHeight);

    for(var i = 0; i < this.mazeHeight; i++){
        var answerRow = new Array(this.mazeWidth);
        for(var j = 0; j < this.mazeWidth; j++){
            answerRow[j] = this.hitTest(j,i)? COLLISION : NOT_INITIALIZED;
        }
        this.stepMap[i] = answerRow;
    }

    // スタート地点からの同じ距離ごとに、迷路内地点のリストをまとめた2次元配列を作成する。
    this.stepList = [];

    // スタート地点を設定する
    this.stepMap[this.sy][this.sx] = 1;

    var stepCount = 1; //調査する場所の、スタート地点からの歩数。最初は1歩目について調査。
    this.stepList[stepCount - 1] = [new Point(this.sx, this.sy)]; // 0歩目の場所は、スタート地点。

    while(true){

        var nextStepList = new Array(); //現在ステップ数の場所から到達できる、次のステップの地点をすべて格納するためのリスト

        for(var i=0; i < this.stepList[stepCount-1].length; i++){//(stepCount-1)歩目の場所のリストについて繰り返し。
            var p = this.stepList[stepCount-1][i]; // (stepCount-1)歩目の場所を、ここでの注目地点とする。
            var px = p.x;
            var py = p.y;
            //注目地点の「上」のセルが未初期状態かどうか
            if(this.stepMap[py-1][px] == NOT_INITIALIZED){
                this.stepMap[py-1][px] = stepCount+1;
                nextStepList.push(new Point(px, py-1));
            }
            //注目地点の「下」のセルが未初期状態かどうか
            if(this.stepMap[py+1][px] == NOT_INITIALIZED){
                this.stepMap[py+1][px] = stepCount+1;
                nextStepList.push(new Point(px, py+1));
            }
            //注目地点の「左」のセルが未初期状態かどうか
            if(this.stepMap[py][px-1] == NOT_INITIALIZED){
                this.stepMap[py][px-1] = stepCount+1;
                nextStepList.push(new Point(px-1, py));
            }
            //注目地点の「右」のセルが未初期状態かどうか
            if(this.stepMap[py][px+1] == NOT_INITIALIZED){
                this.stepMap[py][px+1] = stepCount+1;
                nextStepList.push(new Point(px+1, py));
            }
        }
        if(nextStepList.length == 0){
            //もうこれ以上遠くへは到達できない場合はループを脱出して終了！
            break;
        }else{
            // 次のステップ地点を格納したリストを、this.stepList配列のステップ数番目に格納。
            this.stepList[stepCount++] = nextStepList;
            // このステップでの道のセルの数を合計に加算
            this.pathStepTotal += nextStepList.length;
        }
    }
}

さらに、この_initAnswerで作成した stepMap, stepList の内容を確認するためのdebugメソッドを追加しておくことにします。 このメソッドを実行すると、「2D迷路データとその解を自動生成する(3):「ポテンシャル法」で迷路を解いてみる」のエントリ内での説明図のような内容を、コンソールに対して出力します。

    debug: function(){
     // 地図のコンソールに表示
     for(var i = 0; i < this.mazeData.length; i++){
         var line = "";
         for(var j = 1; j < this.mazeData[i].length - 1; j++){
          line += " "+String.fromCharCode(48+this.stepMap[i][j]);
         }
         console.log(line);
     }

     // 歩数ごとの地点リストをコンソールに表示
     for(var i = 0; i < this.stepList.length; i++){
         var line = ""+i+":\t"+String.fromCharCode(48+i)+"\t";
         for(var j = 0; j < this.stepList[i].length; j++){
          line += " "+this.stepList[i][j].toString();
         }
         console.log(line);
     }
    }

なお、大きな迷路についてdebugを実行すると、ASCII文字として表示できない場合が出てくると思いますが、面倒くさいのでチェックしてません！