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

立即下载用AI写一个

发布时间：2018-07-30

278人 | 浏览：6738次 | 收藏 |

技术：Qt，A*，C++

运行环境：Qt5.5.0

概述

用Qt绘制可视化网格，验证A*算法。程序中，可以自行设置网格的大小和数量，也可以设置起点、终点和障碍物。点击搜索路径后，可以显示最佳路径。该项目用于验证A*的算法。

详细

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

**效果**

![](/contentImages/image/20180730/J0KsR55DArjacrif1O2.png)
![](/contentImages/image/20180730/TR6TLt9LgsIvEWfTQPr.png)

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

**项目文件截图**
 ![](/contentImages/image/20180730/erzJfjN1JCLL9NxMDPQ.png)

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

**定义最小网格类**
首先，我们需要定义一个最小网格类，用于绘制网格地图（GridMap）。
网格地图是将二维场景中的地图划分为一个个小网格，这个小网格是最小的空间单位，我们可以设置该网格为障碍物、起点或终点。
下面是最小网格类。
```cpp
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的过程。
```cpp
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对象的属性。代码很简单。在设置起点和终点是需要特别标记，因为如果地图中没有标定起点和终点，就无法寻路了。
```cpp
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()，然后再初始化地图。
```cpp
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()函数后，就会绘制地图了。

**更新地图**
不说了，看代码，很简单，后面详细介绍一下绘制地图和绘制路径。
```cpp
void MainWindow::paintEvent(QPaintEvent *e)
{
    DrawChessboard(); //绘制地图背景
    DrawItems();      //绘制地图
    DrawPath();       //绘制路径

update();
}

```

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

```
**寻找路径**
地图绘制好了以后，就可以寻路了。单击搜索路径后，就可以寻路了。寻路直线需要清除原来的路径，避免上次的路径影响。如果发现地图中没有起点和终点，就直接退出，避免造成寻路异常。
```cpp
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
博客上对A*的算法描述的非常清晰，简单易懂，我就不重复了。但是我用他的代码时，总是会出现路径越界，调试之后发现是边界检测那块有一点问题，也就是isCanreach()函数，读者可以好好对比一下。同时我在源码的基础上添加了一些清除开路径和闭路径的操作，不知道为什么源码没有。如果没有的话，会有问题的。

**绘制路径**
寻路完成以后，就可以直接绘制路径了。
```cpp
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*算法可视化分析

概述

详细

相似例子推荐

评论

作者

评分详细

作者例子