自动寻路之A星算法+Qt开发图形界面

项目演示

最近笔者学习了一个新的知识&＃xff0c;因为是车辆行业的研究生&＃xff0c;对无人车、嵌入式物联网、机器人很感兴趣&＃xff0c;所以在科研之余学习了一下A星算法&＃xff0c;用时三个星期的周末&＃xff0c;写了一个基于A星算法的游戏图形界面demo&＃xff0c;其效果如图:

A星算法理论

无人车的路径规划问题涉及到A星算法、卡尔曼滤波算法、SLAM建图仿真等技术&＃xff0c;其中A星算法应用到不仅是车辆的路径规划上&＃xff0c;其在游戏行业有着很广泛的应用&＃xff0c;比如lol中&＃xff0c;我们想要控制自己的人物到地图上的某一点去&＃xff0c;那么我们只需点击目的地&＃xff0c;则人物会自动的按照算法算出来的最优路径进行自动导航到达我们指定的位置。在本项目中&＃xff0c;没有向游戏中的地图那么复杂&＃xff0c;笔者建立了简单的网格地图&＃xff0c;来简单模拟游戏中的路径规划。

如上图中起点终点所示&＃xff0c;黑色为障碍物&＃xff0c;最优路径则为黄色区域。其算法核心即为启发式搜索&＃xff0c;通过公式F&＃61;G&＃43;H得出&＃xff1a;其中F叫做路径代价&＃xff0c;G则为起点到当前点已经付出的代价累加&＃xff0c;H为当前点到终点的预计代价。在这里我们假设每个方格为10×10的大小&＃xff0c;那么G分为直线代价&＃xff08;10&＃xff09;和斜线代价&＃xff08;14&＃xff09;&＃xff0c;H为当前点到终点的预计代价并且无视障碍&＃xff0c;那么像图中所示起点的下一步的代价总和已经可以计算得出&＃xff0c;就这样每一步都执行8次代价计算&＃xff08;有障碍物则舍弃&＃xff09;&＃xff0c;选择代价总和最小的走&＃xff0c;直到终点。

Qt中代码讲解

创建地图

地图的创建很简单&＃xff0c;用一个二维数组即可&＃xff0c;首先定义行数和列数&＃xff0c;在这里我将定义一个枚举变量&＃xff0c;令FLOOR为0&＃xff0c;WALL为1。

int map[ROWS][COLS]&＃61;{{WALL,WALL,WALL,WALL,WALL,WALL,WALL,WALL,WALL,WALL,WALL,WALL},{WALL,PERSON,FLOOR,FLOOR,FLOOR,WALL,FLOOR,FLOOR,FLOOR,FLOOR,FLOOR,WALL},{WALL,FLOOR,FLOOR,FLOOR,FLOOR,WALL,FLOOR,FLOOR,FLOOR,FLOOR,FLOOR,WALL},{WALL,FLOOR,FLOOR,FLOOR,WALL,WALL,FLOOR,FLOOR,WALL,FLOOR,FLOOR,WALL},{WALL,FLOOR,FLOOR,WALL,FLOOR,WALL,FLOOR,WALL,FLOOR,FLOOR,FLOOR,WALL},{WALL,FLOOR,FLOOR,WALL,FLOOR,WALL,FLOOR,WALL,FLOOR,FLOOR,FLOOR,WALL},{WALL,FLOOR,FLOOR,WALL,FLOOR,WALL,FLOOR,WALL,FLOOR,FLOOR,FLOOR,WALL},{WALL,FLOOR,FLOOR,FLOOR,FLOOR,FLOOR,FLOOR,WALL,FLOOR,FLOOR,FLOOR,WALL},{WALL,WALL,WALL,WALL,WALL,WALL,WALL,WALL,WALL,WALL,WALL,WALL},
};


获取地图中任意点的坐标&＃xff08;终点坐标获取&＃xff09;

因为我们的目的地是自己设置的&＃xff0c;所以此项目中我通过鼠标点击地图的位置获取坐标作为我们设置的目的地&＃xff1a;

