A* (A star) algorithm optimization

Question

I'm a student and me and my team have to make a simulation of student's behaviour in a campus (like making "groups of friends") walking etc. For finding path that student has to go, I used A* algorithm (as I found out that its one of fastest path-finding algorithms). Unfortunately our simulation doesn't run fluently (it takes like 1-2 sec between successive iterations). I wanted to optimize the algorithm but I don't have any idea what I can do more. Can you guys help me out and share with me information if its possible to optimize my A* algorithm? Here goes code:

  public LinkedList<Field> getPath(Field start, Field exit) {


    LinkedList<Field> foundPath = new LinkedList<Field>();
    LinkedList<Field> opensList= new LinkedList<Field>();
    LinkedList<Field> closedList= new LinkedList<Field>();
    Hashtable<Field, Integer> gscore = new Hashtable<Field, Integer>();
    Hashtable<Field, Field> cameFrom = new Hashtable<Field, Field>();
    Field x = new Field();
    gscore.put(start, 0);
    opensList.add(start);
    while(!opensList.isEmpty()){

        int min = -1;
        //searching for minimal F score
        for(Field f : opensList){
            if(min==-1){
                min = gscore.get(f)+getH(f,exit);
                x = f;
            }else{
                int currf = gscore.get(f)+getH(f,exit);
                if(min > currf){
                    min = currf;
                    x = f;
                }
            }
        }
        if(x == exit){
            //path reconstruction
            Field curr = exit;
            while(curr != start){
                foundPath.addFirst(curr);
                curr = cameFrom.get(curr);
            }
            return foundPath;
        }
        opensList.remove(x);
        closedList.add(x);
        for(Field y : x.getNeighbourhood()){
            if(!(y.getType()==FieldTypes.PAVEMENT ||y.getType() == FieldTypes.GRASS) || closedList.contains(y) || !(y.getStudent()==null))
                            {
                continue;
            }
            int tentGScore = gscore.get(x) + getDist(x,y);
            boolean distIsBetter = false;
            if(!opensList.contains(y)){
                opensList.add(y);
                distIsBetter = true;
            }else if(tentGScore < gscore.get(y)){
                distIsBetter = true;
            }
            if(distIsBetter){
                cameFrom.put(y, x);
                gscore.put(y, tentGScore);
            }               
        }
    }

    return foundPath;
}

 private int getH(Field start, Field end){
    int x;
    int y;
    x = start.getX()-end.getX();
    y = start.getY() - end.getY();
    if(x<0){
        x = x* (-1);
    }
    if(y<0){
        y = y * (-1);
    }
    return x+y;
}
private int getDist(Field start, Field end){
    int ret = 0;
    if(end.getType() == FieldTypes.PAVEMENT){
        ret = 8;
    }else if(start.getX() == end.getX() || start.getY() == end.getY()){
        ret = 10;
    }else{
        ret = 14;
    }

    return ret;
}

//EDIT

This is what i got from jProfiler:

So getH is a bottlneck yes? Maybe remembering H score of field would be a good idea?

Answer 1

A linked list is not a good data structure for the open set. You have to find the node with the smallest F from it, you can either search through the list in O(n) or insert in sorted position in O(n), either way it's O(n). With a heap it's only O(log n). Updating the G score would remain O(n) (since you have to find the node first), unless you also added a HashTable from nodes to indexes in the heap.

A linked list is also not a good data structure for the closed set, where you need fast "Contains", which is O(n) in a linked list. You should use a HashSet for that.

Answer 2

You can optimize the problem by using a different algorithm, the following page illustrates and compares many different aglorihms and heuristics:

• A*
• IDA*
• Djikstra
• JumpPoint
• ...

http://qiao.github.io/PathFinding.js/visual/

Answer 3

From your implementation it seems that you are using naive A* algorithm. Use following way:-

1. A* is algorithm which is implemented using priority queue similar to BFS.

2. Heuristic function is evaluated at each node to define its fitness to be selected as next node to be visited.

3. As new node is visited its neighboring unvisited nodes are added into queue with its heuristic values as keys.

4. Do this till every heuristic value in the queue is less than(or greater) calculated value of goal state.

Answer 4

1. Find bottlenecks of your implementation using profiler . ex. jprofiler is easy to use
2. Use threads in areas where algorithm can run simultaneously.
3. Profile your JavaVM to run faster. Allocate more RAM

Answer 5

a) As mentioned, you should use a heap in A* - either a basic binary heap or a pairing heap which should be theoretically faster.

b) In larger maps, it always happens that you need some time for the algorithm to run (i.e., when you request a path, it will simply have to take some time). What can be done is to use some local navigation algorithm (e.g., "run directly to the target") while the path computes.

c) If you have reasonable amount of locations (e.g., in a navmesh) and some time at the start of your code, why not to use Floyd-Warshall's algorithm? Using that, you can the information where to go next in O(1).

Answer 6

I built a new pathfinding algorithm. called Fast* or Fastaer, It is a BFS like A* but is faster and efficient than A*, the accuracy is 90% A*. please see this link for info and demo.

https://drbendanilloportfolio.wordpress.com/2015/08/14/fastaer-pathfinder/

It has a fast greedy line tracer, to make path straighter. The demo file has it all. Check Task manager when using the demo for performance metrics. So far upon building this the profiler results of this has maximum surviving generation of 4 and low to nil GC time.