寻路算法：A* 与跳跃点搜索
Path finding Algorithms : A* Vs Jump Point Search
我知道 A* 比 Dijkstra 算法更好，因为它考虑了启发式值，但是从 A* 和跳点搜索来看，在有障碍的环境中寻找最短路径的最有效算法是什么？有什么区别？
跳点搜索是基于图上某些条件的改进 A*。因此，如果你满足这些条件（主要是统一成本网格），JPS 严格优于 A*（相同的最优性，最好的情况可以好几个数量级，最坏的情况可能是相同的复杂性，但
稍微差一点的常量），但如果不满足条件，则不能使用。
JPS相对于A*的改进基本上是，如果你有一个具有统一成本函数的图（从A到B和从B到C的成本相同，方向相同），你可以某些情况下可以跳过一些步骤，直接从A到C，不展开B中的节点。
JPS 是一种基于 A* 的修剪技术，您删除不需要评估的案例，因为您知道它们将是次优的。你知道这一点是因为统一成本网格条件。
从概念上讲，这等同于在非均匀网格上使用 A*，其中相邻节点表示您在该方向上可以走多远而不会遇到障碍，以及您执行的跳跃成本。因此，如果您可以在不遇到障碍的情况下向右走 10 个节点，则可以将此（或直接跳转到）成本降低为 10*c 的单个节点，其中 c 是从一个节点到的（恒定）成本另一个在右边。
原论文可以找到here.
我知道 A* 比 Dijkstra 算法更好，因为它考虑了启发式值，但是从 A* 和跳点搜索来看，在有障碍的环境中寻找最短路径的最有效算法是什么？有什么区别？
跳点搜索是基于图上某些条件的改进 A*。因此，如果你满足这些条件（主要是统一成本网格），JPS 严格优于 A*（相同的最优性，最好的情况可以好几个数量级，最坏的情况可能是相同的复杂性，但 稍微差一点的常量），但如果不满足条件，则不能使用。
JPS相对于A*的改进基本上是，如果你有一个具有统一成本函数的图（从A到B和从B到C的成本相同，方向相同），你可以某些情况下可以跳过一些步骤，直接从A到C，不展开B中的节点。
JPS 是一种基于 A* 的修剪技术，您删除不需要评估的案例，因为您知道它们将是次优的。你知道这一点是因为统一成本网格条件。
从概念上讲，这等同于在非均匀网格上使用 A*，其中相邻节点表示您在该方向上可以走多远而不会遇到障碍，以及您执行的跳跃成本。因此，如果您可以在不遇到障碍的情况下向右走 10 个节点，则可以将此（或直接跳转到）成本降低为 10*c 的单个节点，其中 c 是从一个节点到的（恒定）成本另一个在右边。
原论文可以找到here.