if((p_x<(pt_x&＃43;SIZE/2))&&(p_x>(pt_x-SIZE/2))&&(p_y>(pt_y-SIZE/2))&&(p_y<(pt_y&＃43;SIZE/2))){str &＃61; QString("%1 , %2").arg(pt[i][j].x()).arg(pt[i][j].y());p_end.row&＃61;i;p_end.col&＃61;j;/*设置显示在label中坐标的颜色*/QPalette pa;pa.setColor(QPalette::WindowText,Qt::red);ui->label->setPalette(pa);ui->label->setText(str);//显示}}}


因为地图是采取网格式的&＃xff0c;所以在程序中进行了判断&＃xff0c;当鼠标点击到某个网格中任意一点时&＃xff0c;则将目的地坐标设置为此网格的中心坐标。

通过键盘控制人物移动&＃xff0c;并获取人物当前坐标&＃xff08;起点坐标获取&＃xff09;

笔者在地图里通过WSAD键可以控制人物的上下左右移动&＃xff0c;并且每次移动时将此时人物所在的坐标赋给起点。label中可以显示此时人物的坐标。

/*上下左右控制过程*/
void MainWindow::gameControl(enum Direction dir)
{//QPoint p &＃61; QCursor::pos();//获取鼠标的绝对位置QString str;if (dir &＃61;&＃61; UP) { // 上方向if (map[man.y - 1][man.x] &＃61;&＃61; FLOOR ) { // 上方向为地板changeMap(man.y, man.x, FLOOR); // 原位置换为地板changeMap(man.y - 1, man.x, PERSON); // 上方向位置换为人str &＃61; QString("%1 , %2").arg(pt[man.y-1][man.x].x()).arg(pt[man.y-1][man.x].y());p_start.row&＃61;man.x-1;p_start.col&＃61;man.y;ui->label->setText(str);//显示}}else if(dir &＃61;&＃61; DOWN){if (map[man.y &＃43; 1][man.x] &＃61;&＃61; FLOOR ) { // 下方向为地板changeMap(man.y, man.x, FLOOR); // 原位置换为地板changeMap(man.y &＃43; 1, man.x, PERSON); // 上方向位置换为人str &＃61; QString("%1 , %2").arg(pt[man.y&＃43;1][man.x].x()).arg(pt[man.y&＃43;1][man.x].y());p_start.row&＃61;man.x&＃43;1;p_start.col&＃61;man.y;ui->label->setText(str);//显示}}else if(dir &＃61;&＃61; LEFT){if (map[man.y][man.x-1] &＃61;&＃61; FLOOR ) { // 左方向为地板changeMap(man.y, man.x, FLOOR); // 原位置换为地板changeMap(man.y , man.x-1, PERSON); // 左方向位置换为人str &＃61; QString("%1 , %2").arg(pt[man.y][man.x-1].x()).arg(pt[man.y][man.x-1].y());p_start.row&＃61;man.x;p_start.col&＃61;man.y-1;ui->label->setText(str);//显示}}else if(dir &＃61;&＃61; RIGHT){if (map[man.y ][man.x&＃43;1] &＃61;&＃61; FLOOR ) { // 右方向为地板changeMap(man.y, man.x, FLOOR); // 原位置换为地板changeMap(man.y , man.x&＃43;1, PERSON); // 右方向位置换为人str &＃61; QString("%1 , %2").arg(pt[man.y][man.x&＃43;1].x()).arg(pt[man.y][man.x&＃43;1].y());p_start.row&＃61;man.x;p_start.col&＃61;man.y&＃43;1;ui->label->setText(str);//显示}}
}

A*核心算法代码

代码的核心部分采用N叉树结构&＃xff0c;即先将起点作为树的根&＃xff0c;其次分出8个树枝&＃xff0c;分别对应下一步的8个坐标方向&＃xff0c;在这8个中将有障碍物的剔除&＃xff0c;其余比较代价最小的那一个点&＃xff0c;然后再将这个点作为树根&＃xff0c;再依次向下伸张&＃xff0c;直到达到终点。最后再依次获得之前所走路径的坐标。程序中用到了C&＃43;&＃43;中STL中的vector容器。

通过选取终点&＃xff0c;利用QTimer实现自动寻路功能

此时算法核心已经完成。接下来实现图形化界面&＃xff1a;
通过鼠标事件获取到终点后&＃xff0c;此时路径上的坐标已经获得&＃xff0c;则设置一个定时器&＃xff0c;改变人物的位置

void MainWindow::start()
{if(p_end.col&＃61;&＃61;0&&p_end.row&＃61;&＃61;0){}else{timer &＃61;new QTimer(this);timer->start(1000);connect(timer,&QTimer::timeout,this,&MainWindow::road);}
}


每次经过1秒&＃xff0c;进行road函数&＃xff0c;人物坐标变换一次

void MainWindow::road()
{if(j>0){changeMap(p_road[j-1].row,p_road[j-1].col,PERSON);changeMap(p_road[j].row,p_road[j].col,FLOOR);j--;}elsetimer->stop();
}


Qt界面美化&＃xff0c;封装完成

在界面中设置了一些按钮的自定义&＃xff0c;添加了界面背景的背景图&＃xff0c;地图的资源图等

/******************************设置窗口格式**********************************///设置窗口格式this->setWindowFlag(Qt::FramelessWindowHint);//设置阴影QGraphicsDropShadowEffect *shadow &＃61;new QGraphicsDropShadowEffect(this);ui->centralwidget->setGraphicsEffect(shadow);shadow-> setBlurRadius(10);shadow-> setColor(Qt::black);shadow-> setOffset(0);//父窗口设置透明this->setAttribute(Qt::WA_TranslucentBackground);/**************************************************************************/


到此项目基本完成&＃xff0c;如果有需要交流和源代码的小伙伴可以加下我的vx&＃xff1a;17362997119&＃xff0c;希望能跟大佬们多交流交流&＃xff01;&＃xff01;