目录

  • - 理解屏幕坐标系
  • - 迷宫的初始绘制
  • - 随机迷宫生成的准备
  • - 使用随机队列生成迷宫
  • - 将迷宫的数据写入文件中
  • - 程序源码理解

屏幕坐标系

左上角为 (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. 从入口开始，将 1 添加入随机队列中
  2. 如果队列不为空，则执行下列操作：
  3. A. 从队列中取出1（随机的），找到与 1 相邻最近的路（这里是 2,3,4），1 可以到达 2,3，并且 2,3 都没有被访问过，所以将 2,3 加入随机队列。并将 2,3 标志为已经访问，下次不再访问。
  4. B. 打破 1->2，1->3 之间的墙。
  5. 重复第 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


推荐阅读：
相关文章