Implementation of A Star (A*) Algorithm in Java

Question

Disclaimer: I have little background in Java, since I am predominantly a C# developer.

Would like to have the java implementation of A* algorithm.
Yes, I saw many versions of the same online and I am unable to choose between them.

I am looking for an A* algorithm implementation that uses all new features of java that makes the algorithm faster(even if a tad bit). The reason is that we are implementing that for path-finding on an MMO and so, performance is the top priority.

Any pointers ( on atleast where to look ) ?

Answer 1

Try several, measure, pick the fastest, adapt to your needs. Performance is mostly determined by the choice of heuristic function, which is independent of A* proper.

If the heuristic is fixed, the implementation of the priority queue is likely to become the bottleneck, so try pairing heaps. These are some of the fastest heap data structures in practice, and they have the advantage over binary heaps that they allow for O(1) insertion time + amortized O(log n) pop-min. This is important in the expected case of many A* loops, where the queue is filled, but never entirely emptied, i.e., the number of insertions is much greater than the number of pops.

If memory becomes an issue, switch to iterative-deepening A* (IDA*) or recursive best-first search (RBFS).

If nothing works, consider using an approximation algorithm (greedy search). Simply optimizing a decently written A* loop isn't going to give you tremendous speed-ups.

See Russell and Norvig for algorithms and a good discussion of the issues.

Answer 2

If performance is your top priority, A* is probably not your best choice. A* provides an exact solution, and as a result will keep processing away until it finds the correct answer. There are other lightweight solutions that give good enough solutions in much faster time: e.g enforced hill climbing or best-first, even a simple depth first.