使用隨機隊列生成迷宮
目錄
- - 理解屏幕坐標系
- - 迷宮的初始繪製
- - 隨機迷宮生成的準備
- - 使用隨機隊列生成迷宮
- - 將迷宮的數據寫入文件中
- - 程序源碼理解
屏幕坐標系
左上角為 (0, 0)。
如果將第一個參數當作 x，第二個參數當作 y。那麼 x 軸以左上角為起點，水平向右；y 軸以左上角為起點，豎直向下。
下面了函數繪製一個圓形，圓心坐標為 (100, 50)，半徑為 50，顏色 Scalar(BLUE, GREEN, RED)。
circle(img, Point(100, 50), 50, Scalar(0, 200, 23));
迷宮的初始繪製
為了簡單，規定窗口大小為 `800*800`。藍色區域表示迷宮的牆，由 79 個 `10*10` 的正方形構成，四周預留 5px 的間隙。
// 繪製size*size個正方形，每個正方形為10*10像素
void MazeInit() {
int x = 5, y = 5;
for (int i = 0; i < size_; ++i) {
x = 5;
for (int j = 0; j < size_; ++j) {
Rect r(x, y, 10, 10);
rectangle(img, r, Scalar(246, 99, 38), -1);
x += 10;
}
y += 10;
}
}
隨機迷宮生成的準備
使用隨機隊列的方式生產迷宮。初始化繪製時，四周都是牆，藍色表示牆，白色表示路。為迷宮生成演算法做準備。
確定好一個入口和出口。這裡我選擇右上角和左下角。
這裡我使用的迷宮生成演算法的主要思想是：從入口的下一個節點開始，隨機的打破「上下左右」的一個正方形，迷宮地圖四周的牆不允許打破。不斷的前進，創造一條路到出口的路。
使用隨機隊列生成迷宮
迷宮的生成演算法有很多種，這裡我使用隨機隊列的方式，這應該也是最好理解的一種。
主要的演算法思想如下：
- 從入口開始，將 1 添加入隨機隊列中
- 如果隊列不為空，則執行下列操作：
- A. 從隊列中取出1（隨機的），找到與 1 相鄰最近的路（這裡是 2,3,4），1 可以到達 2,3，並且 2,3 都沒有被訪問過，所以將 2,3 加入隨機隊列。並將 2,3 標誌為已經訪問，下次不再訪問。
- B. 打破 1->2，1->3 之間的牆。
- 重複第 2 步。
看下面的這種情況，因為 2 已經打破了與 4 之間的牆，所以 4 已經被訪問了。3 雖然檢測到可以到達 4，但是因為 4 已經被 2 給訪問了，所以 34 之間的牆不能再被打破。
隨機隊列的方式應該是最簡單的方式。下面的代碼可能會有錯。
void RandomGenerateMaze() {
RQueue<point> *rqueue = new RQueue<point>(size_ * size_);
int inx = in_y_-1, iny = in_x_;
point first(inx, iny);
rqueue->Add(first);
visited_[inx][iny] = true;
while (!rqueue->IsEmpty()) {
point curr = rqueue->Remove();
for (int i = 0; i < 4; ++i) {
point new_point(curr.x + d[i][0]*2, curr.y + d[i][1]*2);
if (in_maze(new_point.x, new_point.y) &&
!visited_[new_point.x][new_point.y] &&
is_road(new_point.x, new_point.y)) {
rqueue->Add(new_point);
visited_[new_point.x][new_point.y] = true;
// 打破牆，但是不允許打破邊緣四周的牆
if (!wall_edge(curr.x + d[i][0], curr.y + d[i][1])) {
update_maze(curr.x + d[i][0], curr.y + + d[i][1]); // 打破牆
imshow("Window", img);
waitKey(1);
}
}
}
}
}
將迷宮的數據寫入文件中
將生成的迷宮數據寫入文件中，然後可以直接讀取文件，直接進行迷宮的繪製。然後就可以編寫不同的演算法走迷宮了。
因為迷宮的生成演算法將 maze[][] 數組已經設置好了，只需將 maze[][] 數組進行遍歷，根據 true or false 確定迷宮的路和牆。
// 迷宮信息寫入文件
// 『 』：空格代表路
// 『#』：#號代表牆
void WriteMazeDataToFile(std::string filename) {
ofstream file(filename);
assert(file.is_open());
printf("Write to %s ...
", filename.c_str());
for (int i = 0; i < size_; ++i) {
for (int j = 0; j < size_; ++j) {
if (maze_[i][j]) {
file << " "; // 路
} else {
file << "#"; // 牆
}
}
file << std::endl;
}
file.close();
printf("Maze information is written completed!
");
}
至此，迷宮的數據算是準備好了。
編寫一個讀取文件的函數，根據文件的內容進行迷宮的繪製。然後就可以編寫 DFS/BFS 走迷宮了。走迷宮演算法同樣也是很多的。如果能實現 A* 演算法，那就太贊了。
演算法源碼
- web: GitHub
- username: donngdev
- repository: Sorting-Visualization/maze
推薦閱讀：
