Implementation of A Star (A*) Algorithm in Java

java algorithm path-finding a-star
naveen picture naveen · Jan 7, 2011 · Viewed 29.8k times · Source

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

Fred Foo picture Fred Foo · Jan 7, 2011

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.

Related questions

Path finding in a Java 2d Game?

Essentially its a pacman clone game I'm working on. I have an Enemy class, and 4 instances of this class created which all represent 4 ghosts of the game. All ghosts start up in random areas of the screen and then they …

Read More
Finding the max/min value in an array of primitives using Java

It's trivial to write a function to determine the min/max value in an array, such as: /** * * @param chars * @return the max value in the array of chars */ private static int maxValue(char[] chars) { int max = chars[0]; for (int ktr = 0; …

Read More
Generating all permutations of a given string

What is an elegant way to find all the permutations of a string. E.g. permutation for ba, would be ba and ab, but what about longer string such as abcdefgh? Is there any Java implementation example?

Read More