免责声明：我对Java的一些背景知识，因为我是predominantly C＃开发人员

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

想拥有Java实现的A *算法。 是的，我看到了同样的网上的很多版本，我无法在它们之间做出选择。

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.

我要寻找一个A *算法的实现，使用Java的所有新功能，使得算法快（即使一点点位）。原因是，我们正在实施，对于在一个 网​​络游戏 等，性能是重中之重。

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.

任何指针（在ATLEAST去哪里找）？

Any pointers ( on atleast where to look ) ?

推荐答案

试几种，度量，选择最快的，适应你的需求。性能主要是由启发函数的选择，这是独立的确定A *正确的。

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.

如果启发式是固定的，优先级队列的实施很可能会成为瓶颈，所以尽量配对堆的。这些都是一些速度最快的堆数据结构在实践中，他们有优势的二进制堆，他们允许O（1）插入时间+摊销O（log n）的弹出分钟。这是在许多A *循环，其中队列被填满，但从来没有完全排空，即预期的情况下重要的是，插入的数目比啪啪的数量要大得多。

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.

如果内存成为一个问题，切换到迭代加深A *（IDA *）或递归最优先搜索（的RBFs）。

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

如果实在不行，可以考虑使用一种近似算法（贪婪搜索）。简单地优化体面书面A *循环是不会给你巨大的速度提升。

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.