一、问题描述

迷宫是一个矩形区域，有一个入口和一个出口。迷宫内部包含不能穿越的墙壁或障碍物。这些障碍物沿着行和列防止，与迷宫的边界平行。迷宫的如果在左上角，出口在右下角。
在这里插入图片描述
我们可以使用一个 bool 矩阵来描述这个迷宫。当矩阵中某个位置有障碍时，其值为 ture，否则为 false。迷宫老鼠问题是要寻找一条从入口到出口的路径。路径是一个由位置组成的序列。每一个位置都没有障碍，而且除入口之外，路径上的每个位置是前一个位置在东、南、西、北上相邻的一个位置。

二、设计

我们采用自顶向下的方法设计这个程序。不难理解，这个程序有三个部分：输入迷宫，寻找路径和输出路径。书中使用三个模块实现这些部分。我们这里把输入和输出模块作为放在一起，除此之外，我们还有一个模块用于显示欢迎信息、软件名称及作者信息。为了简便，我们这里使用QT6.1.2 开发。

1、思路

该程序主体流程是：进入欢迎界面；让用户设置迷宫形状；根据用户的需要绘制迷宫；在用户点击寻找路径的按钮时绘制路径（支持多次绘制，暂不支持擦除）。
首先思考主体界面。主体界面自身有一个类。其实例中应该还有含有两个子对象。分别用于存放欢迎界面和迷宫界面（可以将设置界面独立）。由于这两个子对象不会同时显示，我们可以考虑使用 QStackedWidget 存放。
然后考虑欢迎界面。我们需要确认采取显示欢迎字样。这里我选择一个较为简单的淡入淡出的 label。由于该类可以由其它类复用，因此我们将公共接口提取并放在 util 文件夹中。
最后考虑迷宫界面。主体的布局采取左边为交互界面，右边为显式界面。比例为1:3。考虑到计算迷宫的策略可以动态切换，因此我们将计算迷宫的方式单独出来放在 business 文件夹中。二者之间的数据传递是一个 QVector<QVector> 用于表示地图每个矩形的状态。

2、类图

在这里插入图片描述

3、目录结构

[RatInMaze]
	RatInMaze.pro
	[document]
	[output]
	[src]
		main.cpp
		[business]
			CLS_FindPathStack.h
			CLS_FindPathStack.cpp
		[ui]
			CLS_MainWidget.h
			CLS_MainWidget.cpp
			CLS_MainWidget.ui
			CLS_Maze.h
			CLS_Maze.cpp
			CLS_Maze.ui
			CLS_Welcome.h
			CLS_Welcome.cpp
			CLS_Welcome.ui
			[util]
				CLS_LabelGradualChange.h
				CLS_LabelGradualChange.cpp

三、实现

1、ui文件

CLS_MainWidget.ui
在这里插入图片描述
CLS_Welcome.ui

CLS_Maze.ui

2、淡入淡出 label

qt 中的 css 不支持设置动画，因此需要使用定时器或线程实现淡入淡出。我们这里选择使用线程计时。淡入淡出的基本原理就是不断地改变透明度。
类声明为：

#ifndef CLS_LABELGRADUALCHANGE_H
#define CLS_LABELGRADUALCHANGE_H

#include <QLabel>

class CLS_LabelGradualChange : public QLabel
{
    Q_OBJECT

public:
    explicit CLS_LabelGradualChange(QWidget *parent = nullptr);
    ~CLS_LabelGradualChange();

    /*
     * @brief 设置渐变颜色
     * @param color 目标颜色
     */
    void setColor(QColor color);

    /*
     * @brief 设置淡入淡出时长
     * @param timeout 总时长
     */
    void setTimeout(int timeout);

