博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
基于Qt的A*算法可视化分析
阅读量:6247 次
发布时间:2019-06-22

本文共 5481 字,大约阅读时间需要 18 分钟。

代码地址如下:

需求

之前做过一个无人车需要自主寻找最佳路径,所以研究了相关的寻路算法,最终选择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
rowItems; for(int j=0; j

其中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"<

代码很简单,关键就是path=astar.GetPath().下面重点分析一下寻路的过程。

寻路的代码不是本人写了,原作者已经不记得了,但是他的代码有点问题,我调试后做了修改。下面是我参考的博客:
博客上对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
算法可视化分析

代码地址如下:

注:本文著作权归作者,由demo大师代发,拒绝转载,转载需要作者授权

你可能感兴趣的文章
dotnet --info
查看>>
运算符优先级
查看>>
接口测试-python
查看>>
python使用hbase
查看>>
我太水了~
查看>>
Mysql-proxy中的lua脚本编程(一)
查看>>
SY-SUBRC 的含义【转】
查看>>
仓库管理系统用例建模
查看>>
转换数字为人民币大写金额
查看>>
Python爬虫之爬取西刺免费IP并保存到MySQL
查看>>
PostgreSQL的进程结构
查看>>
[HBase_2] HBase数据模型
查看>>
Android之Sqlite数据库
查看>>
高并发编程-CountDownLatch深入解析
查看>>
Sublime 中文标题乱码
查看>>
世界上最幸福的职业-鉴黄师
查看>>
asp.net 10 Cookie & Session
查看>>
[置顶]C# 邮件发送方法【NetMail方式】
查看>>
一个数据库系统的笔试题
查看>>
使用Form个性化修改标准Form的LOV
查看>>