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

Question

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

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

灰色方块不可穿越，绿色方块表示已经"visited"的节点，蓝色方块表示算法生成的路径。

尽管我试图使对角线成本更高 (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

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

您可能会覆盖此处的值：
```
        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 the open set or n.g > currentNode.g + cost.
那样做检查
你应该把支票if ((openNodes.indexOf(n) == -1)从你现在拥有的地方拿走，然后把它放在我说的地方。如果新的 g 成本更好，你应该更新它，即使它在开放列表中。您只需更新每个节点一次。如果碰巧你先检查对角线，你将完全忽略侧步。

这可能是问题所在：通过忽略开放列表中的邻居，您只会更新一次它们的成本。只要不在closed list里面就可以更新他们的cost
我不确定这是否是一个有效的问题，但我认为您在启发式函数中使用 1.414 是在玩火。启发式函数必须是可接受的，这意味着它永远不应该高估成本。如果你运行陷入一些浮点问题，你可能高估了。我会谨慎行事，使用 1.4 作为启发式算法，使用 1.414 作为对角相邻节点之间的实际成本。

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

My A* pathfinding implementation does not produce the shortest path

algorithm

actionscript-3

flash

path-finding

a-star