0
\$\begingroup\$

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: 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: 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".

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

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.

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

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.