    /*
     * @brief 设置颜色变化的总次数
     * @param timeout 总时长
     */
    void setTotalTimes(int totalTimes);

signals:
    void sigLoadFinished();

protected:
    virtual void showEvent(QShowEvent *event) override;

private:
    QString m_qstrStyleSheet;   // 预设的样式表，需要使用.arg拼接透明度
    int m_iTimeout = 0;         // 淡入淡出时长
    int m_iTotalTimes = 0;      // 颜色变化的总次数
    int m_iTimes = 0;
    bool m_blShow = true;

    void startShowThread();     // 线程中计时

private slots:
    /*
     * @brief 更新透明度槽
     */
    void slotShow();

};

#endif // CLS_LABELGRADUALCHANGE_H

实现文件：

#include "CLS_LabelGradualChange.h"
#include <QColor>
#include <QThread>

const int CONST_SHOW_TIMES = 20; // 默认显示20次

CLS_LabelGradualChange::CLS_LabelGradualChange(QWidget *parent) :
    QLabel(parent)
{
    m_iTotalTimes = CONST_SHOW_TIMES;
}

CLS_LabelGradualChange::~CLS_LabelGradualChange()
{

}

void CLS_LabelGradualChange::setColor(QColor color)
{
    m_qstrStyleSheet = styleSheet() + QString("color:rgba(%2,%3,%4,%5);").arg(color.red())
            .arg(color.green()).arg(color.blue());
}

void CLS_LabelGradualChange::setTimeout(int timeout)
{
    m_iTimeout = timeout;
}

void CLS_LabelGradualChange::setTotalTimes(int totalTimes)
{
    if (totalTimes > 0)
    {
        m_iTotalTimes = totalTimes;
    }
}

void CLS_LabelGradualChange::showEvent(QShowEvent*)
{
    if (m_blShow)
    {
        startShowThread();
        m_blShow = false;
    }
}

void CLS_LabelGradualChange::startShowThread()
{
    double dbInterval = double(m_iTimeout) / m_iTotalTimes;
    QThread *pThread = QThread::create([dbInterval](){QThread::msleep(dbInterval);});
    connect(pThread, SIGNAL(finished()), this, SLOT(slotShow()));
    pThread->start();
}

void CLS_LabelGradualChange::slotShow()
{
    ++m_iTimes;
    double opacity = 2.0 * double(m_iTimes >= m_iTotalTimes / 2 ? m_iTotalTimes - m_iTimes : m_iTimes) / m_iTotalTimes;
    setStyleSheet(m_qstrStyleSheet.arg(opacity));

    if (m_iTimes < m_iTotalTimes)
    {
        startShowThread();
    }
    else
    {
        emit sigLoadFinished();
    }
}

3、欢迎界面

类声明：

#ifndef CLS_WELCOME_H
#define CLS_WELCOME_H

#include <QWidget>

namespace Ui {
class CLS_Welcome;
}

class CLS_Welcome : public QWidget
{
    Q_OBJECT

public:
    explicit CLS_Welcome(QWidget *parent = nullptr);
    ~CLS_Welcome();

signals:
    /*
     * @brief 显式结束信号
     */
    void sigLoadFinished();

private:
    Ui::CLS_Welcome *ui;
};

#endif // CLS_WELCOME_H

实现文件：

#include "CLS_Welcome.h"
#include "ui_CLS_Welcome.h"

const QString CONST_GAMENAME = QObject::tr("RAT IN A MAZE");
const QString CONST_COPYRIGHT = QObject::tr("@coding-hwz,2021");
const QColor CONST_COLOR_GAMENAME = QColor(150, 152, 18);
const QColor CONST_COLOR_COPYRIGHT = QColor(255, 255, 255);
const int CONST_TIMEOUT = 1500;

