12

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 ) ?

Improve this question
3
  • 4
    Can you give us links to versions you already found? And, by the way, using "new features of Java" won't make an algorithm faster. Commented Jan 7, 2011 at 11:23
  • 2
    Link expired again, here's the newest for anyone like me who finds this: github.com/graphhopper/graphhopper/blob/master/core/src/main/… Commented May 12, 2013 at 0:31
  • @BattleBarnes the included bidirectional A* is even faster Commented Jan 23, 2015 at 14:21

2 Answers 2

Reset to default
23

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

what Datastructure should be used for the closedList?
A hash table. Or a red-black tree. Or a splay tree. Or whatever turns out to be fastest. @st0le, you're right that this matters, but in my experience, fast sets are easier to come by than fast priority queues.
@sk0le: if a closed set is needed at all, that is.
@Robert, thanks. "How to implement A*" comes up on SO every now and then, and "read R&N" is almost always the answer ;)
10

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.

Improve this answer

3 Comments

+1. Optimizing A* code won't win the OP a performance trophy.
-0, as yes, A* is probably not that efficient but the alternatives you need are speed-up techniques specific to path-finding like contraction hierarchies and similar.
For the sake of accuracy, A* does not always provide the optimal answer. It only does if the heurstics is admissible.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.