迷路を作って遊んでみる3 - 犬も歩けば棒も歩く

前回からの続きです。今回はダイクストラアルゴリズムを使って迷路の最短経路を求めてみます。

ダイクストラを利用する

今回、以前作ったダイクストラアルゴリズムのプログラムを参考にして勧めていきます。まず最初に迷路をどうやってグラフとして表現するのか説明していきます。

迷路をグラフで表現する

まずは迷路の形をグラフとして表現する必要があります。今回は迷路に含まれる通路のセルを、グラフのノードとしてみなします。例えば10*10の迷路があったとして、そのうちの50セルが通路だった場合、グラフのノードは50個になります。次にノード間の関係について考えてみます。迷路のあるセルについてみてみると、周囲には8つのセル(左上、上、右上、右、右下、下、左下、左、左上)があります。そのうち上、右、下、左の位置が通路の場合、そちらに移動することができます。つまり、上、右、下、左に通路がある場合、その部分をグラフのエッジとしてつなげば良いわけです。
これを踏まえるとノードの表現は以下のようになります。

/**
 * ノード
 * @param {Object} position 座標 (例 {x:3,y:1})
 */
function Node(position) {
    this.position = position;
    this.top = null;
    this.right = null;
    this.left = null;
    this.bottom = null;
        
    Node.prototype.toString = function() {
        return "(" + this.position.x + "," + this.position.y + ")";
    };
};

利用例

これを使って迷路を表現してみます。例えば、以下のような迷路があったとします。

maze = new Maze(3,4);

maze.setCell(0,0,MAZETYPE.WAY);
maze.setCell(1,0,MAZETYPE.WAY);
maze.setCell(2,0,MAZETYPE.WAY);
maze.setCell(0,1,MAZETYPE.WAY);
maze.setCell(0,2,MAZETYPE.WAY);
maze.setCell(1,2,MAZETYPE.WAY);
maze.setCell(2,2,MAZETYPE.WAY);
maze.setCell(1,3,MAZETYPE.WAY);

maze.display(); //表示

これを表示してみると、以下のようになります。

これをグラフで表現すると、このような形になります。グラフは無向グラフなので、例えばノードAに隣接するノードBがあった場合、AからBにのびるエッジと、BからAにのびるエッジの二本あります。

var cell0_0  = new Node({x:0,y:0});
var cell1_0  = new Node({x:1,y:0});
var cell2_0  = new Node({x:2,y:0});

var cell0_1  = new Node({x:0,y:1});

var cell0_2  = new Node({x:0,y:2});
var cell1_2  = new Node({x:1,y:2});
var cell2_2  = new Node({x:2,y:2});

var cell1_3  = new Node({x:1,y:3});

cell0_0.right = cell1_0;
cell1_0.left = cell0_0;

cell1_0.right = cell2_0;
cell2_0.left = cell1_0;

cell0_2.right = cell1_2;
cell1_2.left = cell0_2;

cell1_2.right = cell2_2;
cell2_2.left = cell1_2;

cell0_0.bottom = cell0_1;
cell0_1.top = cell0_0;

cell0_1.bottom = cell0_2;
cell0_2.top = cell0_1;

cell1_2.bottom = cell1_3;
cell1_3.top = cell1_2;

二本分のエッジを設定しなくてはいけないので、少しめんどうですね。Nodeに以下のようなメソッドを定義してエッジの設定で楽をしましょう。

Node.prototype.setRight = function(next) {
    this.right = next;
    next.left = this;
};

Node.prototype.setLeft = function(next) {
    this.left = next;
    next.right = this;
};

Node.prototype.setTop = function(next) {
    this.top = next;
    next.bottom = this;
};

Node.prototype.setBottom = function(next) {
    this.bottom = next;
    next.top = this;
};

これを利用すると、先ほどのグラフの定義は以下のように変更できます。

cell0_0.setRight(cell1_0);
cell1_0.setRight(cell2_0);
cell0_2.setRight(cell1_2);
cell1_2.setRight(cell2_2);

cell0_0.setBottom(cell0_1);
cell0_1.setBottom(cell0_2);
cell1_2.setBottom(cell1_3);

最短経路を求める

どうにか迷路をグラフとして表現することができました。迷路を自動的にグラフに変換する処理も必要ですが、これは後回しにしましょう。先にグラフから最短経路を求めてみます。以前作ったものに少し手を加えて、以下のような実装になりました。ソースコードの解説はしません。以前書いた記事を参考にしてください。

/**
 * ダイクストラ
 */
function dijkstra(start) {
    var list = new Array();
    dijkRec(list, start);
    return list;
};