CLS_Welcome::CLS_Welcome(QWidget *parent) :
    QWidget(parent),
    ui(new Ui::CLS_Welcome)
{
    ui->setupUi(this);
    if (parent)
    {
        setWindowFlags(Qt::FramelessWindowHint);
    }

    setStyleSheet("font:30px bold \"Times New Roman\";");
    ui->verticalLayout->setSpacing(50);

    ui->label_GameName->setText(CONST_GAMENAME);
    ui->label_CopyRight->setText(CONST_COPYRIGHT);

    ui->label_GameName->setAlignment(Qt::AlignCenter);
    ui->label_CopyRight->setAlignment(Qt::AlignCenter);

    ui->label_GameName->setColor(CONST_COLOR_GAMENAME);
    ui->label_CopyRight->setColor(CONST_COLOR_COPYRIGHT);

    ui->label_GameName->setTimeout(CONST_TIMEOUT);
    ui->label_CopyRight->setTimeout(CONST_TIMEOUT);

    connect(ui->label_CopyRight, SIGNAL(sigLoadFinished()), this, SIGNAL(sigLoadFinished()));
}

CLS_Welcome::~CLS_Welcome()
{
    delete ui;
}

4、迷宫界面

类声明：

#ifndef CLS_MAZE_H
#define CLS_MAZE_H

#include <QWidget>
#include <QStack>
#include "CLS_FindPathStack.h"

namespace Ui {
class CLS_Maze;
}

class CLS_Maze : public QWidget
{
    Q_OBJECT

public:
    explicit CLS_Maze(QWidget *parent = nullptr);
    ~CLS_Maze();

protected:
    void paintEvent(QPaintEvent*);
    void resizeEvent(QResizeEvent*);
    void mouseReleaseEvent(QMouseEvent* event);

private slots:
    void on_pushButton_FindPath_clicked();

    void on_pushButton_Restart_clicked();

private:
    Ui::CLS_Maze *ui;
    QVector<QVector<QRect>> m_vecRects;                 // 需要绘制的矩形坐标，先行后列
    QVector<QVector<bool>> m_vecRectsStatus;            // 矩形状态，为true说明有障碍物，为false没有
    QStack<CLS_FindPathStack::mapIndex> m_stackPath;    // 从入口到出口的路径

    /*
     * @brief 初始化矩形坐标
     */
    void initRects();

    /*
     * @brief 绘制矩形
     * @param painter 绘图对象
     */
    void drawMaze(QPainter& painter);

    /*
     * @brief 绘制路径
     * @param painter 绘图对象
     */
    void drawPath(QPainter& painter);
};

#endif // CLS_MAZE_H

实现文件：

#include "CLS_Maze.h"
#include "ui_CLS_Maze.h"

#include <QPainter>
#include <QMouseEvent>
#include <QStack>
#include <optional>
#include <QMessageBox>

const int CONST_LINE_NUM = 10;  // 默认每行、列矩形数
const int CONST_MARGIN = 50;    // 边距
const int CONST_LINE_WIDTH = 2; // 矩形边线宽
const int CONST_RATIO = 3;      // 矩形显示界面与用户控制界面宽度比

const QString CONST_BUTTONTEXT_FINDPATH = QObject::tr("显示路线");
const QString CONST_BUTTONTEXT_RESTART = QObject::tr("重新绘制");
const QString CONST_INFORMATION_NOPATH = QObject::tr("路线不存在");
const QString CONST_BUTTON_STYLE = QString("QPushButton{ \
                                        background-color:rgb(134,183,200);\
                                        border:2px solid #5F92B2;\
                                        border-radius:5px;\
                                        color:white;\
                                        margin: %1 0 %1 %1;\
                                        height: 50px;\
                                    }\
                                    QPushButton:hover{\
                                        background-color:rgb(0,130,150);\
                                        border:2px solid #5F92B2;\
                                        border-radius:5px;\
                                        color:white;\
                                    }\
                                    QPushButton:pressed{\
                                        background-color:rgb(85,170,255);\
                                        border:2px solid #3C80B1;\
                                        border-radius:5px;\
                                        color:white;\
                                    }").arg(CONST_MARGIN);

