javascript - A* 算法有一个奇怪的错误

Question

我尝试为我开发的游戏编写 A* 算法，但有时会遇到奇怪的错误（算法尚未完成）。

我将我的算法结果与https://qiao.github.io/PathFinding.js/visual/ 结果进行比较，看看我是否做得很好，这就是我得到的：

我的代码：https : //image.prntscr.com/image/k7FLFuzcScCPLEBMhwaM5Q.png 桥代码：https ://image.prntscr.com/image/5IKMnlF9S-KXRORoQsPkvg.png

如您所见，建筑物和距离相同，那为什么我会得到不同的结果？我错过了什么？

对不起我的英语不好。

class AStar {
constructor(engine) {
    this.engine = engine;
    this.engine.astar = this;
    this.dest = null;
    this.diagonal = false; // Can use diagonal? (7, 9, 1, 3)
    this.permission = null; // Source permission
}
nodePermission(node) {
    if (!this.engine.mapSettings.premissions.hasOwnProperty(node[0]))
        return false;
    if (!this.engine.mapSettings.premissions[node[0]].hasOwnProperty(node[1]))
        return false;
    return (this.engine.mapSettings.premissions[node[0]][node[1]] === this.permission);
} // return permission status (true or false)
getNeighborhoods(node) {
    let nodes = [];
    if (this.engine.player.position.x > 0 && this.engine.player.position.y > 0 && this.diagonal)
        nodes.push([(node[0] - 1), (node[1] - 1)]); // push 7
    if (this.engine.player.position.y > 0)
        nodes.push([node[0], (node[1] - 1)]); // push 8
    if (this.engine.player.position.y > 0 && this.engine.player.position.x < this.engine.mapSettings.mapSizeX && this.diagonal)
        nodes.push([(node[0] + 1), (node[1] - 1)]); // push 9
    if (this.engine.player.position.x > 0)
        nodes.push([(node[0] - 1), node[1]]); // push 4
    //nodes.push(node); // push 5
    if (this.engine.player.position.x < this.engine.mapSettings.mapSizeX)
        nodes.push([(node[0] + 1), node[1]]); // push 6
    if (this.engine.player.position.x > 0 && this.engine.player.position.y < this.engine.mapSettings.mapSizeY && this.diagonal)
        nodes.push([(node[0] - 1), (node[1] + 1)]); // push 1
    if (this.engine.player.position.y < this.engine.mapSettings.mapSizeY)
        nodes.push([(node[0]), (node[1] + 1)]); // push 2
    if (this.engine.player.position.x < this.engine.mapSettings.mapSizeX && this.engine.player.position.y < this.engine.mapSettings.mapSizeY && this.diagonal)
        nodes.push([(node[0] + 1), (node[1] + 1)]); // push 3
    if (nodes.length <= 0)
        return false;
    // Check block
    for (let i in nodes) {
        if (!this.nodePermission(nodes[i]))
            delete nodes[i];
    }
    nodes = nodes.filter(function(n){ return n !== undefined });
    return nodes;
} // return neighborhoods nodes (array of nodes)
nodeValue(node) {
    let result = [];
    // Distance between node and player
    result.push(
        Math.abs(node[0] - this.engine.player.position.x) + Math.abs(node[1] - this.engine.player.position.y)
    );
    // Distance between node and destination
    result.push(
        Math.abs(node[0] - this.dest[0]) + Math.abs(node[1] - this.dest[1])
    );
    // Sum of both
    result.push(result[0] + result[1]);
    this.engine.text.addText(result[1], 20*(node[0]-this.engine.map.mapConstructor.from.x), 20*(node[1]-this.engine.map.mapConstructor.from.y));
    return result;
} // return G, H, F (as array)
lowestNode(nodes) {
    let h = 0;
    let f = 0;
    let node = null;
    for (let i in nodes) {
        if (!nodes.hasOwnProperty(i))
            continue;
        let value = this.nodeValue(nodes[i]);
        if (h === 0 && f === 0) {
            h = value[1];
            f = value[2];
            node = i;
            continue;
        }
        if (value[2] < f) {
            f = value[2];
            h = value[1];
            node = i;
        }
        else if (value[2] === f && value[1] < h) {
            f = value[2];
            h = value[1];
            node = i;
        }
    }
    return nodes[node];
} // return the node with the highest priority to evolve
arraysEqual(arr1, arr2) {
    if(arr1.length !== arr2.length)
        return false;
    for(let i = arr1.length; i--;) {
        if(arr1[i] !== arr2[i])
            return false;
    }
    return true;
}
searchForArray(needle, haystack){
    let i, j, current;
    for (i = 0; i < haystack.length; ++i){
        if(needle.length === haystack[i].length){
            current = haystack[i];
            for (j = 0; j < needle.length && needle[j] === current[j]; ++j);
            if(j === needle.length)
                return true;
        }
    }
    return false;
}
findPath(node) {
    for (let id in this.engine.text.textList) {
        this.engine.text.deleteText(id);
    }
    let x = (this.engine.map.mapConstructor.from.x + node[0]);
    let y = (this.engine.map.mapConstructor.from.y + node[1]);
    let src = [this.engine.player.position.x, this.engine.player.position.y];
    this.dest = [x, y];
    this.permission = this.engine.mapSettings.premissions[x][y];
    // - - - - - - - - - -
    let openList = [src];
    let closedList = [];
    // - - - - - - - - - -
    while (openList.length > 0) {
        let current = this.lowestNode(openList);                            // Get the node with highest priority
        if (this.arraysEqual(current, this.dest))                           // If the algorithm reach to destination
            return this.reconstructPath(closedList, current);               // Reconstruct the path
        // Delete from openList
        let delIndex = openList.indexOf(current);                           // Get the index's node in array
        delete openList[delIndex];                                          // delete node by index
        openList = openList.filter(function(n){ return n !== undefined });  // remove empty value
        closedList.push(current);                                           // add node to closedList
        let neihberhoods = this.getNeighborhoods(current);                  // Get neighborhoods's node
        for (let i in neihberhoods) {
            if (!neihberhoods.hasOwnProperty(i))
                continue;
            if (this.searchForArray(neihberhoods[i], closedList))
                continue;
            if (!this.searchForArray(neihberhoods[i], openList))
                openList.push(neihberhoods[i]);
            if (this.nodeValue(current)[2] >= this.nodeValue(neihberhoods[i])[2])
                continue;
            closedList.push(neihberhoods[i]);
        }
    }
}
reconstructPath(closedList, current) {
    return;
    console.log('Found that');
    console.log(closedList);
    console.log(current);
    console.log('finish');
}

}

标签： javascriptalgorithm