/**
 * 最短経路を再帰的に求める
 * @param {Object} list Routeの配列
 * @param {Object} start 初回のみ指定
 */
function dijkRec(list, start) {
    var isFirst = false; //初回かどうか
    var route; //今回選択するルート
    if (start != null) {
        isFirst = true;
        route = new Route(null, start, null); //ダミー用
    } else { //二回目以降
        if (list.length <= 0) return;
        //コストが一番小さい経路を探す
        var min;
        var minIndex;
        for (var i = 0; i < list.length; i++) {
            var li = list[i];
            if (li.check) continue; //チェック済みならスキップ
            var cost = li.getCost();
            if (min > cost) {
                min = cost;
                minIndex = i;
            } else if (min == null) {
                min = cost;
                minIndex = i;
            }
        }
        if (minIndex == null) return;
        route = list[minIndex];
    }
    route.check = true; //探索済みマーク
    //その経路から先を探索する
    var from = route.to;
    var nextNodeList = [ from.top, from.right, from.bottom, from.left ];       
    for (var i = 0; i < 4; i++) {
        var nextNode = nextNodeList[i];
        if(nextNode == null) continue;
        //nextNodeがすでにリストにあるか調べる
        var check = false;
        for (var j = 0; j < list.length; j++) {
            if (nextNode == list[j].to  || nextNode == list[j].from) {
                check = true;
                break;
            }
        }
        //探索候補のルートを追加
        var r;
        if (!check) { //まだない場合
            if (!isFirst) {
                //クローンから新しいルートを作る
                r = route.clone();
                r.to = nextNode; //宛先を書きかえ
                r.route.push(from); //ルートに追加
            } else {
                r = new Route(from, nextNode, new Array());
            }
            list.push(r);
        } else { //すでにある場合
            if (list[j].getCost() > route.getCost() + 1 ) { //新しいルートのほうがコストが低い場合
                //クローンから新しいルートを作る
                r = route.clone();
                r.to = nextNode;
                r.route.push(from); //ルートかきかえ
                r.check = list[j].check;
                list[j] = r; //入れ替え
            } else { //逆にコストが高い場合
                continue; // !!ここで終わり!!
            }
        }
    }
    dijkRec(list);
};

/**
 * あるノードからあるノードへの経路を示す
 * @param {Object} from
 * @param {Object} to
 * @param {Object} route　間にあるノードの集合(配列)
 * routeにはfromとtoのノードは含まない
 */
function Route(from, to, route) {
    this.from = from;
    this.to = to;
    if (route) this.route = route;
    else this.route = new Array();
    this.check = false; //チェック用のフラグ
}

Route.prototype.toString = function() {
    return this.from + " - " + this.to + " " + this.getCost();
};

Route.prototype.getCost = function() {
    if(this.route == null || this.to == null || this.from == null) return null;
    return this.route.length + 1;
};

Route.prototype.clone = function() {
    var array = this.route.clone();
    return new Route(this.from, this.to, array);
};

/**
 * Arrayのプロトタイプオブジェクトにcloneメソッドを追加
 */
Array.prototype.clone = function() {
    if ( this[0] != null && this[0].constructor == Array ) {
        var ar, n;
        ar = new Array( this.length );
        for ( n = 0; n < ar.length; n++ ) {
            ar[n] = this[n].clone();
        }
        return ar;
    }
    return Array.apply( null, this );
};

利用例は以下のとおり

var cell0_0  = new Node({x:0,y:0});
var cell1_0  = new Node({x:1,y:0});
var cell2_0  = new Node({x:2,y:0});
var cell0_1  = new Node({x:0,y:1});
var cell0_2  = new Node({x:0,y:2});
var cell1_2  = new Node({x:1,y:2});
var cell2_2  = new Node({x:2,y:2});
var cell1_3  = new Node({x:1,y:3});
cell0_0.setRight(cell1_0);
cell1_0.setRight(cell2_0);
cell0_2.setRight(cell1_2);
cell1_2.setRight(cell2_2);
cell0_0.setBottom(cell0_1);
cell0_1.setBottom(cell0_2);
cell1_2.setBottom(cell1_3);

var list = dijkstra(cell0_0);
for(var i = 0; i < list.length; i++){
    var li = list[i];
    document.write(li+"<br>");        
}

実行すると以下のように出力されます。

(0,0) - (1,0), 1
(0,0) - (0,1), 1
(0,0) - (2,0), 2
(0,0) - (0,2), 2
(0,0) - (1,2), 3
(0,0) - (2,2), 4
(0,0) - (1,3), 4

迷路をグラフに直す

