我编写了一个A*路径查找算法，它可以找到穿过障碍物的路径，并且可以对角移动。我基本上是将链接中的伪代码实现为实际代码，并且使用了二进制堆方法来添加和删除开放列表中的项目。

使用二进制堆显著提升了性能，大约比我之前使用的插入排序算法快了500倍。

问题是，它仍然平均需要150万纳秒左右，也就是大约0.0015秒的时间。

所以问题是，我的计划是制作一个塔防游戏，每当我在地图上添加一个塔时，每个怪物的路径查找都需要更新。如果地图上有大约50个怪物，这意味着更新所有怪物的路径将需要大约0.0015 * 50 = 0.075秒。游戏的每一次更新（所有游戏内内容的更新）是每60分之一秒，也就是0.016秒，所以问题是更新路径所需的时间比更新一次的时间还长，这将导致严重的滞后。所以我应该怎么做呢？我需要找到一个更好的算法来排序开放列表，还是应该将路径查找任务分开，以便每次更新只执行X个路径查找任务，而不是全部执行？

回答：

与其从每个敌人开始搜索到检查点，不如从检查点开始向外搜索到所有敌人。这样，你只需要进行一次搜索，而不是50次。

更具体地说，只需从玩家开始进行广度优先搜索（或者，如果你的图是有权重的，可以使用Dijkstra算法），直到所有敌人都被覆盖。

你可以通过更改你的启发式函数EstimatedDistanceToEnd（即h(x)）为到任何敌人的最小估计值，来调整这个策略以适用于A*，但如果敌人很多，这可能会比更简单的选项慢。启发式函数必须是一致的，这样才能生效。

此外，请确保你使用的是正确的平局处理标准。

最重要的是，请记住，大多数游戏不需要每一帧都运行路径查找算法——通常每秒一次或两次，甚至更少，具体取决于游戏的需求。

如果这仍然太慢，你可以考虑使用D* lite来在后续搜索之间重用信息。但是，我敢打赌，运行一次广度优先搜索将足够快。

（摘自我在gamedev上对类似问题的回答）