A* 在遍历它的路径回到开始节点时有时会永远循环

Question

我尝试了 2 种不同的伪代码，来自 Wikipedia and MIT，最终都给我相同的结果：有时，就像在这些屏幕截图上一样，永远循环遍历，因为不知何故以某种方式出现了 link ：

我在 AS3 中包含代码：

{
private function searchPath(e:MouseEvent = null):void 
{
    for (var i:int = 0; i < nodes.length; i ++)
        nodes[i].role = Node.IDLE_NODE;
    
    if (!endNode || !beginNode) return;
    beginNode.role = Node.BEGIN_NODE;
    endNode.role = Node.END_NODE;
    
    openSet.push(beginNode);
    beginNode.g = 0;
    beginNode.f = beginNode.h = heuristicCost(beginNode, endNode);
    addEventListener(Event.ENTER_FRAME, update);
}
    
private function update(e:Event):void 
{
    if (openSet.length)
    {
        // searching for minimal f score node
        var current:Node = openSet[0];
        for (var i:int = 0; i < openSet.length; i ++)
            if (openSet[i].f < current.f)
            {
                current = openSet[i];
            }
        
        current.role = Node.CURRENT_NODE;
        // remove current node from openset
        openSet.splice(openSet.indexOf(current), 1);
        
        
        // walking through neighbours
        for each(var neighbour:Node in current.neighbours)
        {
            if (neighbour == endNode)
            {
                neighbour.parentNode = current;
                highlightPath(neighbour);
                return;
            }
            
            if (current.g + heuristicCost(current, neighbour) >= neighbour.g)
                continue;
            
            neighbour.g = current.g + heuristicCost(current, neighbour);
            neighbour.h = heuristicCost(neighbour, endNode);
            neighbour.f = neighbour.g + neighbour.h;    
            
            // if neighbour is in the closed set or is in the openthen skip it
            if (!(closedSet.indexOf(neighbour) > -1) && (openSet.indexOf(neighbour) < 0))
            {
                openSet.push(neighbour);
                neighbour.parentNode = current;
            }
        }
        // add current node to the closed set
        closedSet.push(current);
    }
    else
    {
        while (closedSet.length) closedSet.pop();
        trace("No solution");
        removeEventListener(Event.ENTER_FRAME, update);
    }
}
private function highlightPath(current:Node):void 
{
    
    var tp:Vector.<Node> = new Vector.<Node>();
    
    tp.push(current);
    
    while (current.parentNode) //this loops forever in situations from screenshots, because there's a link back
    {
        tp.push(current.parentNode);
        current.role = Node.PATH_NODE;
        current = current.parentNode;
    }
    current.role = Node.PATH_NODE;
    
    while (openSet.length) openSet.pop();
    while (closedSet.length) closedSet.pop();
    for (var i:int = 0; i < nodes.length; i ++)
        nodes[i].g = nodes[i].h = nodes[i].f = Infinity;

    removeEventListener(Event.ENTER_FRAME, update);
}
}

不要在意距离！该路径是最优的，更近的节点没有连接（我在屏幕截图中隐藏了连接）。

还有，忘了说截图上的开始节点是黑色的，不是橙色的。

抱歉，伙计们，我犯了一个非常愚蠢的错误，我忘记在第一个运行之后将我的节点的 parentNodes 重置为 null。

Answer 1

设置neighbour.g时应设置neighbour.parentNode = current。现在，您正在将 parentNode 设置为将 neighbor 推送到 openSet

的第一个节点

此外，如果您使用适当的数据结构 （closedSet 的集合；优先级队列openSet)

A* 在遍历它的路径回到开始节点时有时会永远循环

A* sometimes loops forever when traversing it's path back to the begin node

a-star

path-finding

actionscript-3