所以基本上我编写了一个 A* 探路者，它可以找到穿过障碍物的路径并进行诊断。我基本上是将 http://www.policyalmanac.org/games/aStarTutorial.htm 中的伪代码实现为真正的代码，并且还使用了二进制堆方法来添加和删除 openlist 中的项目。
使用二叉堆显着提升了性能，比我之前使用的插入排序算法快 500 倍。
问题是它仍然平均需要大约 150 万纳秒，也就是大约 0.0015 秒。
所以问题是，我的计划是制作一个塔防游戏，每次我在 map 上添加一个塔时，每个生物的寻路都需要更新。如果我在 map 上最多有 50 只左右的生物，这意味着更新整个生物的所有路径大约需要 0.0015 * 50 = .075 秒。游戏基本上每 1/60 秒(即 0.016 秒)滴答一次(所有游戏内容更新)，因此问题是更新路径所需的时间比滴答所需的时间长，这将导致大量滞后。那么我应该怎么做呢？我是否需要找到一种更好的算法来对 openlist 进行排序，或者以某种方式划分寻路任务，以便每个滴答声只执行 X 个寻路任务，而不是所有这些任务。
最佳答案
不是从每个敌人搜索到检查点，而是立即从检查点向外搜索到每个敌人。这样，您只需进行一次搜索，而不是进行 50 次搜索。
更具体地说，只需从玩家向外进行广度优先搜索(或 djikstra's ，如果您的图是加权的)，直到遇到每个敌人。
您可以通过将启发式 EstimatedDistanceToEnd(又名 h(x) )更改为对任何敌人的最小估计来更改此策略以使用 A*，但是对于许多敌人，这最终可能比更简单的选项慢。启发式必须是 consistent 才能工作。
此外，请确保您使用的是 correct tie-breaking criteria 。
此外，最重要的是，请记住 对于大多数游戏，您不需要在每一帧 中运行探路者 - 通常您每秒只能运行一两次，甚至更少，具体取决于游戏。
如果这仍然太慢，您可以考虑使用 D* lite 在后续搜索之间重用信息。但是，我敢打赌，运行单个广度优先搜索将足够快。
(复制自我在 gamedev 上对 a similar question 的回答)
关于java - 如何提高我的 A* 寻路者的性能？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/15114950/