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

Question

I have tried 2 different pseudocodes, from both Wikipedia and MIT, eventually both give me the same results: sometimes, like on these screenshots, traversing loops forever because somehow there appears a link back somehow:

I include code in 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);
}
}

Don't pay attention to the distances! That path is optimal, the nodes that are closer aren't connected(I hided connections on screenshots).

And also, forgot to mention that begin node on the screenshots is black, not orange.

Sorry, guys, I made a very silly mistake, I forgot to reset my parentNodes of Nodes to null after first run.

Answer 1

You should set neighbour.parentNode = current when you set neighbour.g. Right now you're setting parentNode to the first node that pushes neighbor onto the openSet

Also you will get much better performance if you use the proper data-structures (a set for closedSet; a priority-queue for openSet)