java - 用于塔防的 Dijkstra、广度优先还是 A*？

Question

所以我问了一个关于为我的塔防游戏优化我的 A* 的问题，得到了几个答案，说我应该先使用 Dijkstra 或 Breadth 来计算 50 多个敌人的最短距离。

我的问题是

我是先使用广度还是 Dijkstra？dijkstra 比 A* 快吗？它和A*一样准确吗？有什么方法可以优化 A* 而不是二进制堆，这样我就可以使用 A* 计算路径而无需学习 dijkstra？

目前平均需要大约 0.003 秒来计算 30* 30 网格上的长路径，我的 A* 使用二进制堆，但我认为这可能不够快。

Answer 1

DJikstra是具有惰性启发式函数的 A* 的一个单独案例。然后，所有问题都归结为您是否可以提出合适的启发式函数。如果可以的话，A* 会表现得更好，这一点毫无疑问。

Answer 2

对于塔防游戏，您通常希望为每个出口保存最短路径树，并将其用于所有前往该出口的生物。这样，您只需在连接发生变化时（即建造或摧毁塔时）重新计算一次。

由于无论如何您都想计算完整的最短路径树，因此您不妨使用普通的旧Dijkstra 算法而不是更复杂的 A*。

但是，也可以根据需要使用“增量 A*”来构建最短路径树。基本上，你会从目标运行 A* 到 mob，当你到达目标时保存算法的状态（包括到目前为止构建的部分最短路径树），然后恢复它（使用不同的目标和启发式）当您接下来需要从树尚未覆盖的某个点找到通往该目标的路径时。您甚至可以在添加或移除塔时对树进行增量更新，尽管这会变得有点复杂。