迷路をグラフに直す処理を実装します。これによって、迷路に対して、上でやったように最短経路を求めることができます。Searchオブジェクトに以下のようにmazeToGraphというメソッドを設けました。

var Search = {
	
	……

    mazeToGraph : function(maze) {
        var start;
        //ノードを作って二次元配列に入れておく
        var array = maze.array.clone();
        for(var i = 0; i < maze.w; i++){
            for (var j = 0; j < maze.h; j++) {
                var type = maze.getCell(i,j);
                if(type == MAZETYPE.WAY || type == MAZETYPE.START || type == MAZETYPE.GOAL) {
                     array[i][j] = new Node({x:i,y:j});
                } else {
                    array[i][j] = null;
                }
            }
        }
        start = array[maze.start.x][maze.start.y];
        if(start == null) return null;
        //ノードをエッジでつなぐ
        for (var i = 0; i < maze.w; i++) {
            for (var j = 0; j < maze.h; j++) {
                var type = maze.getCell(i,j);
                if(type == MAZETYPE.WAY || type == MAZETYPE.START || type == MAZETYPE.GOAL) {
                     var right = maze.getCell(i + 1, j);
                     var bottom = maze.getCell(i, j + 1);
                     if(right == MAZETYPE.WAY || right == MAZETYPE.START || right == MAZETYPE.GOAL) array[i][j].setRight(array[i+1][j]);
                     if(bottom == MAZETYPE.WAY || bottom == MAZETYPE.START || bottom == MAZETYPE.GOAL) array[i][j].setBottom(array[i][j+1]);
                }
            }
        }
        return start; //開始位置のノードだけ返す
    }
};

これを実行すると、開始位置のノードが返ってきます。

ゴールまでの最短経路を求める

次に、上で作ったグラフを利用してゴールまでの最短経路を求めるメソッドを実装します。SearchオブジェクトにgetShortestPathというメソッドを追加しました。これで最短経路を求めることができます。

var Search = {

	……

    /**
     * スタート地点からゴールまでの最短経路を返す
     * この経路の実体はdijkstra.jsのRouteオブジェクトから生成したオブジェクト。
     * @param {Object} maze
     * @param {Object} point (省略可能) 指定した場合はスタート地点からゴールまでではなく、スタート地点からこの場所までの最短経路を返す。 (例. { x : 3, y : 4 } )
     */
    getShortestPath : function(maze, point) {
        var graph = this.mazeToGraph(maze); //グラフの開始地点のノード
        if(graph == null) return;
        var routeList = dijkstra(graph); //グラフの開始地点から、各地点までの最短経路(Route)の集合
        if(routeList == null) return;
        //目的地を決める
        if(point == null) var point = maze.goal;
        for(var i = 0; i < routeList.length; i++){
            var route = routeList[i];
            if( route.to.position.x == point.x && route.to.position.y == point.y )
                return route;
        }
        return;
    }
};

getShortestPathメソッドの第二引数は省略可能です。省略した場合はゴールまでの経路を求めます。また、明示的に指定下場合は、引数pointの示す(x,y)座標までの最短経路を求めます。これの利用例は以下のようになります。

var maze = new Maze(15,15);
maze.setCell(1,1,MAZETYPE.WAY);    
maze.setCell(2,1,MAZETYPE.WAY);
maze.setCell(3,1,MAZETYPE.WAY);

……

maze.setCell(1,1,MAZETYPE.START); //スタート
maze.setCell(9,13,MAZETYPE.GOAL); //ゴール
maze.display(); //表示

//作成した迷路を引数にする
var route = Search.getShortestPath(maze);
alert(route);

最終的にはRouteオブジェクトが返って来きます。Routeオブジェクトは内部でtoStringメソッドをオーバライドしているので、文字列として表示することができます。上のコードを実行すると、以下のようにスタートからゴールまでの最短経路のコストが表示されます。

以下のURLで実行できるようにしておきました。

http://www17.atpages.jp/prime503/maze-old2/

ダウンロード

HelloMaze2.zip

ファイル構成

index.html
prototype.js
- JavaScriptのライブラリ
- 特に見なくてもいいです。
maze.js
- 迷路を作るためのMazeオブジェクトを定義しています
search.js
- 迷路を探索するための機能です
- 下のほうには、グラフのノードと、ダイクストラアルゴリズムのメソッドが書かれています
mazetest.js
- 上記のファイルを利用して実際に迷路を作って、最短経路を求めています
- index.htmlのページ読み込みが終わると、このファイルで定義されているinitメソッドが呼び出されます

最後に

今回はここまでです。あと、もうちょっと続きます。

リンク

迷路を作って遊んでみる
 迷路を作って遊んでみる2
迷路を作って遊んでみる4