Qt -DFS可視化

博客主頁：【夜泉_ly】
本文專欄：【暫無】
歡迎點贊👍收藏?關注??

在這里插入圖片描述

前言

本來，我是在搞我的戰棋小游戲的，
如果大家玩過戰棋應該知道，
當我們點擊一個單位時，
一般會顯示出一片區域，
表示這個單位的移動范圍(以及可攻擊目標等等)。

我當時就想到了用DFS和BFS，
然后就寫了。

之后我想，
既然已經在游戲中實現了DFS，
那能不能以現有代碼為基礎，
寫一個DFS算法可視化呢？
感覺很有意思，
所以有了本文。

當然，雖然標題叫做DFS可視化，
但是代碼部分大多是在對戰棋游戲的實現進行試驗，
因此存在很多‘多余’的設計，大家看看就行。

關于如何sleep

既然是可視化，
那必定不能等DFS完了再更新地圖狀態，
因此我決定在每次更新了一個格子的狀態后，
就暫停一會兒再繼續DFS。

結果問題來了，
怎么做到每次都暫停一會兒？

我本來想直接在DFS中直接加sleep就好了：
在這里插入圖片描述
然后程序卡了，
DFS完了才更新界面。
我以為是沒用信號觸發的問題，
改成用信號觸發地格更新：

結果還是不行。
為什么？
最開始我以為和Linux中多線程競爭鎖的問題類似，
大概描述一下就是：
搶鎖 - 我搶到了! - 我釋放 - 欸我離得近，我再搶！
然后發現了一個本質的區別：
這里只有一個線程啊🤣！

問題出在事件隊列：
當前這個DFS就是事件隊列的一個事件，
而DFS發送的信號所觸發的事件，
不過是去事件隊列后面排隊罷了，
那現在執行的是誰？
還是DFS！
我DFS沒跑完，
你們后面的事件都別想跑！

所以用QTimer？
我這是DFS。。。
如果用QTimer，那得搞個stack，
然后用類似非遞歸版的DFS來做吧？

我最終的解決方案是，
使用子線程跑DFS，
這樣就不會阻塞主線程的事件隊列了。

實現思路

那么大致分為幾個模塊

首先是圖片模塊，
這里搞的單例模式，
用于加載圖片給所有人用。
為什么提前加載？
因為不這樣做會很卡。。。

然后是地圖格模塊，
我感覺地圖格在戰棋游戲中還挺重要的，
所以把很多屬性存進去了，
這里只是個DFS可視化，
所有只保留關鍵的一些屬性。

然后是子線程模塊，
主要作用是進行DFS和發送信號。

最后就是widget主窗口，
進行初始化地圖，處理用戶交互等工作。

Pixmaps

比較簡單，比較作用就是加載和存儲圖片。
注意這里不能用餓漢模式，
圖片的加載必須放在QApplication對象創建之后。

pixmaps.h

#ifndef PIXMAPS_H
#define PIXMAPS_H
#include <QPixmap>
class Pixmaps {static Pixmaps *getInstance();
private:Pixmaps();Pixmaps(const Pixmaps&) = delete;static void* _instance;
public:QPixmap map0, map1, map2, map3, dst, src;const int map_width = 100, map_height = 100,unit_width = 80, unit_height = 80;
};
#endif // PIXMAPS_H

pixmaps.cpp

