A* Implementation Produces zig-zag in positive directions

Question

I have an implementation of A* in Java. I followed this guide http://www.policyalmanac.org/games/aStarTutorial.htm.

But I noticed that the paths generated where the goal is in the positive X and Y direction, I get this zig-zag phenomenon.

Let me demonstrate with these two images (top left area is the origin [0,0]):

Here I generate a path where the goal is farther away from the origin than the start: And here I generate a path where the goal is closer to the origin than the start: I have tried to manipulate the heuristic algorithm I use, to no avail.

Here's the code:

public List<Vector3f> find(Vector3f startLocation, Vector3f goalLocation, NodeValidator validator) {
    start = nodes.get(grid.getNode(startLocation).index);
    goal = nodes.get(grid.getNode(goalLocation).index);

    if ( ! validator.validate(goal.node)) return null;

    open.clear();
    closed.clear();

    open.add(start);

    start.movementCost = 0;
    start.heuristic = 0;

    while(open.isEmpty() == false) {
        NodeProxy q = null;

        for(NodeProxy node : open) {
            if (q == null || node.getCost() < q.getCost()) {
                q = node;
            }
        }

        //did we get the goal?
        if (q == goal) {               
            List<Vector3f> path = new ArrayList<Vector3f>();

            //get goal node
            NodeProxy nodeProxy = goal;
            while(nodeProxy != start && nodeProxy != null) {
                if (nodeProxy != null) {
                    path.add(nodeProxy.node.center);
                }

                if (nodeProxy.parent == null) {
                    break;
                }
                nodeProxy = nodeProxy.parent;
            }

            Collections.reverse(path);
            return path;
        }

        open.remove(q);
        closed.add(q);

        float g;
        for(Compass direction : Compass.values()) {
            Node n = q.node.neighbours.get(direction);
            if (n == null) continue;

            NodeProxy successor = nodes.get(n.index);

            g = direction.cost;

            if (validator.validate(successor.node) && closed.contains(successor) == false) {
                if ( ! open.contains(successor)) {
                    open.add(successor);
                    successor.movementCost = q.movementCost + g;
                    successor.heuristic = getHeuristic(successor.node, goal.node);
                    successor.parent = q;
                }else if (q.movementCost < successor.movementCost + g) {
                    successor.movementCost = q.movementCost + g;
                    successor.heuristic = getHeuristic(successor.node, goal.node);
                    successor.parent = q;
                }
            }

            closed.add(q);
        }
    }

    return null;
}

Some notes regarding the code: The validator object is simply an object tasked with checking if a node is "walkable".

Answer 1

this line:

if (q.movementCost < successor.movementCost + g)

should look like:

if (q.movementCost + g < succesor.movementCost)

also remember that function getCost() should return heuristic + movementCost.

Answer 2

The issue was that, the way I computed the neighbours was based on a normalized direction vector. But of course, those don't work for diagonals.

Except, that they kinda did, in my case, but only in the positive directions.

Because when I ask the A* grid to "getNode(Vector3f location)", it does this to the input vector:

location.x -= location.x % nodeSize
location.z -= location.z % nodeSize;

So, basically: Use a grid location for each node, where nodes have a size of 1. Just multiply or divide by node size whenever you translate from grid space to world space etc.