A-Star doesnt behave like it should

Question

I'm quite new to pathfinding and recently got A-Star working for the first time in Java with Libgdx, but it has some flaws, it doesnt always find the fastest path , or the program simply kills itself(because it's too slow?) :/

(Input/Output here: Imgur album: White = untouched Node, green = start, red = target, blue = path, yellow = node is on closed list but unrelevant)

The rest of the code can be found on Github.

This is the code for the Algorithm itself:

Node lastNode;

Node[] neighborNodes;

int lowestF = 2000;

Node bestNode;

public void findPath() {
    for(int x = 0; x < map.worldWidth; x++) {
        for(int y = 0; y < map.worldHeight; y++) {
            nodes[x][y].calculateHeuristic(targetNode);
        }
    }

    lastNode = startNode;

    while(lastNode != targetNode || !openList.isEmpty()) {
        neighborNodes = map.getNeighbors(lastNode);
        for(Node node:neighborNodes) {
            if(node != null)
                if(node.state != State.BLOCKED && !closedList.contains(node)) {
                    openList.add(node);
                    node.parentNode = lastNode;
                }
        }
        lowestF = 1000;
        for(Node node:openList) {
            if(node.f <= lowestF) {
                lowestF = node.f;
                bestNode = node;
            }
        }
        if(openList.isEmpty() && bestNode != targetNode) {
            System.out.println("No Path possible");
            return;
        }
        openList.remove(bestNode);
        closedList.add(bestNode);
        lastNode = bestNode;
        lastNode.setState(State.SEARCHED);
    }

    reconstructPath();
}

public void reconstructPath() {
    Node lastNode = targetNode;
    while(lastNode != startNode) {
        lastNode = lastNode.parentNode;
        lastNode.setState(State.PATH);
    }
    setStartAndEnd();
}

And the Node Class:

public class Node {

public enum State {
    NORMAL, BLOCKED, START, END, SEARCHED, PATH
}

public State state;
int xPos, yPos;
Color color;
Node parentNode;

int f;
int movementCost = 10;
int heuristic;

public Node(int x, int y) {
    xPos = x;
    yPos = y;
    setState(State.NORMAL);
}

public void setState(State newState) {  
    state = newState;
}

public boolean isNodeClicked() {
    int inputX = Gdx.input.getX();
    int inputY = Gdx.graphics.getHeight() - Gdx.input.getY();
    if(inputX > xPos*32 && inputX < xPos*32+32 && 
        inputY > yPos*32 && inputY < yPos*32+32) {
        return true;
    }

    return false;
}

public void calculateHeuristic(Node targetNode) {
    heuristic = (Math.abs((xPos-targetNode.xPos)) + Math.abs((yPos-targetNode.yPos))) * movementCost;
    f = movementCost+heuristic;
}

public int calculateHeuristic(Node finishNode, int useless) {
    return (Math.abs((xPos-finishNode.xPos)) + Math.abs((yPos-finishNode.yPos))) * movementCost;
}

}

At the moment I'm using a 2-dimensional array for the map or nodes and Arraylist for open and closed list.

It'd be much appreciated if somebody could help me get my A-star to behave and explain to me what I did wrong, I would also be very grateful for any other criticism, since I want to improve my programming :)

Thanks for your help in Advance :)

Answer 1

Your problem is here:

public void calculateHeuristic(Node targetNode) {
    heuristic = (Math.abs((xPos-targetNode.xPos)) + Math.abs((yPos- targetNode.yPos))) * movementCost;
    f = movementCost+heuristic;
}

Your calculation of your heuristic is wrong, because your calculation of your movementCost is wrong. The cost of a node is not a fixed value. It's the summation of all of the costs to move between nodes along the path to that node so far. So your node should actually have a function,

public int calculateCost(){
    if(parentNode != null){
        return movementCost + parentNode.calculateCost();
    } else{
        return movementCost;
    }
}

And your heuristic thus becomes:

public void calculateHeuristic(Node targetNode) {
    heuristic = (Math.abs((xPos-targetNode.xPos)) + Math.abs((yPos- targetNode.yPos))) * movementCost;
    f = calculateCost()+heuristic;
}

Your other problems look like they probably all come from the various typos/logical errors I mentioned in the comments (while(...||openSet.isEmpty()) instead of while(...|| !openSet.isEmpty()), etc)