A* algorithm works OK, but not perfectly. What's wrong?

Question

This is my grid of nodes:

I'm moving an object around on it using the A* pathfinding algorithm. It generally works OK, but it sometimes acts wrongly:

• When moving from 3 to 1, it correctly goes via 2. When going from 1 to 3 however, it goes via 4.
• When moving between 3 and 5, it goes via 4 in either direction instead of the shorter way via 6

What can be wrong? Here's my code (AS3):

    public static function getPath(from:Point, to:Point, grid:NodeGrid):PointLine {

        // get target node
        var target:NodeGridNode = grid.getClosestNodeObj(to.x, to.y);

        var backtrace:Map = new Map();
        var openList:LinkedSet = new LinkedSet();
        var closedList:LinkedSet = new LinkedSet();

        // begin with first node
        openList.add(grid.getClosestNodeObj(from.x, from.y));

        // start A*
        var curNode:NodeGridNode;
        while (openList.size != 0) {

            // pick a new current node
            if (openList.size == 1) {
                curNode = NodeGridNode(openList.first);
            }
            else {
                // find cheapest node in open list
                var minScore:Number = Number.MAX_VALUE;
                var minNext:NodeGridNode;
                openList.iterate(function(next:NodeGridNode, i:int):int {
                    var score:Number = curNode.distanceTo(next) + next.distanceTo(target);
                    if (score < minScore) {
                        minScore = score;
                        minNext = next;
                        return LinkedSet.BREAK;
                    }
                    return 0;
                });
                curNode = minNext;
            }

            // have not reached
            if (curNode == target) break;
            else {
                // move to closed
                openList.remove(curNode);
                closedList.add(curNode);

                // put connected nodes on open list
                for each (var adjNode:NodeGridNode in curNode.connects) {
                    if (!openList.contains(adjNode) && !closedList.contains(adjNode)) {
                        openList.add(adjNode);
                        backtrace.put(adjNode, curNode);
                    }
                }
            }
        }

        // make path
        var pathPoints:Vector.<Point> = new Vector.<Point>();
        pathPoints.push(to);
        while(curNode != null) {
            pathPoints.unshift(curNode.location);
            curNode = backtrace.read(curNode);
        }
        pathPoints.unshift(from);
        return new PointLine(pathPoints);

    }

NodeGridNode::distanceTo()

    public function distanceTo(o:NodeGridNode):Number {
        var dx:Number = location.x - o.location.x;
        var dy:Number = location.y - o.location.y;
        return Math.sqrt(dx*dx + dy*dy);
    }

Answer 1

The problem I see here is the line

if (!openList.contains(adjNode) && !closedList.contains(adjNode))

It may be the case that an adjNode may be easier(shorter) to reach through the current node although it was reached from another node previously which means it is in the openList.

Answer 2

Found the bug:

                openList.iterate(function(next:NodeGridNode, i:int):int {
                    var score:Number = curNode.distanceTo(next) + next.distanceTo(target);
                    if (score < minScore) {
                        minScore = score;
                        minNext = next;
                        return LinkedSet.BREAK;
                    }
                    return 0;
                });

The return LinkedSet.BREAK (which acts like a break statement in a regular loop) should not be there. It causes the first node in the open list to be selected always, instead of the cheapest one.