2024年6月11日发(作者：)

从头理解JPS寻路算法

JPS（Jump Point Search）寻路算法是一种高效的路径算法，其核心

思想是通过优化跳跃点来减少的节点数量，从而提高寻路效率。本文将从

头理解JPS寻路算法，并详细介绍其原理、流程和关键步骤。

一、JPS寻路算法原理

JPS寻路算法基于A*（A star）算法，但通过引入跳跃点的概念来减

少路径的节点数量。跳跃点是一种特殊类型的节点，它们对路径具有重要

的作用。JPS算法通过识别和利用每个节点上的跳跃点，来跳过不必要的

检查和，从而加速路径的查找。

二、JPS寻路算法流程

1.初始化起始节点和目标节点，将起始节点加入开启列表。

2.当开启列表非空时，重复以下步骤：

-从开启列表中选择最佳节点作为当前节点，并将其从开启列表中移

出。

-将当前节点加入封闭列表。

-如果当前节点是目标节点，表示已找到路径，结束。

-否则，计算当前节点的所有邻居节点（包括跳跃点和普通节点）。

-对于每个邻居节点，进行以下处理：

-如果邻居节点已在封闭列表中，跳过该节点。

-计算邻居节点的G值（从起始节点到邻居节点的实际代价）。

-如果邻居节点不在开启列表中，将其加入开启列表，并更新其G值

和父节点。

-如果邻居节点已在开启列表中，检查是否通过当前节点到达该节点

更短，如果是则更新其G值和父节点。

3.如果开启列表为空，表示未找到路径。

三、JPS寻路算法关键步骤

1.节点的扩展方式：JPS算法通过事先查找每个节点的跳跃点来减少

的节点数量。节点的扩展方式有四种：水平、垂直、对角线和跳跃。

-水平扩展：从当前节点开始，沿着水平方向扩展，直到遇到障碍物

或边界。

-垂直扩展：从当前节点开始，沿着垂直方向扩展，直到遇到障碍物

或边界。

-对角线扩展：从当前节点开始，沿着对角线方向扩展，直到遇到障

碍物、边界或对角线上的一个跳跃点。

-跳跃扩展：从当前节点开始，在每个扩展方向上，找到一个或多个

跳跃点，并沿该跳跃点继续扩展，直到遇到障碍物、边界或目标节点。

2.跳跃点的确定：跳跃点是指在一些方向上可以直接跳过多个节点的

特殊节点。在扩展节点时，JPS算法通过识别和计算每个节点上的跳跃点，

来加速路径。跳跃点的确定需要考虑以下情况：

-水平或垂直扩展：当当前节点从上一个节点水平或垂直移动到下一

个节点时，如果下一个节点的水平方向或垂直方向上存在障碍物或边界，

则该节点为一个跳跃点。

-对角线扩展：对于对角线方向上的扩展，如果上述情况成立，则该

节点为一个跳跃点。

-跳跃扩展：跳跃扩展需要通过递归调用找到路径上的所有跳跃点，

并进行扩展操作。

3.启发式函数的选择：JPS算法中，启发式函数用于评估当前节点和

目标节点之间的距离，以指导路径。常用的启发式函数有曼哈顿距离和欧

几里得距离。选择合适的启发式函数可以在过程中找到更优的路径。

四、JPS寻路算法的优点和应用场景

JPS寻路算法相比传统的A*算法，具有以下优点：

-减少的节点数量：通过引入跳跃点的概念，JPS算法能够有效地跳

过不必要的检查和，从而减少的节点数量。

-提高寻路效率：由于减少了的节点数量，JPS算法能够更快地找到

路径，提高寻路的效率。

-可用于实时应用：由于JPS算法的高效性，它常被用于实时应用，

如游戏开发中的路径规划、机器人导航等领域。

总结：

JPS寻路算法是一种高效的路径算法，通过引入跳跃点来减少的节点

数量，从而提高寻路效率。它的原理基于A*算法，通过识别和利用每个

节点上的跳跃点来跳过不必要的检查和。JPS算法的关键步骤包括节点的

扩展、跳跃点的确定和通过启发式函数进行路径。JPS算法具有减少节点

数量和提高寻路效率的优点，适用于实时应用。