Flawed logic in A* implementation

Question

I've been using examples of others' implementations of the A* pathfinding algorithm as a crutch to help me write my first implementation. I'm having some trouble with the logic in one of the more readable examples I've found.

I'm not here to pick apart this code, really, I'm trying to figure out if I am right or if I am misunderstanding the mechanics here. If I need to review how A* works I will but if this code is incorrect I need to find other sources to learn from.

It appears to me that the logic found here is flawed in two places both contained here:

for(Node neighbor : current.getNeighborList()) {
    neighborIsBetter;
    //if we have already searched this Node, don't bother and continue to the next 
    if (closedList.contains(neighbor))
        continue;

    //also just continue if the neighbor is an obstacle
    if (!neighbor.isObstacle) {

        // calculate how long the path is if we choose this neighbor as the next step in the path 
        float neighborDistanceFromStart = (current.getDistanceFromStart() + map.getDistanceBetween(current, neighbor));

        //add neighbor to the open list if it is not there
        if(!openList.contains(neighbor)) {
-->         openList.add(neighbor);
            neighborIsBetter = true;
            //if neighbor is closer to start it could also be better
-->     } else if(neighborDistanceFromStart < current.getDistanceFromStart()) {
            neighborIsBetter = true;
        } else {
            neighborIsBetter = false;
        }
        // set neighbors parameters if it is better
        if (neighborIsBetter) {
            neighbor.setPreviousNode(current);
            neighbor.setDistanceFromStart(neighborDistanceFromStart);
            neighbor.setHeuristicDistanceFromGoal(heuristic.getEstimatedDistanceToGoal(neighbor.getX(), neighbor.getY(), map.getGoalLocationX(), map.getGoalLocationY()));
        }
    }
}

source

The first line I marked (-->), seems incorrect to me. If you look at the implementation of the list being used(below) it sorts based on heuristicDistanceFromGoal which is set several lines below the .add.

public int compareTo(Node otherNode) {
    float thisTotalDistanceFromGoal = heuristicDistanceFromGoal + distanceFromStart;
    float otherTotalDistanceFromGoal = otherNode.getHeuristicDistanceFromGoal() + otherNode.getDistanceFromStart();

    if (thisTotalDistanceFromGoal < otherTotalDistanceFromGoal) {
        return -1;
    } else if (thisTotalDistanceFromGoal > otherTotalDistanceFromGoal) {
        return 1;
    } else {
        return 0;
    }
}

The second line I marked should always evaluate to false. It reads:

} else if(neighborDistanceFromStart < current.getDistanceFromStart()) {

Which can be simplified to:

if((current.getDistanceFromStart() + map.getDistanceBetween(current, neighbor)) < current.getDistanceFromStart())

And again to:

if(map.getDistanceBetween(current, neighbor) < 0)

Which would be fine except getDistanceBetween() should always return a positive value (see here).

Am I on or off track?

Answer 1

First of all, you are mostly on track. I strongly suspect the code you posted is still under development and has some problems. But, still your assumption of distance is positive is not correct in general. A* is a graph search algorithm and edges can have negative weights as well in general. Hence, I assume they tried to implement the most general case. The openList.add seems totally fine to me though. Your queue should be sorted with heuristic distance. Just check the wiki page https://en.wikipedia.org/wiki/A_star, the related line is f_score[neighbor] := g_score[neighbor] + heuristic_cost_estimate(neighbor, goal). And, main idea behind this is, you always underestimate the distance (admissible heuristic); hence, if the goal is found, none of the not-explored nodes can be optimal. You can read more at http://en.wikipedia.org/wiki/Admissible_heuristic

Second of all, If you want a stable AI code base, You can simply use http://code.google.com/p/aima-java/. It is the implementation of the algorithms in AIMA (Artificial Intelligence A Modern Approach)