我的A*路径规划实现没有产生最短路径

Question

我正在制作一个需要正确路径规划的Flash游戏。我使用了这篇教程中的伪代码和对角线启发式。虽然我没有严格遵循他们的代码，但语言是ActionScript 3，我也在使用flashpunk库。

我目前的问题是程序生成的路径明显不是最短路径。这里有一张截图显示了问题： 灰色块是不可通过的，绿色块标记已被“访问”的节点，蓝色块显示算法生成的路径。

看起来对角线移动成本等于非对角线移动成本，尽管我试图使对角线成本更高（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;
}

如果需要的话，我可以提供项目源代码。

- Don Zhang

---

这里是swf文件链接(http://puu.sh/iPWwg/39f1dde5e2.swf)。您可以点击瓷砖将其标记为不可穿越。我还在stackoverflow上找到了另一个问题(https://dev59.com/E4rda4cB1Zd3GeqPISXz)，但他的解决方案好像不适用于我？ - Don Zhang

calculateCostOfNode 的代码在哪里？ - Wheeldog

你的迷宫更适合使用地图方法而不是图形方法。请参考C++中的A*算法。 - Spektre

函数calculateCostOfNode(inputNode:Node) { var f:Number = inputNode.g + diagonalHeuristic(inputNode, destinationNode); return f; } 这是calculateCostOfNode的代码。你说得对，它只有一行。 - Don Zhang

如果我在diagonalHeuristic和findConnectedNodes中将1.414更改为1.4，行为是相同的。如果我还在solveMaze()中将g成本从1.414更改为1.4，行为也是相同的。 - Don Zhang

Answer 1

我看到有几个可能存在问题。

1. You are potentially overwriting values here:

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

   It should be:

        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);
   

   With n.g initiated to a very large value, or you can do the check like if n not in the open set or n.g > currentNode.g + cost.

   You should remove the check if ((openNodes.indexOf(n) == -1) from where you have it now and put it where I said. If the new g cost is better, you should update it, even if it's in the open list. You only update each node once. If it so happens that you check diagonals first, you will completely ignore side steps.

   This is likely the problem: by ignoring neighbors that are in the open list, you will only update their cost once. It is OK to update their cost as long as they are not in the closed list.

2. I don't know for sure if this is a valid concern, but I think you're playing with fire a little by using 1.414 in the heuristic function. The heuristic function has to be admissible, which means it should never overestimate the cost. If you run into some floating point issues, you might overestimate. I'd play it safe and use 1.4 for the heuristic and 1.414 for the actual cost between diagonally adjacent nodes.

- IVlad

---

你好，感谢您的评论。

1. 我已经按照您的建议实现了 n.g > currentNode.g + cost 的测试。我还没有实现测试是否已经在 openNodes 列表中。为了执行本点讨论的代码行，相邻节点不在 open 或 closed 列表中已经是一个条件。
2. 循环结束时的最后一行代码将当前节点推入 closed 列表。缩进可能会让事情变得混乱，这是我的错。
3. 已按照您的建议实施 :)

程序仍然存在相同的问题。 - Don Zhang

@DonZhang，你应该把检查if ((openNodes.indexOf(n) == -1)的位置从现在的位置移除，并放到我说的位置。如果新的g成本更好，即使它在开放列表中，你也应该更新它。每个节点只更新一次。如果碰巧你先检查对角线，那么你将完全忽略侧面步骤。这很可能是问题所在：通过忽略在开放列表中的邻居，你只会更新它们的成本一次。只要它们不在关闭列表中，更新它们的成本就可以了。 - IVlad