所以基本上我编写了一个 A* 探路者，它可以找到穿过障碍物的路径并进行诊断。我基本上将http://www.policyalmanac.org/games/aStarTutorial.htm中的伪代码实现为真实代码，并使用二进制堆方法从 openlist 添加和删除项目。
使用二叉堆可以显着提升性能，比我之前使用的插入排序算法快大约 500 倍。
问题是它仍然平均需要大约 150 万纳秒，大约是 0.0015 秒。
所以问题是，我的计划是制作一个塔防游戏，每次我在地图上添加一个塔时，每个暴徒的寻路都需要更新。如果我在地图上最多有大约 50 个小怪，这意味着更新整个小怪的所有路径大约需要 0.0015 * 50 = 0.075 秒。游戏基本上每 1/60 秒（即 0.016 秒）打勾（所有游戏内容更新），所以问题是更新路径的时间比打勾的时间长，这将导致巨大的延迟。那么我该怎么做呢？我是否需要找到一种更好的算法来对 openlist 进行排序，或者以某种方式划分寻路任务，以便每个刻度仅执行 X 个寻路任务，而不是所有任务。
与其从每个敌人搜索到检查站，不如从检查站向外搜索到每个敌人。这样，您只需进行一次搜索，而不是进行 50 次搜索。
更具体地说，只需从玩家向外进行广度优先搜索（或djikstra's，如果您的图表是加权的），直到到达每个敌人。
EstimatedDistanceToEnd 您可以通过将启发式（aka h(x)）更改为对任何敌人的最小估计来更改此策略以使用 A* ，但是对于很多敌人，这最终可能会比更简单的选项慢。启发式必须是一致的才能起作用。
此外，请确保您使用了正确的平局标准。
此外，最重要的是，请记住，对于大多数游戏，您不需要在每一帧都运行探路者- 通常您每秒只能运行一次或两次，甚至更少，具体取决于游戏。
如果这仍然太慢，您可以考虑使用D* lite在后续搜索之间重用信息。但是，我敢打赌，运行单一的广度优先搜索将绰绰有余。
（复制自我对 gamedev 上类似问题的回答）
您是否考虑过 Floyd-Warshall 算法？
本质上，A* 用于从单个源到一个或多个目的地的路径查找。然而，在塔防中（当然取决于你的规则），它是关于在地图上导航的多个来源。
因此，对于这一点，弗洛伊德的算法似乎更优化。但是，您可以让您的 A* 算法找到单元组而不是单个单元的路径，这样可以优化您的计算时间。
据推测，您可以从出口向后搜索所有小兵，因此您只需要探索一次迷宫。