基于Qt的A*算法可视化分析

男娘i 2022-05-11 04:34 213阅读 0赞

> 代码地址如下：  
> [http://www.demodashi.com/demo/13677.html][http_www.demodashi.com_demo_13677.html]

**需求**  
之前做过一个无人车需要自主寻找最佳路径，所以研究了相关的寻路算法，最终选择A*算法，因为其简单易懂，是入门级的寻路算法。  
但是在验证的算法的时候，没有直观的感受，总是觉得会有什么问题，所以我就写了一个可视化的A*算法验证，界面基于Qt开发。  
**项目说明**  
本项目主要分为2个部分，Qt绘制网格和A*算法实现。下面可以看到，界面的实现和A*算法的实现基本上是分离的。也就是说可以单独使用，比如Qt网格绘制，可以用于扫雷游戏，A\*算法的代码可以直接拷贝，稍作修改就可以直接用于游戏，或者无人车。

**效果**

![J0KsR55DArjacrif1O2.png][]  
![TR6TLt9LgsIvEWfTQPr.png][]

**操作说明**  
鼠标右键：设置障碍物；鼠标左键：设置起点和终点。

**项目文件截图**  
![erzJfjN1JCLL9NxMDPQ.png][]

**项目实现**  
程序的实现流程：定义一个最小网格类->通过鼠标设置起点、终点和障碍物，并实时绘制->寻找路径->绘制路径。

**定义最小网格类**  
首先，我们需要定义一个最小网格类，用于绘制网格地图（GridMap）。  
网格地图是将二维场景中的地图划分为一个个小网格，这个小网格是最小的空间单位，我们可以设置该网格为障碍物、起点或终点。  
下面是最小网格类。

class Item { public: Item(); Item(QPoint pos); QPoint m_pos; //position bool m_bIsObstacle; //whether is obstacle int m_nObjectType; //the object type , Nothing,Robot or goal };

可以看出最小网格对象很简单，只需要一个位置信息，障碍物标志位，机器人或目标点标志。以上就是最小网格的全部属性，当然如果想要实现更加复杂的功能，可以添加属性。

**初始化地图**  
初始化地图是指将2维地图划分为网格的过程，其实就是new Item的过程。

void MainWindow::InitItems() { for(int i=0; i<m_nColumes; i++) { QVector<Item*> rowItems; for(int j=0; j<m_nRows; j++) { QPoint pos = QPoint(i,j); Item* pItem = new Item(pos); rowItems.append(pItem); } m_items.append(rowItems); } }

其中m\_nColumes和m\_nRows是在初始化地图之前设置的长宽。

**设置障碍物**  
在寻路之前，我们要先设置好障碍物、起点和终点。设置障碍物用鼠标右键，单击右键，设置小网格为障碍物，再次单击取消障碍物；设置起点和终点用鼠标左键，单击左键1次，设置小网格为起点，再次单击为终点，再次单击为空白，依次循环。  
这里我们用鼠标事件实现，可以看到其实就是根据鼠标事件来设置相应位置Item对象的属性。代码很简单。在设置起点和终点是需要特别标记，因为如果地图中没有标定起点和终点，就无法寻路了。

void MainWindow::mousePressEvent(QMouseEvent * e) { //得到鼠标处的格子坐标 QPoint pt; pt.setX( (e->pos().x() - START_X ) / RECT_WIDTH); pt.setY( (e->pos().y() - START_X ) / RECT_HEIGHT); //wheather is the point in the Game area if (!PointInGameArea(pt)) { return; } //获取所点击矩形元素 Item* pItem = m_items[pt.x()][pt.y()]; //leftbutton set object tpye,rightbutton set obstacle if(e->button()==Qt::LeftButton) //left button ,set Robot or goal { // pItem->m_nObjectType++; pItem->m_nObjectType%=3; pItem->m_bIsObstacle=false; //clear obstacle } else if(e->button()==Qt::RightButton) //set obstacle or not obstacle { pItem->m_nObjectType=0; //clear object type if (pItem->m_bIsObstacle) { pItem->m_bIsObstacle = false; } else { pItem->m_bIsObstacle = true; } } }

鼠标事件会自动触发paintEvent()函数，所以在点击鼠标后，地图会重绘。

**新建地图**  
新建地图需要将上次的地图清除，也就是ReleaseItems()，同时清除路径ReleasePath()，然后再初始化地图。

void MainWindow::NewGame() { resize(START_X*2 + m_nColumes*RECT_WIDTH ,START_Y*2 + m_nRows*RECT_HEIGHT); ReleaseItems(); ReleasePath(); InitItems(); }

无论是初始化地图还是新建地图，都没有提到地图的绘制，那么地图什么时候绘制呢？在NewGame()中有一个Resize()函数，也就是改变窗口的大小，该函数会触发paintEvent（）函数，所以当调用NewGame()函数后，就会绘制地图了。

**更新地图**  
不说了，看代码，很简单，后面详细介绍一下绘制地图和绘制路径。

void MainWindow::paintEvent(QPaintEvent *e) { DrawChessboard(); //绘制地图背景 DrawItems(); //绘制地图 DrawPath(); //绘制路径 update(); }

**绘制地图**  
绘制地图其实就是根据相应位置的Item对象的属性，来绘制该网格。网格属性在初始化和设置障碍物时，已经设置好了。代码很简单，就是判断网格属性是障碍物还是起点，然后直接绘制就好了。

void MainWindow::DrawItem(QPainter& painter,Item* pItem) { if(pItem->m_bIsObstacle) //show obstacle { QRect rcSrc(0,0,m_ObstacleImage.width(),m_ObstacleImage.height()); QRect rcTarget(START_X + pItem->m_pos.x()*RECT_WIDTH + 2,START_Y + pItem->m_pos.y()*RECT_HEIGHT + 2,RECT_WIDTH-4,RECT_HEIGHT-4); painter.drawPixmap(rcTarget,m_ObstacleImage,rcSrc); painter.setBrush(Qt::transparent); painter.drawRect( START_X + pItem->m_pos.x()*RECT_WIDTH,START_Y + pItem->m_pos.y()*RECT_HEIGHT,RECT_WIDTH,RECT_HEIGHT); return; } else if (pItem->m_nObjectType!=0) //show Robot item or goal item { if(pItem->m_nObjectType == 1) //show Robot { QRect rcSrc(0,0,m_RobotImage.width(),m_RobotImage.height()); QRect rcTarget(START_X + pItem->m_pos.x()*RECT_WIDTH + 2,START_Y + pItem->m_pos.y()*RECT_HEIGHT + 2,RECT_WIDTH-4,RECT_HEIGHT-4); painter.drawPixmap(rcTarget,m_RobotImage,rcSrc); painter.setBrush(Qt::transparent); painter.drawRect( START_X + pItem->m_pos.x()*RECT_WIDTH,START_Y + pItem->m_pos.y()*RECT_HEIGHT,RECT_WIDTH,RECT_HEIGHT); return ; } else { QRect rcSrc(0,0,m_GoalImage.width(),m_GoalImage.height()); QRect rcTarget(START_X + pItem->m_pos.x()*RECT_WIDTH + 2,START_Y + pItem->m_pos.y()*RECT_HEIGHT + 2,RECT_WIDTH-4,RECT_HEIGHT-4); painter.drawPixmap(rcTarget,m_GoalImage,rcSrc); painter.setBrush(Qt::transparent); painter.drawRect( START_X + pItem->m_pos.x()*RECT_WIDTH,START_Y + pItem->m_pos.y()*RECT_HEIGHT,RECT_WIDTH,RECT_HEIGHT); return; } } else { painter.setBrush(Qt::green); } painter.drawRect( START_X + pItem->m_pos.x()*RECT_WIDTH,START_Y + pItem->m_pos.y()*RECT_HEIGHT,RECT_WIDTH,RECT_HEIGHT); }

**寻找路径**  
地图绘制好了以后，就可以寻路了。单击搜索路径后，就可以寻路了。寻路直线需要清除原来的路径，避免上次的路径影响。如果发现地图中没有起点和终点，就直接退出，避免造成寻路异常。

void MainWindow::OnSearchPath() { ReleasePath(); createMazeMap(); //create Maze map and start end point if(!m_bIsHaveRobot || !m_bIsHaveGoal) { std::cout<<"have not roobot or goal"<<std::endl; return; } astar.InitAstar(mazeMap); path=astar.GetPath(start, end, false); markPathInMazeMap(); printMazeMap(); printPath(); if(!path.empty()) path.pop_back(); if(!path.empty()) path.pop_front(); update(); }

代码很简单，关键就是path=astar.GetPath().下面重点分析一下寻路的过程。  
寻路的代码不是本人写了，原作者已经不记得了，但是他的代码有点问题，我调试后做了修改。下面是我参考的博客：  
[https://www.cnblogs.com/wlzy/p/7096114.html][https_www.cnblogs.com_wlzy_p_7096114.html]  
博客上对A\*的算法描述的非常清晰，简单易懂，我就不重复了。但是我用他的代码时，总是会出现路径越界，调试之后发现是边界检测那块有一点问题，也就是isCanreach()函数，读者可以好好对比一下。同时我在源码的基础上添加了一些清除开路径和闭路径的操作，不知道为什么源码没有。如果没有的话，会有问题的。

**绘制路径**  
寻路完成以后，就可以直接绘制路径了。

void MainWindow::DrawPath() { QPainter painter(this); painter.setBrush(Qt::yellow); if(!path.empty()) for(auto &p:path) { painter.drawRect( START_X + p->x*RECT_WIDTH,START_Y + p->y*RECT_HEIGHT,RECT_WIDTH,RECT_HEIGHT); } }

**总结**  
完成了基于Qt的A*算法可视化分析后，我发现以后很多算法都可以可视化分析了，非常直观，有助于理解算法。  
基于Qt的A*算法可视化分析

> 代码地址如下：  
> [http://www.demodashi.com/demo/13677.html][http_www.demodashi.com_demo_13677.html]

> 注：本文著作权归作者，由demo大师发表，拒绝转载，转载需要作者授权

[http_www.demodashi.com_demo_13677.html]: http://www.demodashi.com/demo/13677.html
[J0KsR55DArjacrif1O2.png]: /images/20220511/76cecd8bbcb142ef8f2a9b41c1d5e580.png
[TR6TLt9LgsIvEWfTQPr.png]: /images/20220511/3e2050aca52f4b2c98982c73f72673d3.png
[erzJfjN1JCLL9NxMDPQ.png]: /images/20220511/906b2479d16c4c288c4b491f5ec31cb0.png
[https_www.cnblogs.com_wlzy_p_7096114.html]: https://www.cnblogs.com/wlzy/p/7096114.html