Menu
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 ) ?
1000
A * algorithm is a searching algorithm that searches for the shortest path between the initial and the final state. It is used in various applications, such as maps. In maps the A* algorithm is used to calculate the shortest distance between the source (initial state) and the destination (final state).
I'm quite sure the * (star) in the A* algorithm means that the algorithm is admissible, i.e. it is guaranteed that it finds the shortest path in the graph if this path exists (when the heuristic employed is optimistic).
A* Algorithm- A* Algorithm is one of the best and popular techniques used for path finding and graph traversals. A lot of games and web-based maps use this algorithm for finding the shortest path efficiently. It is essentially a best first search algorithm.
A* Search Algorithm is a simple and efficient search algorithm that can be used to find the optimal path between two nodes in a graph. It will be used for the shortest path finding. It is an extension of Dijkstra's shortest path algorithm (Dijkstra's Algorithm).
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.
60
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
