1

我正在尝试使用 Dijkstra 算法来找到迷宫的每个位置回到特定点。

我在这里找到了 Dijkstra 算法的 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/

任何帮助将不胜感激。

4

0 回答 0