CODEWITHSUNDEEP
javaalgorithmpath-findinga-starheuristics
Jh62
Jh62

Reputation: 334

A-Star Pathfinding choosing bad waypoints

SOLVED: I'm sorry. I was reconstructing improperly the path. I thought closedSet had all the waypoints from start to end only, but it has some other waypoints too. I miss understood the concept. Now it's working okey!

I'm still getting some trouble with A*.

My character is finding his path, but sometimes, depending where i click on the map, the algorithm finds the shortest path or the path, but with many nodes that shouldn't be selected.

I've tried to follow Wikipedia's and A* Pathfinding for Beginner's implementation, but they give me the same result. I don't know if it is the heuristic or the algorithm itself, but something's not right.

And this is an example of the problem clicking two different nodes: https://i.sstatic.net/dXuEm.jpg

Here's the Pathfind class:

import java.util.ArrayList;
import java.util.Collections;
import java.util.TreeSet;

public class Pathfind {
public Pathfind(){

}

public ArrayList<Node> findPath(Node start, Node end, ArrayList<Node> nodes){

    ArrayList<Node> openSet = new ArrayList<Node>();
    ArrayList<Node> closedSet = new ArrayList<Node>();

    Node current;

    openSet.add(start);

    while(openSet.size() > 0){

        current = openSet.get(0);

        current.setH_cost(ManhattanDistance(current, end));

        if(start == end) return null;           
        else if(closedSet.contains(end)){
            System.out.println("Path found!");
            return closedSet;
        }

        openSet.remove(current);
        closedSet.add(current);

        for(Node n : current.getNeigbours()){           
            if(!closedSet.contains(n)){     
                if(!openSet.contains(n) || (n.getG_cost() < (current.getG_cost()+10))){ 
                    n.setParent(current);
                    n.setG_cost(current.getG_cost()+10);
                    n.setH_cost(ManhattanDistance(n, end));

                        if(!openSet.contains(n))
                            openSet.add(n);

                    Collections.sort(openSet);
                }
            }
        }
    }       

    return null;
}

private int ManhattanDistance(Node start, Node end){
    int cost = start.getPenalty();

    int fromX = start.x, fromY = start.y;
    int toX = end.x, toY = end.y;

    return cost * (Math.abs(fromX - toX) + Math.abs(fromY - toY));
}

}

Upvotes: 3

Views: 1549

Answers (2)

amit
amit

Reputation: 178411

I believe the bug is with the condition:

if(n.getCost() < current.getCost()){

You shouldn't prevent advancing if the cost (g(node)+h(node)) is decreasing from the current. Have a look at this counter example: (S is the source and T is the target)

_________
|S |x1|x2|
----------
|x3|x4|x5|
---------
|x6|x7|T |
----------

Now, Assume you are at S, you haven't moved yet so g(S) =0, and under the manhattan distance heuristic, h(S) = 4, so you get f(S)=4

Now, have a look at x1,x3: Assuming you are taking one step to each, they will have g(x1)=g(x3)=1, and both will have h(x1)=h(x3)=3 under the same heuristic. It will result in f(x1)=f(x3)=4 - and your if condition will cause none to "open", thus once you finish iterating on S - you will not push anything to open - and your search will terminate.

As a side note:
I believe the choice of closedSet as ArrayList is not efficient. each contains() op is O(n) (where n is the number of closed nodes). You should use a Set for better performance - A HashSet is a wise choice, and if you want to maintain the order of insertion - you should use a LinkedHashSet. (Note you will have to override equals() and hashCode() methods of Node)

Upvotes: 1

BlueRaja - Danny Pflughoeft
BlueRaja - Danny Pflughoeft

Reputation: 85966

Do your units walk up/down/left/right only, or can they take diagonals as well?

The one requirement for the A*-heuristic is that it's admissible - it must never over-estimate the actual path-length. If your units can walk diagonally, then manhatten-distance will over-estimate the path-length, and thus A* is not guaranteed to work.

Upvotes: 0

Related Questions