【Jump Point Search 路径规划算法 C++实现教程】
Jump Point Search 算法是一种基于图搜索的路径规划算法，主要用于在二维网格地图中寻找从起点到终点的最短路径。与传统的 A*算法相比，JPS 算法通过对搜索空间进行预处理和跳跃点的识别，能够大大减少搜索节点的数量，从而提高搜索效率。在Jps.h文件中，定义了 JPS 算法所需的数据结构。Direct枚举类型表示八个方向：上（p_up）、下（p_down）、左（p_left）、右（p_
·
Jump Point Search 路径规划算法 C++实现教程
Jump Point Search 路径规划算法 C++实现教程
在路径规划领域，A算法是一种经典且广泛应用的算法，而 Jump Point Search（JPS）算法则是一种相对较新的高效路径规划算法。本文将介绍 JPS 算法的 C++实现，并与 A算法进行差异对比。
需要参考博客【A*路径规划算法 C++实现教程】才可以进行对比实验😊😊😊,地图文件同在
参考博客：路径规划 | 图搜索算法：JPS
一、JPS 算法简介
Jump Point Search 算法是一种基于图搜索的路径规划算法，主要用于在二维网格地图中寻找从起点到终点的最短路径。与传统的 A*算法相比，JPS 算法通过对搜索空间进行预处理和跳跃点的识别，能够大大减少搜索节点的数量，从而提高搜索效率。
二、JPS 算法的 C++实现
1. 数据结构定义
在Jps.h文件中，定义了 JPS 算法所需的数据结构。
Direct枚举类型表示八个方向：上（p_up）、下（p_down）、左（p_left）、右（p_right）、左上（p_leftup）、左下（p_leftdown）、右上（p_rightup）、右下（p_rightdown）。PathNode结构体表示辅助地图中的节点，包含行和列坐标（row、col）、从起点到当前节点的实际代价g、从当前节点到终点的估计代价h、总代价f、节点的值（表示是否为障碍物）、是否为最短路径中的一点（isroute）、是否被走过（isfind）、是否在开放列表中（inopen）、是否为空节点（isnull）以及父节点指针（parent）和关键邻居节点列表（keyNeighbours）。
2. 函数实现
在Jps.c文件中，实现了 JPS 算法的各个函数。
Prune函数用于判断邻居类型，确定是否是最佳邻居和强迫邻居。根据单元地图的 8 位二进制格式、父节点位置和检测的邻居位置，判断邻居的类型。Init函数用于初始化 JPS 算法所需的辅助地图。它接受输入的二维地图、地图高度和宽度，为辅助地图分配内存并初始化每个节点。JumpStraight函数实现直跳跃，即在指定方向上进行搜索，直到找到跳点、碰到障碍物或超出地图。它通过不断沿着指定方向前进，检查搜索点周围的 3x3 单元地图，判断是否存在强迫邻居或超出地图范围。JumpOblique函数实现斜跳跃，与直跳跃类似，但在斜向方向上进行搜索。同样，它会检查搜索点周围的单元地图，判断是否存在强迫邻居或超出地图范围。如果存在强迫邻居，则返回当前搜索点；如果没有，则向当前点的直线“真·邻居”做直跳跃，如果直跳跃不返回空，则返回当前点。FindPath函数是 JPS 算法的核心函数，用于寻找从起点到终点的路径。它通过不断从开放列表中选择具有最小f值的节点作为当前节点，然后向所有“真·邻居”方向跳跃，更新开放列表和辅助地图中的节点属性。当找到终点或者开放列表为空时，算法结束。最后，通过回溯父节点的方式构建路径，并进行逐点插值以得到更平滑的路径。interpolate函数用于计算两个点之间的差值，通过逐点插值的方式在两点之间生成一系列中间点，以得到更平滑的路径。PrintRoute函数用于打印路径和路径总长度。PrintRouteMap函数用于打印带有路径标记的地图。
2.1 jps.cpp
#include"jps.h"
//判断邻居类型，是否是最佳邻居和强迫邻居
//入参：单元地图8位二进制格式(十进制范围0-255)，父节点位置(0-8)、检测的邻居的位置(0-8)
//当前点在单元地图的中心（4）位置
bool* Jps::Prune(short unitMap,char p,char n){
static bool retType[2];//返回的类型
char obstaclePos = 0;
#if 0
//单元地图预处理
char unitMapTmp =0;
if(p ==0){//单元地图顺时针转180度
unitMapTmp = unitMapTmp | (unitMap<<8 &(1<<8) );//0->8
unitMapTmp = unitMapTmp | (unitMap<<6 &(1<<7) );//1->7
unitMapTmp = unitMapTmp | (unitMap<<4 &(1<<6) );//2->6
unitMapTmp = unitMapTmp | (unitMap<<2 &(1<<5) );//3->5
unitMapTmp = unitMapTmp | (unitMap>>2 &(1<<3) );//5->3
unitMapTmp = unitMapTmp | (unitMap>>4 &(1<<2) );//6->2
unitMapTmp = unitMapTmp | (unitMap>>6 &(1<<1) );//7->1
unitMapTmp = unitMapTmp | (unitMap>>8 &(1<<0) );//8->0
p = 8;
}
#endif // 0
if(p == 0){
if(n ==7 ||n ==5 || n ==8){
retType[0] = true;
retType[1] = false;
}
if(n ==2){
obstaclePos = unitMap>>1 & 0x01;
if( 1 == obstaclePos){
retType[0] = true;
retType[1] = true;
}
if( 0 == obstaclePos){
retType[0] = false;
retType[1] = false;
}
}
if(n ==6){
obstaclePos = unitMap>>3 & 0x01;
if( 1 == obstaclePos){
retType[0] = true;
retType[1] = true;
}
if( 0 == obstaclePos){
retType[0] = false;
retType[1] = false;
}
}
if(n == 1||n ==3){
retType[0] = false;
retType[1] = false;
}
}
if(p == 1){
if(n ==7){
retType[0] = true;
retType[1] = false;
}
if(n ==6){
obstaclePos = unitMap>>3 & 0x01;
if( 1 == obstaclePos){
retType[0] = true;
retType[1] = true;
}
if( 0 == obstaclePos){
retType[0] = false;
retType[1] = false;
}
}
if(n ==8){
obstaclePos = unitMap>>5 & 0x01;
if( 1 == obstaclePos){
retType[0] = true;
retType[1] = true;
}
if( 0 == obstaclePos){
retType[0] = false;
retType[1] = false;
}
}
if(n == 0||n ==2||n ==3||n ==5){
retType[0] = false;
retType[1] = false;
}
}
if(p == 2){
if(n ==7 ||n ==6 || n ==3){
retType[0] = true;
retType[1] = false;
}
if(n ==0){
obstaclePos = unitMap>>1 & 0x01;
if( 1 == obstaclePos){
retType[0] = true;
retType[1] = true;
}
if( 0 == obstaclePos){
retType[0] = false;
retType[1] = false;
}
}
if(n ==8){
obstaclePos = unitMap>>5 & 0x01;
if( 1 == obstaclePos){
retType[0] = true;
retType[1] = true;
}
if( 0 == obstaclePos){
retType[0] = false;
retType[1] = false;
}
}
if(n == 1||n ==5){
retType[0] = false;
retType[1] = false;
}
}
if(p == 3){
if(n ==5){
retType[0] = true;
retType[1] = false;
}
if(n ==2){
obstaclePos = unitMap>>1 & 0x01;
if( 1 == obstaclePos){
retType[0] = true;
retType[1] = true;
}
if( 0 == obstaclePos){
retType[0] = false;
retType[1] = false;
}
}
if(n ==8){
obstaclePos = unitMap>>7 & 0x01;
if( 1 == obstaclePos){
retType[0] = true;
retType[1] = true;
}
if( 0 == obstaclePos){
retType[0] = false;
retType[1] = false;
}
}
if(n == 0||n ==1||n ==6||n ==7){
retType[0] = false;
retType[1] = false;
}
}
if(p == 5){
if(n ==3){
retType[0] = true;
retType[1] = false;
}
if(n ==0){
obstaclePos = unitMap>>1 & 0x01;
if( 1 == obstaclePos){
retType[0] = true;
retType[1] = true;
}
if( 0 == obstaclePos){
retType[0] = false;
retType[1] = false;
}
}
if(n ==6){
obstaclePos = unitMap>>7 & 0x01;
if( 1 == obstaclePos){
retType[0] = true;
retType[1] = true;
}
if( 0 == obstaclePos){
retType[0] = false;
retType[1] = false;
}
}
if(n == 1||n ==2||n ==7||n ==8){
retType[0] = false;
retType[1] = false;
}
}
if(p == 6){
if(n ==1 ||n ==2 || n ==5){
retType[0] = true;
retType[1] = false;
}
if(n ==0){
obstaclePos = unitMap>>3 & 0x01;
if( 1 == obstaclePos){
retType[0] = true;
retType[1] = true;
}
if( 0 == obstaclePos){
retType[0] = false;
retType[1] = false;
}
}
if(n ==8){
obstaclePos = unitMap>>7 & 0x01;
if( 1 == obstaclePos){
retType[0] = true;
retType[1] = true;
}
if( 0 == obstaclePos){
retType[0] = false;
retType[1] = false;
}
}
if(n == 3||n ==7){
retType[0] = false;
retType[1] = false;
}
}
if(p == 7){
if(n ==1){
retType[0] = true;
retType[1] = false;
}
if(n ==0){
obstaclePos = unitMap>>3 & 0x01;
if( 1 == obstaclePos){
retType[0] = true;
retType[1] = true;
}
if( 0 == obstaclePos){
retType[0] = false;
retType[1] = false;
}
}
if(n ==2){
obstaclePos = unitMap>>5 & 0x01;
if( 1 == obstaclePos){
retType[0] = true;
retType[1] = true;
}
if( 0 == obstaclePos){
retType[0] = false;
retType[1] = false;
}
}
if(n == 3||n ==5||n ==6||n ==8){
retType[0] = false;
retType[1] = false;
}
}
if(p == 8){
if(n ==0 ||n ==1 || n ==3){
retType[0] = true;
retType[1] = false;
}
if(n ==2){
obstaclePos = unitMap>>5 & 0x01;
if( 1 == obstaclePos){
retType[0] = true;
retType[1] = true;
}
if( 0 == obstaclePos){
retType[0] = false;
retType[1] = false;
}
}
if(n ==6){
obstaclePos = unitMap>>7 & 0x01;
if( 1 == obstaclePos){
retType[0] = true;
retType[1] = true;
}
if( 0 == obstaclePos){
retType[0] = false;
retType[1] = false;
}
}
if(n == 5||n ==7){
retType[0] = false;
retType[1] = false;
}
}
return retType;
}
void Jps::Init(int **_map,int _height,int _width){
//初始化空节点
nullNode.isnull = true;
height = _height;
width = _width;
//建立辅助地图
pathMap = new PathNode**[height];
for(int i=0;i<height;i++){
pathMap[i] = new PathNode*[width];
for(int j=0;j<width;j++){
pathMap[i][j] = new PathNode;
memset(pathMap[i][j],0, sizeof(PathNode));
pathMap[i][j]->row = i;
pathMap[i][j]->col = j;
pathMap[i][j]->isfind = false;
pathMap[i][j]->isroute = false;
pathMap[i][j]->value = _map[i][j];
}
}
}
//直跳跃
//入参：辅助地图、当前节点、直跳跃方向-x方向值，y方向值
//返回跳点
Jps::PathNode Jps::JumpStraight(PathNode*** _pathMap,PathNode currenNode,Direct dir){
int delta_x = 0;
int delta_y = 0;
short unitMap = 0;
char valueT = 0;//存储辅助地图中点的临时值，用于算出单元地图值
bool* nodeTyp;
char parent;//单元地图中，父节点
char neighbGroup[9] = {9,9,9,9,9,9,9,9,9};//单元地图中,要探测的邻居组，初始化为非(0-8)的值，为9的点为不可行点
switch(dir)
{
case p_up:
delta_x = 0;
delta_y = -1;
parent = 7;
break;
case p_down:
delta_x = 0;
delta_y = 1;
parent = 1;
break;
case p_left:
delta_x = -1;
delta_y = 0;
parent = 5;
break;
case p_right:
delta_x = 1;
delta_y = 0;
parent = 3;
break;
default:
break;
}
PathNode nodeTmp = currenNode;//沿指定方向搜寻的点
//沿指定方向搜寻，知道找到跳点，或碰到障碍物，或超出地图
while(1){
nodeTmp.row += delta_y;
nodeTmp.col += delta_x;
//cout<<"直跳跃："<<nodeTmp.row<<","<<nodeTmp.col<<endl;
//如果搜寻到终点就返回
if(nodeTmp.row == endNode.row &&
nodeTmp.col == endNode.col) return nodeTmp;
//如果搜寻点，是障碍物，或者出了地图，返回空
if(height <= nodeTmp.row || 0 > nodeTmp.row||
width <= nodeTmp.col || 0 > nodeTmp.col ||
1 == _pathMap[nodeTmp.row][nodeTmp.col]->value
) return nullNode;
//获取搜寻点周围3x3单元地图，并找到邻居组
unitMap = 0;//清空单元地图
for(int i=0; i<9; i++){//初始化邻居组
neighbGroup[i] = 9;
}
for(int i = 0;i <3; i++){
for(int j= 0;j <3; j++){
int row_t = nodeTmp.row +i-1;//获取周围的点坐标
int col_t = nodeTmp.col +j-1;
if(height > row_t && 0 <= row_t &&
width > col_t && 0 <= col_t
){//确保周围点没超出地图
valueT = _pathMap[row_t][col_t]->value;
unitMap = unitMap|valueT<<(i*3 +j);
if(1 != valueT){//不为障碍
neighbGroup[i*3+j] = (i*3 +j);
}
}
}
}//end-获取搜寻点周围3x3单元地图，并找到邻居组
//获取当前搜寻点周围点类型
for(int i=0;i <9;i++){
if(9 != neighbGroup[i] &&
parent != neighbGroup[i] &&
4 != neighbGroup[i]
){//如果邻居组中点不为：空(9)、当前搜寻点(4)、父节点
nodeTyp = Prune(unitMap, parent, neighbGroup[i]);
if(1 == nodeTyp[1]){//如果存在强迫邻居，返回当前搜寻点
return nodeTmp;
}
}
}//end-获取当前搜寻点周围点类型
}//while(o)-end
}
Jps::PathNode Jps::JumpOblique(PathNode*** _pathMap,PathNode currenNode,Direct dir){
int delta_x = 0;
int delta_y = 0;
short unitMap = 0;
char valueT = 0;//存储辅助地图中点的临时值，用于算出单元地图值
bool* nodeTyp;
char parent;//单元地图中，父节点
char neighbGroup[9] = {9,9,9,9,9,9,9,9,9};//单元地图中,要探测的邻居组，初始化为非(0-8)的值，为9的点为不可行点
Direct straightDirs[2] = {p_up,p_up};
switch(dir)
{
case p_leftup:
delta_x = -1;
delta_y = -1;
parent = 8;
straightDirs[0] = p_left;
straightDirs[1] = p_up;
break;
case p_leftdown:
delta_x = -1;
delta_y = 1;
parent = 2;
straightDirs[0] = p_left;
straightDirs[1] = p_down;
break;
case p_rightup:
delta_x = 1;
delta_y = -1;
parent = 6;
straightDirs[0] = p_right;
straightDirs[1] = p_up;
break;
case p_rightdown:
delta_x = 1;
delta_y = 1;
parent = 0;
straightDirs[0] = p_right;
straightDirs[1] = p_down;
break;
default:
break;
}
PathNode nodeTmp = currenNode;//沿指定方向搜寻的点
//沿指定方向搜寻，知道找到跳点，或碰到障碍物，或超出地图
while(1){
nodeTmp.row += delta_y;
nodeTmp.col += delta_x;
//cout<<"斜跳跃："<<nodeTmp.row<<","<<nodeTmp.col<<endl;
//如果搜寻到终点就返回
if(nodeTmp.row == endNode.row &&
nodeTmp.col == endNode.col) return nodeTmp;
//如果搜寻点，是障碍物，或者出了地图，返回空
if(height <= nodeTmp.row || 0 > nodeTmp.row||
width <= nodeTmp.col || 0 > nodeTmp.col ||
1 == _pathMap[nodeTmp.row][nodeTmp.col]->value
) return nullNode;
//获取搜寻点周围3x3单元地图，并找到邻居组
unitMap = 0;//清空单元地图
for(int i=0; i<9; i++){//初始化邻居组
neighbGroup[i] = 9;
}
for(int i = 0;i <3; i++){
for(int j= 0;j <3; j++){
int row_t = nodeTmp.row +i-1;//获取周围的点坐标
int col_t = nodeTmp.col +j-1;
if(height > row_t && 0 <= row_t &&
width > col_t && 0 <= col_t
){//确保周围点没超出地图
valueT = _pathMap[row_t][col_t]->value;
unitMap = unitMap|valueT<<(i*3 +j);
if(1 != valueT){//不为障碍
neighbGroup[i*3+j] = (i*3 +j);
}
}
}
}//end-获取搜寻点周围3x3单元地图，并找到邻居组
//获取当前搜寻点周围点类型，如果存在强迫邻居，返回当前搜寻点
for(int i=0;i <9;i++){
if(9 != neighbGroup[i] &&
parent != neighbGroup[i] &&
4 != neighbGroup[i]
){//如果邻居组中点不为：空(9)、当前搜寻点(4)、父节点
nodeTyp = Prune(unitMap, parent, neighbGroup[i]);
if(1 == nodeTyp[1]){//如果存在强迫邻居，返回当前搜寻点
return nodeTmp;
}
}
}//end-获取当前搜寻点周围点类型
//往当前点的直线“真。邻居“，做直跳跃，如果不反回空，返回当前点
PathNode jumpNode;//用于保存直跳跃的返回节点
for(int i=0;i <2; i++){
jumpNode = JumpStraight(_pathMap, nodeTmp, straightDirs[i]);
if(false == jumpNode.isnull) return nodeTmp;
}
}
}
vector<Jps::PathNode> Jps::FindPath(PathNode _startNode,PathNode _endNode){
//设置开始结束点
startNode = _startNode;
endNode = _endNode;
vector<Direct> jumpDirs;//存放当前需要跳跃的方向
vector<Direct>::iterator dirsIt;//用于检索反向树的迭代器
PathNode jumpNode;//返回的跳点
bool* nodeTyp;//返回的邻居类型
PathNode currentNode;//当前节点
vector<PathNode> openTree;//开放列表，关闭列表是用辅助地图各点的isfind属性维护的
vector<PathNode>::iterator it;//用于迭代
vector<PathNode>::iterator minF_iter;//存放最小f值节点
currentNode = startNode;//当前点为开始点
pathMap[currentNode.row][currentNode.col]->isfind = true;
//初始方向树（八个方向）
for(int i=0;i <8;i++){
jumpDirs.push_back( (Direct)i);
}
//寻路
while(1){
//利用当前点，以及parent方向，往所有“真。邻居“方向跳跃
for(dirsIt = jumpDirs.begin();dirsIt != jumpDirs.end(); dirsIt++){
//cout<<"方向："<<(*dirsIt)<<" "<<endl;
if( *(dirsIt) == p_up|| *(dirsIt) == p_down|| *(dirsIt) == p_left|| *(dirsIt) == p_right){
jumpNode = JumpStraight(pathMap, currentNode, (*dirsIt) );
}
if( *(dirsIt) == p_leftup|| *(dirsIt) == p_leftdown|| *(dirsIt) == p_rightup|| *(dirsIt) == p_rightdown){
jumpNode = JumpOblique(pathMap, currentNode, (*dirsIt) );
}
//如果返回的是有效节点，且不在关闭列表中（未找过）
if(false == jumpNode.isnull && false == pathMap[jumpNode.row][jumpNode.col]->isfind){
jumpNode.g = pathMap[currentNode.row][currentNode.col]->g +GetDis( currentNode, jumpNode);
//如果该点已经在开放列表中，比较g值，取g值较小的点的属性，并不用再次加入开放列表
if(pathMap[jumpNode.row][jumpNode.col]->inopen){
if(pathMap[jumpNode.row][jumpNode.col]->g > jumpNode.g){
pathMap[jumpNode.row][jumpNode.col]->g = jumpNode.g;
pathMap[jumpNode.row][jumpNode.col]->GetF();
pathMap[jumpNode.row][jumpNode.col]->parent = pathMap[currentNode.row][currentNode.col];
}
}
//如果不在开放列表中
if(false == pathMap[jumpNode.row][jumpNode.col]->inopen){
jumpNode.h = GetH(jumpNode, endNode);
jumpNode.GetF();
jumpNode.inopen = true;
//将探测点加入开放列表
openTree.push_back(jumpNode);
//更新辅助地图中对应探测点的节点属性
pathMap[jumpNode.row][jumpNode.col]->g = jumpNode.g;
pathMap[jumpNode.row][jumpNode.col]->h = jumpNode.h;
pathMap[jumpNode.row][jumpNode.col]->f = jumpNode.f;
pathMap[jumpNode.row][jumpNode.col]->parent = pathMap[currentNode.row][currentNode.col];
pathMap[jumpNode.row][jumpNode.col]->inopen = jumpNode.inopen;
}
//system("pause");
}
}
if(openTree.size() == 0) break;
//找下一点
minF_iter = openTree.begin();
//cout<<endl<<"找下一点"<<endl;
for(it =openTree.begin();it !=openTree.end(); it++){
//cout<<(*it).row<<","<<(*it).col<<endl;
if(pathMap[(*it).row][(*it).col]->f < pathMap[(*minF_iter).row][(*minF_iter).col]->f){
minF_iter = it;
}
}
//cout<<endl<<"找到的下一点: ";
//cout<<(*minF_iter).row<<","<<(*minF_iter).col<<endl;
#if 0 //调试
cout<<endl<<"找到的下一点: ";
cout<<(*minF_iter).row<<","<<(*minF_iter).col<<endl;
cout<<"此节点父节点坐标：";
PathNode tmp = { (*minF_iter).row,(*minF_iter).col};
while(NULL != pathMap[tmp.row][tmp.col]->parent){
int t_row = tmp.row,t_col = tmp.col;
tmp.row = pathMap[t_row][t_col]->parent->row;
tmp.col = pathMap[t_row][t_col]->parent->col;
cout<<tmp.row<<","<<tmp.col<<" ";
}
cout<<endl;
#endif
currentNode = (*minF_iter);
pathMap[currentNode.row][currentNode.col]->isfind = true;
if(currentNode.row == endNode.row && currentNode.col == endNode.col) break;
openTree.erase(minF_iter);
//获取当前节点即将要搜寻的方向，jumpDirs
jumpDirs.clear();
int delta_y = currentNode.row - pathMap[currentNode.row][currentNode.col]->parent->row;
int delta_x = currentNode.col - pathMap[currentNode.row][currentNode.col]->parent->col;
char p;//单元地图中父点
short unitMap = 0;
char neighbGroup[9] = {9,9,9,9,9,9,9,9,9};//单元地图中,要探测的邻居组，初始化为非(0-8)的值，为9的点为不可行点
if(0 > delta_y && 0 ==delta_x) p = 7;//搜寻方向为上
if(0 < delta_y && 0 ==delta_x) p = 1;//搜寻方向为下
if(0 == delta_y && 0 >delta_x) p = 5;//搜寻方向为左
if(0 == delta_y && 0 <delta_x) p = 3;//搜寻方向为右
if(0 > delta_y && 0 >delta_x) p = 8;//搜寻方向为左上
if(0 < delta_y && 0 >delta_x) p = 2;//搜寻方向为左下
if(0 > delta_y && 0 <delta_x) p = 6;//搜寻方向为右上
if(0 < delta_y && 0 <delta_x) p = 0;//
//获取搜寻点周围3x3单元地图，并找到邻居组
for(int i = 0;i <3; i++){
for(int j= 0;j <3; j++){
int row_t = currentNode.row +i-1;//获取周围的点坐标
int col_t = currentNode.col +j-1;
if(height > row_t && 0 <= row_t &&
width > col_t && 0 <= col_t
){//确保周围点没超出地图
int valueT = pathMap[row_t][col_t]->value;
unitMap = unitMap|valueT<<(i*3 +j);
if(1 != valueT){//不为障碍
neighbGroup[i*3+j] = (i*3 +j);
}
}
}
}//end-获取搜寻点周围3x3单元地图，并找到邻居组
//获取当前搜寻点周围点类型，并赋值探测方向组
for(int i=0;i <9;i++){
if(9 != neighbGroup[i] &&
p != neighbGroup[i] &&
4 != neighbGroup[i]
){//如果邻居组中点不为：空(9)、当前搜寻点(4)、父节点
nodeTyp = Prune(unitMap, p, neighbGroup[i]);
if(1 == nodeTyp[0]){//如果存在关键邻居，就向探测方向组中加入当前方向
if(1==i) jumpDirs.push_back(p_up);
if(7==i) jumpDirs.push_back(p_down);
if(3==i) jumpDirs.push_back(p_left);
if(5==i) jumpDirs.push_back(p_right);
if(0==i) jumpDirs.push_back(p_leftup);
if(6==i) jumpDirs.push_back(p_leftdown);
if(2==i) jumpDirs.push_back(p_rightup);
if(8==i) jumpDirs.push_back(p_rightdown);
}
}
}//end-获取当前搜寻点周围点类型，并赋值探测方向组
//system("pause");
}
//返回路径
vector<PathNode> retPathTmp;
PathNode nodeTmp = endNode;
while(1){
int row_t = nodeTmp.row;
int col_t = nodeTmp.col;
retPathTmp.push_back(nodeTmp);
//retPath.push_back(nodeTmp);
pathMap[row_t][col_t]->isroute = true;
if(NULL == pathMap[nodeTmp.row][nodeTmp.col]->parent) break;
nodeTmp.row = pathMap[row_t][col_t]->parent->row;
nodeTmp.col = pathMap[row_t][col_t]->parent->col;
}
reverse(retPathTmp.begin(),retPathTmp.end());
vector<PathNode> part_path;
//vector<PathNode> interpolatedPoints;
// 进行逐点差值
for (size_t i = 0; i < retPathTmp.size() - 1; ++i) {
vector<PathNode> temp = interpolate(retPathTmp[i], retPathTmp[i + 1]);
retPath.insert(retPath.end(), temp.begin(), temp.end());
}
vector<PathNode>().swap(retPathTmp);//释放内存
vector<PathNode>().swap(part_path);//释放内存
return retPath;
}
// 计算两个点之间的差值
vector<Jps::PathNode> Jps::interpolate(PathNode start, PathNode end) {
vector<PathNode> result;
int dx = end.row - start.row; // 修正为使用 start.row
int dy = end.col - start.col; // 修正为使用 start.col
int steps = max(abs(dx), abs(dy)); // 差值步骤数量
for (int i = steps; i > 0; i--) {
int newX = start.row + dx * (steps - i) / steps;
int newY = start.col + dy * (steps - i) / steps;
// 这里也要确保 newX 和 newY 在有效范围内
if (newX >= 0 && newY >= 0) {
pathMap[newX][newY]->isroute = true;
result.push_back({ newX, newY });
}
}
return result;
}
void Jps::PrintRoute(){
vector<PathNode>::iterator it;//用于迭代
float routLength = 0;//路径总长度
cout<<endl<<"route"<<"("<<retPath.size()<<"): ";
for(it =retPath.begin();it != retPath.end(); it++){
cout<<(*it).row<<","<<(*it).col<<" ";
//计算路径长度
if(it > retPath.begin()){
int row_t = (*it).row,col_t = (*it).col;//本次坐标
int row_t_l = (*(it -1) ).row,col_t_l = (*(it -1) ).col;//上次坐标
routLength += sqrt( pow( col_t - col_t_l,2) +pow( (row_t - row_t_l),2) );//pow次方函数
}
}
cout<<endl;
cout<<"routLength："<<routLength;
}
void Jps::PrintRouteMap() {
//打印路线地图
cout << endl;
for (int i = 0; i < height; i++) {
for (int j = 0; j < width; j++) {
if (pathMap[i][j]->isroute)
cout << "*";
else cout << pathMap[i][j]->value;
}
cout << endl;
}
}
2.2 jps.h
#include <iostream>
//#include<windows.h>
#include<vector>
#include<cmath>
#ifdef byte
#undef byte
#endif
#include <cstddef> // for std::byte
using namespace std;
using std::vector;
class Jps
{
public:
//方向枚举
enum Direct{
p_up,p_down,p_left,p_right,p_leftup,p_leftdown,p_rightup,p_rightdown
};
//辅助地图节点
struct PathNode{
int row;//行
int col;
int g,h,f;
void GetF(){
f = g + h;
}
int value;//
bool isroute;//是否是最短路径中的一点
bool isfind;//是否走过
bool inopen;
bool isnull;//是否是空节点
PathNode* parent;//父节点
vector<PathNode*> keyNeighbours; //关键邻居节点
};
int height,width;
PathNode*** pathMap;//辅助地图
PathNode startNode;
PathNode endNode;
PathNode nullNode;//空节点
vector<PathNode> retPath;//储存最终路径
//计算两点直线距离
int GetDis(const PathNode& startNode,const PathNode& endNode){
int dis = sqrt( pow( (endNode.col -startNode.col),2) +pow( (endNode.row -startNode.row),2) )*10;//pow次方函数
return dis;
}
//计算h值
int GetH(const PathNode& startNode,const PathNode& endNode){
int x = abs(startNode.col - endNode.col);//取水平距离差绝对值
int y = abs(startNode.row - endNode.row);//取竖直距离差绝对值
return (x + y)*10;
}
bool* Prune(short unitMap,char p,char n);
void Init(int **_map,int _height,int _width);
PathNode JumpStraight(PathNode*** _pathMap,PathNode currenNode,Direct dir);
PathNode JumpOblique(PathNode*** _pathMap,PathNode currenNode,Direct dir);
vector<PathNode> FindPath(PathNode _startNode,PathNode _endNode);
void PrintRoute();
void PrintRouteMap();
vector<PathNode> interpolate(PathNode start, PathNode end);
};
3. 调用方法
在main.c文件中，展示了如何调用 JPS 算法进行路径规划。首先读取地图文件，创建 A算法对象和 JPS 算法对象，分别使用 A算法和 JPS 算法进行路径规划，并计算和打印两种算法的寻路时间。
3.1 main.cpp
#include <iostream> //"#"代表预处理命令
#include<cstring>
#include<fstream>//读写头文件
#include<time.h>
#include<windows.h>
#include"astar.h"
#include"jps.h"
using namespace std; //使用standard命名空间
int main(){
system("mode con cols=120 lines=600");
//行row，列col
int height = 100;
int width = 100;
int start_x =1,start_y =1;
int end_x =5,end_y =95;
cout<<"地图尺寸（height*width）: "<<height<<"*"<<width;
cout<<endl<<"开始点（y，x）："<<start_y<<","<<start_x<<endl;
cout<<"结束点（y，x）："<<end_y<<","<<end_x<<endl;
time_t time_start_ms,time_end_ms;//时间记录ms
//读取地图
string filepath="map/map100x100_small.txt";
ifstream fin(filepath.c_str());
if(!fin) {cout<<endl<<"文件不存在"<<endl; system("pause");}
int **pMap;//地图二维指针数组
pMap = new int* [height];
for(int i=0;i < height;i++){
pMap[i] = new int[width];
for(int j=0;j < width;j++){
char c;
fin>>c;
if('.' == c) pMap[i][j] = 0;
else pMap[i][j] = 1;
//cout<<pMap[i][j];
}
//cout<<endl;
}
Astar::MyPoint startPoint = {start_y,start_x};
Astar::MyPoint endPoint = {end_y, end_x};
Astar astar;
time_start_ms = clock();//a星寻路开始时间
astar.Init(pMap, height, width, startPoint, endPoint);
astar.FindPath();
time_end_ms = clock();//a星寻路结束时间
cout<<"a星寻路使用时间："<<difftime(time_end_ms, time_start_ms)<<"ms";
astar.PrintRoute();
astar.PrintRouteMap();
system("pause");
//JPS
cout<<"------------JPS---------------"<<"\n";
Jps jps;
Jps::PathNode jStart = {start_y,start_x};
Jps::PathNode jEnd = {end_y, end_x};
time_start_ms = clock();//JpsPrune寻路开始时间
jps.Init(pMap, height, width);
jps.FindPath(jStart, jEnd);
time_end_ms = clock();//JpsPrune寻路结束时间
cout<<"Jps寻路使用时间："<<difftime(time_end_ms, time_start_ms)<<"ms";
jps.PrintRoute();
jps.PrintRouteMap();
system("pause");
return 0;
}
3.2 输出结果
地图尺寸（height*width）: 100*100
开始点（y，x）：1,1
结束点（y，x）：95,5
a星寻路使用时间：1123ms
route(489): 95,5 95,6 94,7 93,8 92,9 92,10 92,11 93,12 94,13 95,14 95,15 96,16 97,17 98,18 99,19 99,20 99,21 98,22 97,23 96,24 95,25 95,26 95,27 95,28 94,29 94,30 94,31 94,32 94,33 94,34 94,35 94,36 94,37 94,38 94,39 94,40 94,41 94,42 94,43 94,44 94,45 94,46 94,47 94,48 93,49 93,50 93,51 93,52 93,53 93,54 93,55 93,56 93,57 93,58 92,59 92,60 92,61 93,62 94,63 95,64 95,65 95,66 95,67 95,68 96,69 96,70 96,71 95,72 95,73 95,74 95,75 95,76 95,77 94,78 93,79 93,80 93,81 94,82 94,83 94,84 94,85 94,86 94,87 94,88 94,89 94,90 94,91 94,92 94,93 93,94 92,95 91,96 90,96 89,96 89,95 88,94 87,93 86,92 85,91 85,90 85,89 86,88 86,87 86,86 86,85 86,84 86,83 86,82 86,81 86,80 86,79 87,78 88,77 89,76 89,75 89,74 89,73 89,72 89,71 89,70 89,69 89,68 89,67 89,66 89,65 88,64 87,63 86,62 85,61 85,60 85,59 86,58 87,57 88,56 88,55 88,54 88,53 88,52 88,51 88,50 88,49 88,48 88,47 88,46 88,45 87,44 86,43 85,42 84,41 84,40 84,39 85,38 86,37 87,36 88,35 89,34 89,33 89,32 89,31 89,30 89,29 89,28 89,27 89,26 89,25 88,24 87,23 86,22 85,21 85,20 85,19 85,18 85,17 84,16 83,15 82,14 81,13 80,13 79,13 79,14 79,15 79,16 78,17 77,18 76,19 76,20 76,21 76,22 76,23 76,24 76,25 75,26 74,27 73,28 72,29 72,30 72,31 73,32 74,33 75,34 75,35 75,36 75,37 75,38 75,39 75,40 75,41 75,42 75,43 75,44 75,45 75,46 75,47 74,48 73,49 73,50 73,51 73,52 73,53 73,54 73,55 73,56 73,57 73,58 72,59 72,60 72,61 72,62 71,63 70,63 69,63 69,64 69,65 69,66 69,67 68,68 67,69 67,70 67,71 67,72 66,73 65,74 64,75 63,76 62,77 61,78 60,78 59,78 58,78 57,79 57,80 57,81 56,81 55,81 54,82 53,83 52,84 51,85 50,85 49,85 48,85 47,86 46,87 45,88 44,89 44,90 44,91 44,92 44,93 43,94 42,95 41,96 40,96 39,96 39,95 38,94 37,93 36,92 35,91 35,90 35,89 36,88 36,87 36,86 36,85 36,84 36,83 36,82 36,81 36,80 36,79 37,78 38,77 39,76 39,75 39,74 39,73 39,72 39,71 39,70 39,69 39,68 39,67 39,66 39,65 38,64 37,63 36,62 35,61 35,60 35,59 36,58 37,57 38,56 38,55 38,54 38,53 38,52 38,51 38,50 38,49 38,48 38,47 38,46 38,45 37,44 36,43 35,42 34,41 34,40 34,39 35,38 36,37 37,36 38,35 39,34 39,33 39,32 39,31 39,30 39,29 39,28 39,27 39,26 39,25 38,24 37,23 36,22 35,21 35,20 35,19 35,18 35,17 34,16 33,15 32,14 31,13 30,13 29,13 29,14 29,15 29,16 28,17 27,18 26,19 26,20 26,21 26,22 26,23 26,24 26,25 25,26 24,27 23,28 22,29 22,30 22,31 23,32 24,33 25,34 25,35 25,36 25,37 25,38 25,39 25,40 25,41 25,42 25,43 25,44 25,45 25,46 25,47 24,48 23,49 23,50 23,51 23,52 23,53 23,54 23,55 23,56 23,57 23,58 22,59 22,60 22,61 22,62 21,63 20,63 19,63 18,63 17,63 16,64 15,65 14,66 13,67 12,68 11,69 10,69 9,69 9,68 8,67 7,66 6,65 5,64 4,63 3,62 2,61 2,60 2,59 3,58 4,57 5,56 5,55 5,54 5,53 5,52 5,51 5,50 5,49 6,48 7,47 7,46 7,45 7,44 7,43 7,42 7,41 7,40 7,39 7,38 7,37 7,36 7,35 7,34 6,33 5,32 4,31 4,30 4,29 5,28 6,27 7,26 8,25 8,24 8,23 8,22 8,21 8,20 8,19 8,18 8,17 8,16 8,15 8,14 8,13 8,12 7,11 7,10 7,9 7,8 7,7 6,6 5,5 4,4 3,3 2,2 1,1
routLength：559.245
1111111110111111101111111111011111111111111111111111111111111111110111111111111011111011111111111111
1*00000000100000000010000000001000000000100000000010000000001000000000000000000010000000001000000000
10*00000001000000000100000000010000000001000000000100000000***00000000100000000010000000001000000000
100*000000100000000010000000001000000000100000000010000000*010*0000000100000000010000000001000000000
0000*000001000000000100000000***0000000010000000001000000*00100*000000100000000010000000001000000000
10000*0000100000000010000000*010*0000000100000000********0001000*00000100000000010000000001000000000
100000*00010000000001000000*00100*00000010000000*0100000000010000*0000100000000010000000001000000000
1000000*****00000000100000*0001000**************001000000000100000*000100000000000000000001000000000
100000000010**************00001000000000100000000010000000001000000*00100000000010000000001000000000
10000000001000000000100000000010000000001000000000100000000010000000**100000000010000000000000000000
111111111111111111111111111111111111111111111111111111111111111111111*111111110111111011111111110111
100000000010000000001000000000100000000010000000001000000000100000000*100000000010000000001000000000
10000000000000000000100000000000000000000000000000100000000000000000*0100000000010000000001000000000
1000000000100000000010000000001000000000100000000010000000001000000*00100000000010000000001000000000
100000000010000000001000000000100000000010000000001000000000100000*000100000000010000000001000000000
10000000001000000000100000000010000000001000000000100000000010000*0000100000000010000000001000000000
1000000000100000000010000000001000000000100000000010000000001000*00000100000000010000000001000000000
100000000010000000000000000000100000000010000000001000000000100*000000000000000010000000000000000000
100000000010000000001000000000100000000010000000001000000000100*000000100000000010000000001000000000
000000000010000000001000000000100000000010000000000000000000100*000000100000000000000000001000000000
111111111111111011111111111111111110111111111111011111111111111*111111111111111111111111111111111011
100000000010000000001000000000100000000010000000001000000000100*000000000000000010000000001000000000
10000000001000000000100000000***000000001000000000100000000****0000000100000000010000000001000000000
1000000000100000000010000000*010*0000000100000000**********01000000000100000000010000000001000000000
000000000010000000001000000*00100*00000010000000*010000000001000000000100000000010000000000000000000
10000000001000000000100000*0001000**************0010000000001000000000100000000010000000001000000000
1000000000100000000*******00001000000000100000000010000000001000000000100000000010000000001000000000
100000000010000000*010000000001000000000100000000010000000001000000000100000000010000000001000000000
10000000000000000*0010000000001000000000100000000010000000001000000000100000000000000000001000000000
1000000000100****00010000000001000000000100000000010000000001000000000100000000010000000001000000000
1111111111111*11111111111111111111111111111111111111111111111111111111111111111111111111111111111111
1000000000100*00000010000000001000000000100000000010000000001000000000100000000010000000001000000000
10000000001000*0000010000000001000000000100000000010000000001000000000100000000010000000001000000000
100000000010000*000010000000001000000000100000000010000000001000000000100000000010000000001000000000
1000000000100000*0001000000000100000000***0000000010000000001000000000100000000010000000001000000000
10000000001000000*****0000000010000000*010*0000000100000000***000000001000000000100000000***00000000
0000000000100000000010*00000001000000*00100*00000010000000*010*0000000100000000**********010*0000000
10000000000000000000100*000000100000*0001000*000001000000*00100*00000010000000*01000000000100*000000
100000000010000000001000*0000010000*000010000************0001000*000001000000*0010000000001000*00000
1000000000100000000010000**********000001000000000100000000010000************000100000000010000**000
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111*111
100000000010000000001000000000100000000010000000001000000000100000000010000000001000000000100000*000
10000000000000000000100000000010000000001000000000100000000000000000001000000000100000000010000*0000
1000000000100000000010000000001000000000100000000000000000001000000000100000000000000000001000*00000
10000000001000000000100000000000000000000000000000100000000010000000001000000000100000000*****000000
1000000000100000000010000000001000000000100000000010000000001000000000100000000010000000*01000000000
100000000010000000001000000000100000000010000000001000000000100000000000000000001000000*001000000000
10000000001000000000100000000010000000001000000000100000000010000000001000000000100000*0001000000000
1000000000100000000010000000001000000000100000000010000000001000000000100000000010000*00001000000000
0000000000100000000000000000001000000000100000000010000000001000000000100000000010000*00001000000000
1111111110111111101111111111011111111111111111111111111111111111110111111111111011111*11111111111111
1000000000100000000010000000001000000000100000000010000000001000000000000000000010000*00001000000000
100000000010000000001000000000100000000010000000001000000000000000000010000000001000*000001000000000
10000000001000000000100000000010000000001000000000100000000010000000001000000000100*0000001000000000
0000000000100000000010000000000000000000100000000010000000001000000000100000000010*00000001000000000
100000000010000000001000000000100000000010000000000000000000100000000010000000001*000000001000000000
100000000010000000001000000000100000000010000000001000000000100000000010000000001*000000001000000000
1000000000000000000010000000001000000000000000000010000000001000000000100000000***000000001000000000
100000000010000000000000000000100000000010000000001000000000100000000010000000*010000000001000000000
100000000010000000001000000000100000000010000000001000000000100000000010000000*010000000000000000000
111111111111111111111111111111111111111111111111111111111111111111111011111111*111111011111111110111
100000000010000000001000000000100000000010000000001000000000100000000010000000*010000000001000000000
10000000000000000000100000000000000000000000000000100000000000000000001000000*0010000000001000000000
1000000000100000000010000000001000000000100000000010000000001000000000100000*00010000000001000000000
100000000010000000001000000000100000000010000000001000000000100000000010000*000010000000001000000000
10000000001000000000100000000010000000001000000000100000000010000000001000*0000010000000001000000000
1000000000100000000010000000001000000000100000000010000000001000000000100*00000010000000001000000000
100000000010000000000000000000100000000010000000001000000000100000000****000000010000000000000000000
10000000001000000000100000000010000000001000000000100000000010000000*0100000000010000000001000000000
000000000010000000001000000000100000000010000000000000000000100*****00100000000000000000001000000000
111111111111111011111111111111111110111111111111011111111111111*111111111111111111111111111111111011
100000000010000000001000000000100000000010000000001000000000100*000000000000000010000000001000000000
10000000001000000000100000000***000000001000000000100000000****0000000100000000010000000001000000000
1000000000100000000010000000*010*0000000100000000**********01000000000100000000010000000001000000000
000000000010000000001000000*00100*00000010000000*010000000001000000000100000000010000000000000000000
10000000001000000000100000*0001000**************0010000000001000000000100000000010000000001000000000
1000000000100000000*******00001000000000100000000010000000001000000000100000000010000000001000000000
100000000010000000*010000000001000000000100000000010000000001000000000100000000010000000001000000000
10000000000000000*0010000000001000000000100000000010000000001000000000100000000000000000001000000000
1000000000100****00010000000001000000000100000000010000000001000000000100000000010000000001000000000
1111111111111*11111111111111111111111111111111111111111111111111111111111111111111111111111111111111
1000000000100*00000010000000001000000000100000000010000000001000000000100000000010000000001000000000
10000000001000*0000010000000001000000000100000000010000000001000000000100000000010000000001000000000
100000000010000*000010000000001000000000100000000010000000001000000000100000000010000000001000000000
1000000000100000*0001000000000100000000***0000000010000000001000000000100000000010000000001000000000
10000000001000000*****0000000010000000*010*0000000100000000***000000001000000000100000000***00000000
0000000000100000000010*00000001000000*00100*00000010000000*010*0000000100000000**********010*0000000
10000000000000000000100*000000100000*0001000*000001000000*00100*00000010000000*01000000000100*000000
100000000010000000001000*0000010000*000010000************0001000*000001000000*0010000000001000*00000
1000000000100000000010000**********000001000000000100000000010000************000100000000010000**000
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111*111
100000000010000000001000000000100000000010000000001000000000100000000010000000001000000000100000*000
100000000***00000000100000000010000000001000000000100000000***000000001000000000100000000010000*0000
10000000*010*000000010000000001000000000100000000**********010*0000000100000000***000000001000*00000
1000000*00100*000000100000000********************01000000000100*00000010000000*010************000000
10000**0001000**000010000****01000000000100000000010000000001000*****010******0010000000001000000000
1000000000100000*0001000*00000100000000010000000001000000000100000000***0000000010000000001000000000
10000000001000000*00100*0000001000000000100000000010000000001000000000100000000010000000001000000000
100000000010000000*010*00000001000000000100000000010000000001000000000100000000010000000001000000000
0000000000100000000***000000001000000000100000000010000000001000000000100000000010000000001000000000
请按任意键继续. . .
------------JPS---------------
Jps寻路使用时间：26ms
route(472): 1,1 2,2 3,3 4,4 5,5 6,6 7,7 7,8 7,9 7,10 8,11 8,12 8,13 8,14 8,15 8,16 8,17 8,18 8,19 8,20 7,21 6,22 5,23 4,
,24 4,25 4,26 4,27 4,28 4,29 4,30 5,31 6,32 7,33 7,34 7,35 7,36 7,37 7,38 7,39 7,40 6,41 5,42 5,43 5,44 5,45 5,46 5,47 5,
,48 5,49 5,50 4,51 3,52 2,53 2,54 2,55 2,56 2,57 2,58 2,59 2,60 3,61 4,62 5,63 6,64 7,65 8,66 9,67 9,68 10,69 11,68 12,67
7 13,66 14,65 15,64 16,63 17,63 18,63 19,63 20,63 21,62 22,61 22,60 23,59 23,58 23,57 23,56 23,55 23,54 23,53 23,52 23,51
1 23,50 24,49 25,48 25,47 25,46 25,45 25,44 25,43 25,42 25,41 25,40 24,39 23,38 22,37 22,36 22,35 22,34 22,33 22,32 22,31
1 22,30 23,29 24,28 25,27 26,26 26,25 26,24 26,23 26,22 26,21 26,20 27,19 28,18 29,17 29,16 29,15 29,14 30,13 31,14 32,15
5 33,16 34,17 35,18 35,19 35,20 36,21 37,22 38,23 39,24 39,25 39,26 39,27 39,28 39,29 39,30 38,31 37,32 36,33 35,34 34,35
5 34,36 34,37 34,38 34,39 34,40 35,41 36,42 37,43 38,44 38,45 38,46 38,47 38,48 38,49 38,50 37,51 36,52 35,53 35,54 35,55
5 35,56 35,57 35,58 35,59 35,60 36,61 37,62 38,63 39,64 39,65 39,66 39,67 39,68 39,69 39,70 38,71 37,72 36,73 36,74 36,75
5 36,76 36,77 36,78 36,79 36,80 35,81 35,82 35,83 35,84 35,85 35,86 35,87 35,88 35,89 35,90 36,91 37,92 38,93 39,94 39,95
5 40,96 41,95 42,94 43,93 44,92 44,91 44,90 45,89 46,88 47,87 48,86 49,85 50,85 51,84 52,83 53,82 54,81 55,81 56,81 57,80
0 58,79 59,78 60,78 61,77 62,76 63,75 64,74 65,73 66,72 67,71 67,70 68,69 69,68 69,67 69,66 69,65 69,64 70,63 71,62 72,61
1 72,60 73,59 73,58 73,57 73,56 73,55 73,54 73,53 73,52 73,51 73,50 74,49 75,48 75,47 75,46 75,45 75,44 75,43 75,42 75,41
1 75,40 74,39 73,38 72,37 72,36 72,35 72,34 72,33 72,32 72,31 72,30 73,29 74,28 75,27 76,26 76,25 76,24 76,23 76,22 76,21
1 76,20 77,19 78,18 79,17 79,16 79,15 79,14 80,13 81,14 82,15 83,16 84,17 85,18 85,19 85,20 86,21 87,22 88,23 89,24 89,25
5 89,26 89,27 89,28 89,29 89,30 88,31 87,32 86,33 85,34 84,35 84,36 84,37 84,38 84,39 84,40 85,41 86,42 87,43 88,44 88,45
5 88,46 88,47 88,48 88,49 88,50 87,51 86,52 85,53 85,54 85,55 85,56 85,57 85,58 85,59 85,60 86,61 87,62 88,63 89,64 89,65
5 89,66 89,67 89,68 89,69 89,70 88,71 87,72 86,73 86,74 86,75 86,76 86,77 86,78 86,79 86,80 85,81 85,82 85,83 85,84 85,85
5 85,86 85,87 85,88 85,89 85,90 86,91 87,92 88,93 89,94 89,95 90,96 91,95 92,94 93,93 94,92 94,91 94,90 93,89 93,88 93,87
7 93,86 93,85 93,84 93,83 93,82 93,81 93,80 94,79 95,78 96,77 96,76 96,75 96,74 96,73 96,72 96,71 96,70 95,69 94,68 93,67
7 92,66 92,65 92,64 92,63 92,62 92,61 92,60 93,59 93,58 93,57 93,56 93,55 93,54 93,53 93,52 93,51 93,50 94,49 94,48 94,47
7 94,46 94,45 94,44 94,43 94,42 94,41 94,40 94,39 94,38 94,37 94,36 94,35 94,34 94,33 94,32 94,31 94,30 95,29 96,28 97,27
7 98,26 99,25 99,24 99,23 99,22 99,21 99,20 98,19 97,18 96,17 95,16 94,15 93,14 92,13 92,12 92,11 92,10 93,9 94,8 95,7 95
5,6
routLength：548.872
1111111110111111101111111111011111111111111111111111111111111111110111111111111011111011111111111111
1*00000000100000000010000000001000000000100000000010000000001000000000000000000010000000001000000000
10*00000001000000000100000000010000000001000000000100********000000000100000000010000000001000000000
100*000000100000000010000000001000000000100000000010*00000001*00000000100000000010000000001000000000
0000*0000010000000001000*******00000000010000000001*0000000010*0000000100000000010000000001000000000
10000*00001000000000100*0000001*0000000010*********000000000100*000000100000000010000000001000000000
100000*000100000000010*000000010*00000001*0000000010000000001000*00000100000000010000000001000000000
1000000****0000000001*00000000100********000000000100000000010000*0000100000000000000000001000000000
10000000001**********000000000100000000010000000001000000000100000*000100000000010000000001000000000
1000000000100000000010000000001000000000100000000010000000001000000**0100000000010000000000000000000
111111111111111111111111111111111111111111111111111111111111111111111*111111110111111011111111110111
10000000001000000000100000000010000000001000000000100000000010000000*0100000000010000000001000000000
1000000000000000000010000000000000000000000000000010000000000000000*00100000000010000000001000000000
100000000010000000001000000000100000000010000000001000000000100000*000100000000010000000001000000000
10000000001000000000100000000010000000001000000000100000000010000*0000100000000010000000001000000000
1000000000100000000010000000001000000000100000000010000000001000*00000100000000010000000001000000000
100000000010000000001000000000100000000010000000001000000000100*000000100000000010000000001000000000
100000000010000000000000000000100000000010000000001000000000100*000000000000000010000000000000000000
100000000010000000001000000000100000000010000000001000000000100*000000100000000010000000001000000000
000000000010000000001000000000100000000010000000000000000000100*000000100000000000000000001000000000
111111111111111011111111111111111110111111111111011111111111111*111111111111111111111111111111111011
10000000001000000000100000000010000000001000000000100000000010*0000000000000000010000000001000000000
100000000010000000001000000000********0010000000001000000000**00000000100000000010000000001000000000
10000000001000000000100000000*10000000*01000000000**********1000000000100000000010000000001000000000
0000000000100000000010000000*0100000000*100000000*10000000001000000000100000000010000000000000000000
100000000010000000001000000*001000000000*********010000000001000000000100000000010000000001000000000
10000000001000000000*******0001000000000100000000010000000001000000000100000000010000000001000000000
1000000000100000000*10000000001000000000100000000010000000001000000000100000000010000000001000000000
100000000000000000*010000000001000000000100000000010000000001000000000100000000000000000001000000000
10000000001000****0010000000001000000000100000000010000000001000000000100000000010000000001000000000
1111111111111*11111111111111111111111111111111111111111111111111111111111111111111111111111111111111
10000000001000*0000010000000001000000000100000000010000000001000000000100000000010000000001000000000
100000000010000*000010000000001000000000100000000010000000001000000000100000000010000000001000000000
1000000000100000*00010000000001000000000100000000010000000001000000000100000000010000000001000000000
10000000001000000*00100000000010000******00000000010000000001000000000100000000010000000001000000000
100000000010000000***0000000001000*000001*00000000100********00000000010000000001**********000000000
000000000010000000001*00000000100*00000010*000000010*00000001*00000000100********0000000001*00000000
1000000000000000000010*000000010*0000000100*0000001*0000000010*000000010*0000000100000000010*0000000
10000000001000000000100*0000001*000000001000*******000000000100*0000001*000000001000000000100*000000
100000000010000000001000*******000000000100000000010000000001000*******00000000010000000001000**0000
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111*111
10000000001000000000100000000010000000001000000000100000000010000000001000000000100000000010000*0000
1000000000000000000010000000001000000000100000000010000000000000000000100000000010000000001000*00000
100000000010000000001000000000100000000010000000000000000000100000000010000000000000000000100*000000
100000000010000000001000000000000000000000000000001000000000100000000010000000001000000000***0000000
10000000001000000000100000000010000000001000000000100000000010000000001000000000100000000*1000000000
1000000000100000000010000000001000000000100000000010000000001000000000000000000010000000*01000000000
100000000010000000001000000000100000000010000000001000000000100000000010000000001000000*001000000000
10000000001000000000100000000010000000001000000000100000000010000000001000000000100000*0001000000000
0000000000100000000000000000001000000000100000000010000000001000000000100000000010000*00001000000000
1111111110111111101111111111011111111111111111111111111111111111110111111111111011111*11111111111111
100000000010000000001000000000100000000010000000001000000000100000000000000000001000*000001000000000
10000000001000000000100000000010000000001000000000100000000000000000001000000000100*0000001000000000
1000000000100000000010000000001000000000100000000010000000001000000000100000000010*00000001000000000
000000000010000000001000000000000000000010000000001000000000100000000010000000001*000000001000000000
100000000010000000001000000000100000000010000000000000000000100000000010000000001*000000001000000000
100000000010000000001000000000100000000010000000001000000000100000000010000000001*000000001000000000
10000000000000000000100000000010000000000000000000100000000010000000001000000000*0000000001000000000
1000000000100000000000000000001000000000100000000010000000001000000000100000000*10000000001000000000
100000000010000000001000000000100000000010000000001000000000100000000010000000*010000000000000000000
111111111111111111111111111111111111111111111111111111111111111111111011111111*111111011111111110111
10000000001000000000100000000010000000001000000000100000000010000000001000000*0010000000001000000000
1000000000000000000010000000000000000000000000000010000000000000000000100000*00010000000001000000000
100000000010000000001000000000100000000010000000001000000000100000000010000*000010000000001000000000
10000000001000000000100000000010000000001000000000100000000010000000001000*0000010000000001000000000
1000000000100000000010000000001000000000100000000010000000001000000000100*00000010000000001000000000
100000000010000000001000000000100000000010000000001000000000100000000010*000000010000000001000000000
1000000000100000000000000000001000000000100000000010000000001000000000**0000000010000000000000000000
100000000010000000001000000000100000000010000000001000000000100000000*100000000010000000001000000000
0000000000100000000010000000001000000000100000000000000000001000*****0100000000000000000001000000000
111111111111111011111111111111111110111111111111011111111111111*111111111111111111111111111111111011
10000000001000000000100000000010000000001000000000100000000010*0000000000000000010000000001000000000
100000000010000000001000000000********0010000000001000000000**00000000100000000010000000001000000000
10000000001000000000100000000*10000000*01000000000**********1000000000100000000010000000001000000000
0000000000100000000010000000*0100000000*100000000*10000000001000000000100000000010000000000000000000
100000000010000000001000000*001000000000*********010000000001000000000100000000010000000001000000000
10000000001000000000*******0001000000000100000000010000000001000000000100000000010000000001000000000
1000000000100000000*10000000001000000000100000000010000000001000000000100000000010000000001000000000
100000000000000000*010000000001000000000100000000010000000001000000000100000000000000000001000000000
10000000001000****0010000000001000000000100000000010000000001000000000100000000010000000001000000000
1111111111111*11111111111111111111111111111111111111111111111111111111111111111111111111111111111111
10000000001000*0000010000000001000000000100000000010000000001000000000100000000010000000001000000000
100000000010000*000010000000001000000000100000000010000000001000000000100000000010000000001000000000
1000000000100000*00010000000001000000000100000000010000000001000000000100000000010000000001000000000
10000000001000000*00100000000010000******00000000010000000001000000000100000000010000000001000000000
100000000010000000***0000000001000*000001*00000000100********00000000010000000001**********000000000
000000000010000000001*00000000100*00000010*000000010*00000001*00000000100********0000000001*00000000
1000000000000000000010*000000010*0000000100*0000001*0000000010*000000010*0000000100000000010*0000000
10000000001000000000100*0000001*000000001000*******000000000100*0000001*000000001000000000100*000000
100000000010000000001000*******000000000100000000010000000001000*******00000000010000000001000**0000
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111*111
10000000001000000000100000000010000000001000000000100000000010000000001000000000100000000010000*0000
1000000000****0000001000000000100000000010000000001000000000*******000100000000010000000001000*00000
100000000*1000*00000100000000010000000001000000000**********1000000*001000000000**********100*000000
10000000*010000*00001000000000********************100000000010000000*0100000000*1000000000***0000000
10000***00100000*000100000000*100000000010000000001000000000100000000*10000000*010000000001000000000
10000000001000000*0010000000*01000000000100000000010000000001000000000********0010000000001000000000
100000000010000000*01000000*001000000000100000000010000000001000000000100000000010000000001000000000
1000000000100000000*100000*0001000000000100000000010000000001000000000100000000010000000001000000000
00000000001000000000******00001000000000100000000010000000001000000000100000000010000000001000000000
请按任意键继续. . .
三、JPS 与 A*算法的差异对比
1. 搜索方式
- A*算法：通过对每个节点进行评估，选择具有最小
f值（f = g + h，其中g是从起点到当前节点的实际代价，h是从当前节点到终点的估计代价）的节点进行扩展。它会依次检查相邻节点，并将其加入开放列表或更新其代价。 - JPS 算法：通过对搜索空间进行预处理和跳跃点的识别，减少搜索节点的数量。JPS 算法在搜索过程中，只考虑跳跃点，即那些能够直接跳跃到的关键节点，而不是像 A*算法那样依次检查每个相邻节点。这样可以大大减少搜索空间，提高搜索效率。
2. 节点扩展方式
- A*算法：在扩展节点时，会检查当前节点的所有相邻节点，并计算它们的代价。如果相邻节点不在开放列表中，则将其加入开放列表；如果在开放列表中，则更新其代价。
- JPS 算法：在扩展节点时，首先根据当前节点的方向和父节点的位置，确定需要搜索的方向。然后，对于每个搜索方向，进行直跳跃或斜跳跃，直到找到跳点或碰到障碍物或超出地图。如果找到跳点，则将其加入开放列表，并更新其代价。如果跳点已经在开放列表中，则比较其代价，取代价较小的节点的属性，并不用再次加入开放列表。
3. 效率
- A*算法：在一般情况下，A算法能够找到从起点到终点的最短路径，但它的搜索效率可能会受到地图大小和障碍物分布的影响。在复杂的地图中，A算法可能需要搜索大量的节点，导致搜索时间较长。
- JPS 算法：JPS 算法通过对搜索空间进行预处理和跳跃点的识别，能够大大减少搜索节点的数量，从而提高搜索效率。在复杂的地图中，JPS 算法通常比 A*算法更快地找到最短路径。
4. 适用性
- A*算法：适用于各种类型的地图，尤其是在地图规模较小或障碍物分布较为均匀的情况下，A*算法的性能表现较好。
- JPS 算法：JPS 算法在大规模地图或障碍物分布较为复杂的情况下表现出更好的性能。然而，JPS 算法的实现相对复杂，需要更多的计算资源和内存空间。
四、示例运行
通过读取地图文件，创建地图数组，定义起始点和终点，分别使用 A*算法和 JPS 算法进行路径规划，并计算和打印两种算法的寻路时间。可以直观地看到两种算法在不同场景下的性能表现。
五、实际应用建议
在实际应用中，可以根据具体的地图规模和障碍物分布情况选择合适的路径规划算法。如果地图规模较小且障碍物分布较为均匀，A*算法可能是一个不错的选择；如果地图规模较大或障碍物分布较为复杂，JPS 算法可能会提供更好的性能。
六、总结
现在，通过本教程，您学习了 JPS 路径规划算法的 C++实现以及它与 A*算法的差异。理解和掌握这些算法对于开发路径规划相关的应用至关重要，希望本文能帮助您更好地运用这些算法，从而实现更高效的路径规划，为各种应用场景提供更好的解决方案。后期会持续分享路径规划的相关实用案例🥳🥳🥳，科学地合理地进行开发和应用，为推动相关领域的发展贡献一点微薄之力。🤣🤣🤣
如果您有任何问题，可以通过 q group (945348278) 加入鹏鹏小分队，期待与您思维的碰撞😘😘😘
参考博客：【A*路径规划算法 C++实现教程】
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
22
0- 0
已为社区贡献20条内容
所有评论(0)