需求
之前做过一个无人车需要自主寻找最佳路径，所以研究了相关的寻路算法，最终选择A算法，因为其简单易懂，是入门级的寻路算法。
但是在验证的算法的时候，没有直观的感受，总是觉得会有什么问题，所以我就写了一个可视化的A算法验证，界面基于Qt开发。
项目说明
本项目主要分为2个部分，Qt绘制网格和A算法实现。下面可以看到，界面的实现和A算法的实现基本上是分离的。也就是说可以单独使用，比如Qt网格绘制，可以用于扫雷游戏，A*算法的代码可以直接拷贝，稍作修改就可以直接用于游戏，或者无人车。
效果
操作说明
鼠标右键：设置障碍物；鼠标左键：设置起点和终点。
项目文件截图
项目实现
程序的实现流程：定义一个最小网格类->通过鼠标设置起点、终点和障碍物，并实时绘制->寻找路径->绘制路径。
定义最小网格类
首先，我们需要定义一个最小网格类，用于绘制网格地图（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
博客上对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大师代发，拒绝转载，转载需要作者授权