javascript - A*star 搜索算法在 2D Array 上的优化

Question

我正在尝试实现 A*star 搜索算法并且我成功了，但是它有时不会产生最佳最短路径，我想知道是否可以优化算法以产生更好的最短路径？（我的意思是最短路径实际上不是最短路径）

目前我正在跟踪每个邻居的父节点以找到最短路径，我认为这就是问题所在，因此当我将 FinishNode 最后添加到 VisitedNodesInOrder 数组时，我可以访问让我们到达的父节点该单元格最快，我一直返回直到到达 startNode，在这种情况下，父节点为空。

当有墙壁时，它不会按预期工作，因为它在到达墙壁之前看不到墙壁，因此它采用非最佳路径，所以当我从 FinishNode 回溯时，它遵循非最佳路径小路。

这应该像这样工作吗？或者算法有没有办法在尝试采用非最佳路径之前考虑墙壁？

网格由节点对象的 2D 数组组成，该数组具有 row、col 和 NodeType 属性。

每个节点的邻居由它旁边的 4 个单元格组成（左、右、上、下）

const aStar = (grid, startNode, finishNode) => {
    const n = grid.length;
    const m = grid[0].length;

    const endRow = finishNode.row;
    const endCol = finishNode.col;


    const visitedNodesInOrder = [];

    const pq = new PriorityQueue((a, b) => a.distance < b.distance);

    startNode.parent = null;

    //Store in an object {node: {row, col, parent}, distance: x}
    //Distance refers to distance to FinishNode

    pq.push({node: startNode, distance: Math.abs(endRow - startNode.row) + Math.abs(endCol - startNode.col)});

    while(!pq.isEmpty()){
        const {node} = pq.pop();

        const row = node.row;
        const col = node.col;
        const parent = node.parent;

        if(grid[row][col].nodeType == NodeType.VISITED_NODE){
            continue;
        }

        if (grid[row][col].nodeType === NodeType.FINISH_NODE) {
            visitedNodesInOrder.push({row, col, parent});
            break;
        }

        if (grid[row][col].nodeType === NodeType.WALL_NODE) {
            continue;
        }

        if (row < n - 1) {
            pq.push({node: {row: row + 1, col, parent: {row, col}}, distance: Math.abs(endRow - row + 1) + Math.abs(endCol - col)});
        }

        if (row > 0) {
            pq.push({node: {row: row - 1, col, parent: {row, col}}, distance: Math.abs(endRow - row - 1) + Math.abs(endCol - col)});
        }

        if (col < m - 1) {
            pq.push({node: {row: row, col: col + 1, parent: {row, col}}, distance: Math.abs(endRow - row) + Math.abs(endCol - col + 1)});
        }

        if (col > 0) {
            pq.push({node: {row: row, col: col - 1, parent: {row, col}}, distance: Math.abs(endRow - row) + Math.abs(endCol - col - 1)});
        }

        if (grid[row][col].nodeType === NodeType.EMPTY_NODE) {
            visitedNodesInOrder.push({row, col, parent: parent});
            grid[row][col].nodeType = NodeType.VISITED_NODE;
        }

    }

    return visitedNodesInOrder
};

图片中的蓝色代表visitedNodes，黑色是墙壁，黄色路径是“最短”路径。

标签： javascriptalgorithmdata-structuresdijkstraa-star