CLS_Maze::CLS_Maze(QWidget *parent) :
    QWidget(parent),
    ui(new Ui::CLS_Maze),
    m_vecRects(CONST_LINE_NUM, QVector<QRect>(CONST_LINE_NUM)),
    m_vecRectsStatus(CONST_LINE_NUM, QVector<bool>(CONST_LINE_NUM))
{
    ui->setupUi(this);
    ui->horizontalLayout->setStretch(0,1);
    ui->horizontalLayout->setStretch(1,CONST_RATIO);
    ui->widget_Rect->setStyleSheet("background-color:transparent");
    setStyleSheet(CONST_BUTTON_STYLE);
    ui->pushButton_FindPath->setText(CONST_BUTTONTEXT_FINDPATH);
    ui->pushButton_Restart->setText(CONST_BUTTONTEXT_RESTART);
}

CLS_Maze::~CLS_Maze()
{
    delete ui;
}

void CLS_Maze::paintEvent(QPaintEvent*)
{
    QPainter painter(this);
    painter.setPen(QPen(Qt::white, CONST_LINE_WIDTH));
    drawMaze(painter);
    drawPath(painter);
}

void CLS_Maze::resizeEvent(QResizeEvent*)
{
    initRects();
    update(ui->widget_Rect->geometry());
}

void CLS_Maze::mouseReleaseEvent(QMouseEvent* event)
{
    auto pos = event->pos();

    // 寻找目标点位于矩阵的哪一行
    auto find1D = [&pos](QVector<QRect>& vecRect)
    {
        return vecRect.first().top() < pos.y() && vecRect.last().bottom() > pos.y() &&
                vecRect.first().left() < pos.x() && vecRect.last().right() > pos.x();
    };

    auto iterVec = std::find_if(m_vecRects.begin(), m_vecRects.end(), find1D);
    if (iterVec == m_vecRects.end())
    {
        return;
    }

    // 寻找目标点位于改行的哪一列
    auto find2D = [&pos](QRect& rect)
    {
        return rect.top() < pos.y() && rect.bottom() > pos.y() && rect.left() < pos.x() && rect.right() > pos.x();
    };

    auto iterRect = std::find_if(iterVec->begin(), iterVec->end(), find2D);
    if (iterRect == iterVec->end())
    {
        return;
    }

    m_vecRectsStatus[std::distance(m_vecRects.begin(), iterVec)][std::distance(iterVec->begin(), iterRect)] = true;
    update(*iterRect);
}

void CLS_Maze::initRects()
{
    m_vecRects.clear();

    int iVerticalStart = ui->widget_Rect->geometry().top() + CONST_MARGIN;
    int iVerticalDist = (ui->widget_Rect->geometry().height() - 2 * CONST_MARGIN) / CONST_LINE_NUM;
    int iHorizontalStart = ui->widget_Rect->geometry().left() + CONST_MARGIN;
    int iHorizontalDist = (ui->widget_Rect->geometry().width() - 2 * CONST_MARGIN) / CONST_LINE_NUM;
    for (int i = 0; i < CONST_LINE_NUM; ++i)
    {
        QVector<QRect> vecRect(CONST_LINE_NUM);
        for (int j = 0; j < CONST_LINE_NUM; ++j)
        {
            vecRect[j] = QRect(iHorizontalStart + j * iHorizontalDist, iVerticalStart + i * iVerticalDist,
                                      iHorizontalDist, iVerticalDist);
        }
        m_vecRects.push_back(std::move(vecRect));
    }
}

void CLS_Maze::initRectStatus()
{
    for (int i = 0; i < CONST_LINE_NUM; ++i)
    {
        for (int j = 0; j < CONST_LINE_NUM; ++j)
        {
            m_vecRectsStatus[i][j] = false;
        }
    }
}

