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