#include "pixmaps.h"
void* Pixmaps::_instance = nullptr; // 這個不能放.h   --  會造成重定義問題// 報錯會提示在其他包含了這個.h文件中, 重定義了_instance
Pixmaps* Pixmaps::getInstance(){if(_instance == nullptr){// 加鎖。。。懶得加了if(_instance == nullptr){_instance = new Pixmaps;}}return (Pixmaps*)_instance;
}Pixmaps::Pixmaps(): map0("://image/map0.png"), map1("://image/map1.png"), map2("://image/map2.png"), map3("://image/map3.png"), map_src("://image/map_src.png"), map_dst("://image/map_dst.png")
{map0 = map0.scaled(map_width, map_height, Qt::IgnoreAspectRatio, Qt::SmoothTransformation);map1 = map1.scaled(map_width, map_height, Qt::IgnoreAspectRatio, Qt::SmoothTransformation);map2 = map2.scaled(map_width, map_height, Qt::IgnoreAspectRatio, Qt::SmoothTransformation);map3 = map3.scaled(map_width, map_height, Qt::IgnoreAspectRatio, Qt::SmoothTransformation);map_dst = map_dst.scaled(map_width, map_height, Qt::IgnoreAspectRatio, Qt::SmoothTransformation);map_src = map_src.scaled(map_width, map_height, Qt::IgnoreAspectRatio, Qt::SmoothTransformation);
}

單例，只是為了讓別人更方便的用圖片罷了，
所以不用搞太復雜 - - 至少這里不用。

MapSquare

地格類

mapsquare.h

#ifndef MAPSQUARE_H
#define MAPSQUARE_H
#include <QLabel>
#include "pixmaps.h"class MapSquare : public QLabel
{Q_OBJECT
public:MapSquare(QWidget *parent = nullptr);enum UNIT_TYPE{UNIT_TYPE_EMPTY = 0,UNIT_TYPE_PLAYER1 = 1,UNIT_TYPE_PLAYER2 = 2};enum STATUS{STATUS_UNCHECKABLE = -1,STATUS_EMPTY = 0,STATUS_MOVE = 1,STATUS_ATTACK = 2,};void setStatus(STATUS new_status, bool update_pixmap = true);void setUnitType(UNIT_TYPE new_type);void setIndex(int r, int c);void setSrc(int r = -1, int c = -1);void setUnit(void* unit = nullptr);STATUS status(){return _status;}UNIT_TYPE unit_type(){return _unit_type;}int r(){return index_r;}int c(){return index_c;}int src_r() {return _src_r;}int src_c() {return _src_c;}void* unit() {return _unit;}
private:UNIT_TYPE _unit_type;STATUS _status;int index_r, index_c;int _src_r = -1, _src_c = -1;void* _unit = nullptr;
};
#endif // MAPSQUARE_H

嗯，基本是直接cv過來的，enum都沒改，
畢竟要改的話太麻煩了。

這里保留了我們需要用的，
_unit_type，即地格上面有什么，
無、陣營1(這里就是起點)、陣營2(這里就是終點)。

_status，即地格的狀態，
不可達請添加圖片描述、空、可抵達、可攻擊(這里用來表示DFS找到的路徑)。

r和c，表示地格在地圖中的坐標。

_src_r、_src_c、_unit，這里不用管。

mapsquare.cpp

#include "mapsquare.h"MapSquare::MapSquare(QWidget *parent): QLabel(parent) {int w = Pixmaps::getInstance()->map_width,h = Pixmaps::getInstance()->map_height;setGeometry(-w, -h, w, h);setStatus(STATUS_EMPTY);_unit_type = UNIT_TYPE_EMPTY;
}void MapSquare::setStatus(STATUS new_status, bool update_pixmap){_status = new_status;if(update_pixmap){if(_status == STATUS_UNCHECKABLE){setPixmap(Pixmaps::getInstance()->map0);} else if(_status == STATUS_EMPTY){setPixmap(Pixmaps::getInstance()->map1);} else if(_status == STATUS_MOVE){setPixmap(Pixmaps::getInstance()->map2);} else if(_status == STATUS_ATTACK){setPixmap(Pixmaps::getInstance()->map3);}}
}void MapSquare::setUnitType(UNIT_TYPE new_type) {_unit_type = new_type;
}void MapSquare::setIndex(int r, int c) {index_r = r;index_c = c;
}void MapSquare::setSrc(int r, int c) {_src_r = r;_src_c = c;
}void MapSquare::setUnit(void *unit) {_unit = unit;
}

都是簡單的賦值，應該不必多說吧。

dfsthread

用于DFS的線程，本篇的核心。

dfsthread.h