void CLS_Maze::drawMaze(QPainter& painter)
{
    for (int i = 0; i < m_vecRects.size(); ++i)
    {
        for (int j = 0; j < m_vecRects[i].size(); ++j)
        {
            painter.drawRect(m_vecRects[i][j]);

            if (m_vecRectsStatus[i][j])
            {
                painter.fillRect(m_vecRects[i][j] - QMargins(CONST_LINE_WIDTH, CONST_LINE_WIDTH, CONST_LINE_WIDTH, CONST_LINE_WIDTH), QColor(0, 255, 255));
            }
        }
    }
}

void CLS_Maze::drawPath(QPainter &painter)
{
    QVector<QPoint> path;

    for (int i = 0; i < m_stackPath.size() - 1; ++i)
    {
        auto cur = m_stackPath.at(i);
        auto next = m_stackPath.at(i + 1);
        path.push_back(m_vecRects.at(cur.first).at(cur.second).center());
        path.push_back(m_vecRects.at(next.first).at(next.second).center());
    }

    painter.drawLines(path);
}

void CLS_Maze::on_pushButton_FindPath_clicked()
{
    m_stackPath.clear();
    CLS_FindPathStack findPathObj(m_vecRectsStatus);
    auto optPath = findPathObj.findPath();
    if (optPath.has_value())
    {
        m_stackPath = optPath.value();
        update(ui->widget_Rect->geometry());
    }
    else
    {
        QMessageBox::information(nullptr, "", CONST_INFORMATION_NOPATH);
    }
}

void CLS_Maze::on_pushButton_Restart_clicked()
{
    initRects();
    initRectStatus();
    m_stackPath.clear();
    update(ui->widget_Rect->geometry());
}

这里按钮的样式上网找了个，感觉还可以 —— Qt 精美的button合集。

5、主窗体

类声明：

#ifndef CLS_MAINWIDGET_H
#define CLS_MAINWIDGET_H

#include <QWidget>

QT_BEGIN_NAMESPACE
namespace Ui { class CLS_MainWidget; }
QT_END_NAMESPACE

class CLS_MainWidget : public QWidget
{
    Q_OBJECT

public:
    CLS_MainWidget(QWidget *parent = nullptr);
    ~CLS_MainWidget();

    /*
     * @brief 进入欢迎界面
     */
    void welcome();

private:
    Ui::CLS_MainWidget *ui;

private slots:
    /*
     * @brief 加载完成处理槽
     */
    void slotLoadFinished();
};
#endif // CLS_MAINWIDGET_H

实现文件：

#include "CLS_MainWidget.h"
#include "ui_CLS_MainWidget.h"
#include "CLS_Welcome.h"
#include "CLS_Maze.h"

CLS_MainWidget::CLS_MainWidget(QWidget *parent)
    : QWidget(parent)
    , ui(new Ui::CLS_MainWidget)
{
    ui->setupUi(this);
    setStyleSheet("background-color:#000;");
}

CLS_MainWidget::~CLS_MainWidget()
{
    delete ui;
}

void CLS_MainWidget::welcome()
{
    auto pMaze = new CLS_Maze;
    ui->stackedWidget->addWidget(pMaze);

    auto pWelcome = new CLS_Welcome;
    int index = ui->stackedWidget->addWidget(pWelcome);
    connect(pWelcome, SIGNAL(sigLoadFinished()), this, SLOT(slotLoadFinished()));
    ui->stackedWidget->setCurrentIndex(index);
}

void CLS_MainWidget::slotLoadFinished()
{
    ui->stackedWidget->removeWidget(ui->stackedWidget->currentWidget());
}

6、算法

从迷宫的内部位置开始，每个点都有四个移动方向，上下左右。从迷宫的边界开始，则只有两种或三种移动方向。为了避免再处理内部位置和边界位置是存在差异，我们可以在迷宫的周围增加一圈障碍物。因此迷宫的行列都将各增加2.这样虽然会稍稍增加所需要的空间。但是却让我们简化了代码的设计。

