algorithm - 我的 A* 寻路实现不产生最短路径

Question

我正在构建一个需要正确寻路的 Flash 游戏。我在 this tutorial 中使用了伪代码和对角线启发式。我没有密切关注他们的代码。语言是 ActionScript 3，我也在使用 flashpunk 库。

我当前的问题是程序生成的路径显然不是可能的最短路径。这是显示问题的屏幕截图:

灰色 block 是不可遍历的，绿色 block 标记已“访问”的节点，蓝色 block 显示算法生成的路径。

尽管我试图使对角线成本更高 (1.414)，但看起来对角线旅行成本等于非对角线旅行成本。

这是整体算法实现。

function solveMaze() {

    // intitialize starting node
    startingNode.g = 0;
    startingNode.h = diagonalHeuristic(startingNode, destinationNode);
    startingNode.f = startingNode.g + startingNode.h;

    // Loop until destination node has been reached.
    while (currentNode != destinationNode) {

        if (openNodes.length == 0) {
            return null;
        }

        // set lowest cost node in openNode list to current node
        currentNode = lowestCostInArray(openNodes);

        //remove current node from openList
        openNodes.splice(openNodes.indexOf(currentNode), 1);

        //find 8 nodes adjacent to current node
        connectedNodes = findConnectedNodes(currentNode);

        //for each adjacent node,
        for each (var n:Node in connectedNodes) {
            // if node is not in open list AND its not in closed list AND its traversable
            if ((openNodes.indexOf(n) == -1) && (closedNodes.indexOf(n) == -1) && n.traversable) {

                // Calculate g and h values for the adjacent node and add the adjacent node to the open list
                // also set the current node as the parent of the adjacent node

                if ((n.mapX != currentNode.mapX) && (n.mapY != currentNode.mapY)) {
                    cost = 1.414; 
                } else {
                    cost = 1;
                }
                if(n.g> currentNode.g + cost){
                n.g = currentNode.g + cost;
                n.f=calculateCostOfNode(n);
                n.parentNode =currentNode;
                openNodes.push(n);
               }
            }
        }
        // turn current node into grass to indicate its been traversed
        currentNode.setType("walked_path");

        //var temp2:TextEntity = new TextEntity(n.h.toFixed(1).toString(), 32 * currentNode.mapX, 32 * currentNode.mapY);
        //add(temp2);

        // add current node to closed list
        closedNodes.push(currentNode);
    }

    // create a path from the destination node back to the starting node by following each parent node
    var tempNode:Node = destinationNode.parentNode;

    tempNode.setType("path2"); // blue blocks
    while(tempNode != startingNode){
        tempNode = tempNode.parentNode;
        tempNode.setType("path2");

    }
}

这些是使用的辅助函数:

function findConnectedNodes(inputNode:Node):Array {
    var outputArray:Array=[];

    // obtain all nodes that are either 1 unit away or 1.4 units away.
    for each (var n:Node in listOfNodes){
        if ((diagonalHeuristic(inputNode, n) == 1)||(diagonalHeuristic(inputNode, n) == 1.4) {
            outputArray.push(n);
        }
    }
    return outputArray;
}

public static function diagonalHeuristic(node:Node, destinationNode:Node, cost:Number = 1.0, diagonalCost:Number = 1.4):Number {
    var dx:Number = Math.abs(node.mapX - destinationNode.mapX);
    var dy:Number = Math.abs(node.mapY - destinationNode.mapY);

    if (dx > dy) {
        return diagonalCost * dy + (dx - dy);
    }else {
        return diagonalCost * dx + (dy - dx);
    }       
}

function lowestCostInArray(inputArray:Array):Node {
    var tempNode:Node = inputArray[0];
    for each (var n:Node in inputArray) {
        if (n.f < tempNode.f) {
            tempNode = n;
        }
    }
    return tempNode;
}

如果有帮助，我可以提供项目源代码。

Answer 1

我看到了一些潜在的错误。

1. 您可能会覆盖此处的值:

           n.g = currentNode.g + cost;
           n.f=calculateCostOfNode(n);
           n.parentNode =currentNode;
           openNodes.push(n);
   

   应该是:

        if n.g > currentNode.g + cost:
           n.g = currentNode.g + cost;
           n.f=calculateCostOfNode(n);
           n.parentNode =currentNode;
           if n not already in openNodes:
               openNodes.push(n);
   

   将 n.g 初始化为一个非常大的值，或者您可以像 if n not in open set 或 n.g > currentNode.g + cost 那样进行检查。

   你应该从你现在拥有它的地方删除检查 if ((openNodes.indexOf(n) == -1) 并将它放在我说的地方。如果新的 g 成本更好，你应该更新它，即使它在开放列表中。你只更新每个节点一次。如果碰巧你先检查对角线，你将完全忽略边步骤。

   这可能是问题所在:通过忽略开放列表中的邻居，您只会更新一次它们的成本。只要他们不在关闭列表中，就可以更新他们的成本。

2. 我不确定这是否是一个有效的问题，但我认为您在启发式函数中使用 1.414 是在玩火。启发式函数必须是可接受的，这意味着它永远不应该高估成本。如果您遇到一些浮点问题，您可能会高估。我会谨慎行事，使用 1.4 作为启发式算法，使用 1.414 作为对角相邻节点之间的实际成本。