#ifndef DFSTHREAD_H
#define DFSTHREAD_H#include "mapsquare.h"
#include <QObject>
#include <QWidget>
#include <QThread>
#include <QWaitCondition>
#include <QMutex>class DfsThread : public QThread
{Q_OBJECT
public:explicit DfsThread(QWidget *parent = nullptr);void init(QVector<QVector<MapSquare*>>& _map, int _r, int _c, int _max_step);public:void pause();void resume();void oneStep(bool);protected:void run() override;bool dfs(int r, int c, int step, int max_step);signals:void updateSquare(int r, int c, MapSquare::STATUS status);void dstNotFound();private:QVector<QVector<MapSquare*>>* map; // 這里要不斷更改指向, 所以不能用引用QVector<QVector<bool>> visited;int src_r, src_c, max_step;int r_map, c_map;static const int dx[4];static const int dy[4];
private:bool one_step = false;bool paused = false;QMutex mutex;QWaitCondition pauseCond;
};#endif // DFSTHREAD_H

講講成員變量：
map用來存地圖。
visited用來標記當前走過的路徑。
src_r, src_c 就是起點坐標。
max_step 是最多走多少步。
r_map, c_map 是地圖行、列的數量。
dx，dy 用于控制方向。

嗯，后面幾個是用來控制線程的，
為了達到暫停、單步執行的效果，
用到了鎖和條件變量。

dfsthread.cpp

run dfs

void DfsThread::run()
{{QMutexLocker locker(&mutex);while (paused) {pauseCond.wait(&mutex);}}if (!map) return;if (false == dfs(src_r, src_c, 0, max_step)){emit dstNotFound();}
}

先檢查被暫停沒有，然后開始DFS。