我们这里考虑使用栈结构来保存结果路径。初始情况下，仅有矩阵坐标(1,1)放入栈中。然后我们需要决定下一次向哪里移动。为了简便处理四个方向的移动，我们用一个数组保存四个方向行、列的移动距离：(0,1)、(1,0)、(-1,0)、(0,-1)，右下左上。这同样也是我们寻找路径考虑方向的优先级顺序。为了不重复已经走过的路程，我们每走过一个矩阵就将其标记为 true。
注意我们这个算法并不能保证能找到最短路径。

类声明：

#ifndef CLS_FINDPATHSTACK_H
#define CLS_FINDPATHSTACK_H
#include <QGenericMatrix>

class CLS_FindPathStack
{
public:
    typedef QPair<int, int> mapIndex; // 矩阵坐标

    CLS_FindPathStack(const QVector<QVector<bool>>& vecRectsStatus);

    /*
     * @brief 寻找目标路径
     * @return 路径的矩阵坐标（逆序）
     */
    std::optional<QStack<mapIndex>> findPath();

private:
    QVector<QVector<bool>> m_vec2DMapstatus; // 矩阵状态
};

#endif // CLS_FINDPATHSTACK_H

实现文件：

#include "CLS_FindPathStack.h"
#include <QStack>
#include <optional>

CLS_FindPathStack::CLS_FindPathStack(const QVector<QVector<bool>>& vecRectsStatus):
    m_vec2DMapstatus(vecRectsStatus)
{
    // 在迷宫周围增加一圈障碍物
    m_vec2DMapstatus.push_front(QVector<bool>(vecRectsStatus.at(0).size(), true));
    m_vec2DMapstatus.push_back(QVector<bool>(vecRectsStatus.at(0).size(), true));

    for (auto& vecStatus : m_vec2DMapstatus)
    {
        vecStatus.push_front(true);
        vecStatus.push_back(true);
    }
}

std::optional<QStack<CLS_FindPathStack::mapIndex>> CLS_FindPathStack::findPath()
{
    // 判断终点是否可达
    if (m_vec2DMapstatus.at(m_vec2DMapstatus.size() - 2).at(m_vec2DMapstatus.at(0).size() - 2) == true)
    {
        return std::nullopt;
    }

    mapIndex offset[4] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};    // 右下左上
    int offsetLength = 4;

    QStack<mapIndex> path;
    mapIndex here(1, 1);                                        // 用于保存当前栈顶元素，即当前循环从here元素寻址
    path.append(mapIndex(0,0));
    m_vec2DMapstatus[here.first][here.second] = true;


    mapIndex next;
    mapIndex exit(m_vec2DMapstatus.size() - 2, m_vec2DMapstatus.at(0).size() - 2);
    while (here != exit)
    {
        // 找到一条路线尝试
        int nextPos = 0;
        while (nextPos != offsetLength)
        {
            next.first = (here.first + offset[nextPos].first);
            next.second = (here.second + offset[nextPos].second);
            if (!m_vec2DMapstatus.at(next.first).at(next.second))
            {
                break;
            }

            nextPos++;
        }

        if (nextPos != offsetLength)
        {
            // 路径可达，将该点放入路径中并标记为已访问
            path.push(mapIndex(next.first - 1, next.second - 1));
            m_vec2DMapstatus[next.first][next.second] = true;
            here = next;
        }
        else
        {
            if (path.empty())
            {
                // 路径不可达且起点已弹栈，返回失败
                return std::nullopt;
            }

            path.pop();
            here.first = path.top().first + 1;
            here.second = path.top().second + 1;
        }
    }
    return path;
}

该算法的复杂度为 O(size)，与矩阵的元素个数成正比。

7、主文件

#include "CLS_MainWidget.h"

#include <QApplication>

int main(int argc, char *argv[])
{
    QApplication a(argc, argv);
    CLS_MainWidget w;
    w.show();
    w.welcome();
    return a.exec();
}