# A* Implementation Produces zig-zag in positive directions

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();

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) {
}

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

Collections.reverse(path);
return path;
}

open.remove(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)) {
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;
}
}

}
}

return null;
}


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

• ispect the get neighbours logic "Node n = q.node.neighbours.get(direction);" – dnk drone.vs.drones Jul 3 '15 at 7:04
• You're right. There was an issue in how I was computing the neighbours! – Petter Thowsen Jul 3 '15 at 8:56

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.

• I fixed that bug. Still same thing though. And yeah getCost does return heuristic + movementCost. – Petter Thowsen Jul 2 '15 at 23:15

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.