javascript - Javascript Maze 実装における Dijkstra のアルゴリズム

Question

ダイクストラのアルゴリズムを使用して、迷路のすべての位置を特定のポイントに戻すパスを見つけようとしています。

ダイクストラのアルゴリズムの JavaScript バージョンをここで見つけました。

https://github.com/bm1362/dijkstra-js/blob/master/nodes.js

（bm1362さん、ありがとうございます！）

私が迷路グラフの作成に取り組んだ方法は次のとおりです。

// the maze
var maze = 
[[1, 1, 1, 1],
 [1, 0, 0, 0],
 [1, 0, 0, 0],
 [1, 1, 1, 1]];


maze2 = [];
var i = 0;
var mazeSize = 30;
for (var x = 0; x < maze[0].length; x++) {

    for (var y = 0; y < maze[0].length; y++) {

        if (maze[x][y] == 1) {
            nodes.push(new node);
            nodes[i].setPos((x) * (maze[0].length + 100), (y) * ((maze[0].length + 100)))
            nodes[i].tmppos = [x, y];
            nodes[i].id = i;
            maze2[x + ',' + y] = nodes[i];
            i++;
        }

    }
}

//sort nodes in order of x position
var sortedNodes = quickSort(nodes);
//var sortedNodes = nodes;
for (var i = 0; i < sortedNodes.length; i++) {
    sortedNodes[i].number = i;


    var n1 = sortedNodes[i];
    var up = {}, down = {}, left = {}, right = {};
    var pos = [];
    up.x = n1.tmppos[0];
    up.y = n1.tmppos[1] - 1;
    pos.push(up);
    down.x = n1.tmppos[0];
    down.y = n1.tmppos[1] + 1;
    pos.push(down);
    left.x = n1.tmppos[0] - 1;
    left.y = n1.tmppos[1];
    pos.push(left);
    right.x = n1.tmppos[0] + 1;
    right.y = n1.tmppos[1];
    pos.push(right);

    for (var m = 0; m < pos.length; m++) {

        if (maze[pos[m].x] != undefined && maze[pos[m].x][pos[m].y] != undefined && maze[pos[m].x][pos[m].y] == 1) {
            var n2 = maze2[pos[m].x + ',' + pos[m].y];
            var dist = calcDist(n1, n2);
            sortedNodes[i].addConnection(n2);
            connections.push({
                a: n1,
                b: n2,
                dist: dist
            })
        }
    }


}

私が抱えている問題は、すべてのノードが接続しているように見えても、アルゴリズムを実行すると、一部のノードが親セットを取得しないことです。しかし、私はさまざまな方法を試しましたが、まだすべての親を設定することはできません。

ここで JS フィドルを作成しました: http://jsfiddle.net/XcdCr/3/

どんな助けでも大歓迎です。