bool DfsThread::dfs(int r, int c, int step, int max_step)
{{QMutexLocker locker(&mutex);while (paused) {pauseCond.wait(&mutex);}}

同樣，每次DFS前檢查一下被暫停沒有。

    if (step > max_step) return false;if (r < 0 || r >= r_map || c < 0 || c >= c_map) return false;if (visited[r][c]) return false;const QVector<QVector<MapSquare*>>& mapRef = *map;if (mapRef[r][c]->status() == MapSquare::STATUS_UNCHECKABLE) return false;visited[r][c] = true; // 標記為已訪問

對當前地格是否可走進行判定，
如果可走，在visited中標記。
接下來的地格將不包括：請添加圖片描述

    // 檢查是否找到目標 (不同陣營)if (mapRef[r][c]->unit_type() != MapSquare::UNIT_TYPE_EMPTY &&mapRef[r][c]->unit_type() != mapRef[src_r][src_c]->unit_type()) {// 找到目標！emit updateSquare(r, c, MapSquare::STATUS_ATTACK);mapRef[r][c]->setSrc(src_r, src_c);QThread::msleep(300);return true;  // 成功找到路徑}

如果找到目標，
發出信號將地格請添加圖片描述標記為STATUS_ATTACK ，
并開始返回。

    if(mapRef[r][c]->status() != MapSquare::STATUS_MOVE){emit updateSquare(r, c, MapSquare::STATUS_MOVE);mapRef[r][c]->setSrc(src_r, src_c);if(one_step) {pause();} else {QThread::msleep(50); // 暫停一段時間}}

如果沒找到，
發出信號將地格請添加圖片描述標記為STATUS_MOVE ，
并判斷是否是單步執行，
如果是，直接暫停線程，
如果不是，那么休眠50ms，
展現出地格是一步步被改變的，
而不是一下就dfs完了。

    for (int i = 0; i < 4; i++) {int x = dx[i] + r;int y = dy[i] + c;if (dfs(x, y, step + 1, max_step)) {// 到了這里, 說明找到了// 那么接著修改地格狀態, 并返回 trueemit updateSquare(r, c, MapSquare::STATUS_ATTACK);QThread::msleep(300);return true;}}// 恢復狀態visited[r][c] = 0;return false;
}

其他

#include "dfsthread.h"
#include <QDebug>const int DfsThread::dx[4] = {0, 0, 1, -1};
const int DfsThread::dy[4] = {1, -1, 0, 0};DfsThread::DfsThread(QWidget *parent): QThread(parent), map(nullptr)
{
}void DfsThread::init(QVector<QVector<MapSquare*>>& _map, int _r, int _c, int _max_step){map = &_map;src_r = _r;src_c = _c;max_step = _max_step;r_map = _map.size();c_map = _map[0].size();// 這里每次都得重新設置一下visited = QVector<QVector<bool>>(r_map, QVector<bool>(c_map, false));
}void DfsThread::pause(){QMutexLocker locker(&mutex);paused = true;
}void DfsThread::resume(){QMutexLocker locker(&mutex);paused = false;pauseCond.wakeAll();
}void DfsThread::oneStep(bool o){one_step = o;
}

我試了一下，
似乎不加鎖和條件變量也行，
不過為了安全還是加上吧。

Widget

UI界面史中史，設計得就是依托。

完整的可以去我的代碼倉庫看，
這里就不列出來了。

Unit

struct Unit : public QPushButton{Unit(QWidget *parent=nullptr): QPushButton(parent){}int r = -1, c = -1;int move_range = 5;MapSquare::UNIT_TYPE unit_type;
};

這個類本來單獨在一個文件里的，被我合過來了。

關于這個類，我寫了幾個函數：

void initUnit(Unit* unit, MapSquare::UNIT_TYPE unit_type);
void moveUnit(Unit* unit, int r, int c);
void connectUnit(Unit* &unit);

一個是初始化，
一個是移動，
一個是連接信號和槽(繼承自按鈕，可點擊)。

initUnit :

void Widget::initUnit(Widget::Unit *unit, MapSquare::UNIT_TYPE unit_type)
{if(unit_type == MapSquare::UNIT_TYPE_PLAYER1)unit->setIcon(Pixmaps::getInstance()->map_src);else if(unit_type == MapSquare::UNIT_TYPE_PLAYER2)unit->setIcon(Pixmaps::getInstance()->map_dst);elseqDebug() << "初始化單位為未定義類型";unit->setIconSize(QSize(80, 80));unit->setStyleSheet("border : transparent;");unit->unit_type = unit_type;
}

傳入一個Unit*，和單位類型，
就能初始化一個單位。

moveUnit

void Widget::moveUnit(Widget::Unit *unit, int r, int c)
{if(unit->r != -1 && unit->c != -1) {map[unit->r][unit->c]->setUnitType(MapSquare::UNIT_TYPE_EMPTY);map[unit->r][unit->c]->setUnit();}unit->setGeometry(map[r][c]->geometry());unit->r = r;unit->c = c;unit->raise();map[r][c]->setUnitType(unit->unit_type);map[r][c]->setUnit(unit);
}

首先得判斷是否剛初始化，
如果已經設置過坐標，
那么得先把原地格的狀態清空，
(感覺還能封裝，地格可以提供一個狀態清空函數)
然后才能移動單位，
并重新設置相關屬性。

connectUnit

void Widget::connectUnit(Widget::Unit* &unit)
{connect(unit, &QPushButton::clicked, this, [&](){qDebug() << "unit clicked ...";if(dfsThreadIsRunning()) return;MapSquare::STATUS _status = map[unit->r][unit->c]->status();if(_status == MapSquare::STATUS_EMPTY) {resetMap(); // 重置地圖dfsThread.init(map, unit->r, unit->c, unit->move_range); // 每次都要初始化dfsThread.start(); // 不能用run, 會阻塞主線程} else {resetMap(); // 重置地圖}});
}

單位被點擊，
如果當前地格狀態為空，
則開始DFS。
如果地格狀態為其他的，
暫時不做處理。

其他

connect(&dfsThread, &DfsThread::updateSquare, this, [this](int r, int c, MapSquare::STATUS status) {qDebug() << "子線程來信號了！" << status;map[r][c]->setStatus(status);
});