迷宫算法 之 迷宫生成和迷宫寻路
本文讲解迷宫生成和迷宫寻路算法。
////////////////////////////////////////////////////////////////////////////////////////////////////
一、三种迷宫生成算法
1、 DFS(即深度优先)算法生成,分为递归和非递归方法。
2、 十字分割算法生成,分为递归和非递归方法。
3、 随机 Prim 算法生成,一种非递归方法。
二、两种迷宫寻路算法
1、DFS 寻路,采用非递归实现。
2、A* 寻路,一种非递归方法。
////////////////////////////////////////////////////////////////////////////////////////////////////
进入讲解之前先给出一些说明
1、笔者所用语言:C++(包括部分 C++11 特性)。
2、笔者环境:Win10 + VS2019。
3、迷宫生成后的界面由 EasyX 绘图库生成。
4、以 EasyX 制作的迷宫算法可视化程序,如有需要请移步:https://codebus.cn/teternity/post/MazeAlgorithm
5、迷宫统一要求:长宽均为奇数(且本文默认长宽均为 N)、最外围一圈是墙、入口坐标(0, 1)、出口坐标(N-1, N-2)。
6、本文由笔者原创,不涉及版权争议,仅用作学习。
7、阅读代码前,你至少需要熟练的掌握 栈和队列 等数据结构,以及一些 STL 容器,这会在后文提及。
////////////////////////////////////////////////////////////////////////////////////////////////////
// 接下来进入正文
////////////////////////////////////////////////////////////////////////////////////////////////////
一、三种迷宫生成算法(最外围是墙或入口,因此操作范围是:(1, 1) 到 (N-2, N-2) )
1、 DFS 算法生成(是一种挖墙算法)
a、初始时全是墙(N是奇数)
b、x,y 均在 1~N-2 中的奇数随机选取一点(即该点坐标均为奇数),将其挖开,并将该点入栈
c、四个方向随机选取一个方向,设当前挖开坐标为 (x, y),
若该方向上满足 (x + dx*2, y + dy*2) 是墙(dx 和 dy 代表方向,取值为 1 或 -1),则挖开 (x + dx, y + dy),并重设当前点为 (x + dx*2, y + dy*2),将当前点入栈
d、以 Cur 为当前点,重复操作步骤 b
e、若 Cur 不能挖开周围的墙,则栈执行 pop 操作,并将 Cur 重置为此时栈中的 top 元素
f、直到栈为空,说明挖墙操作结束
至此,DFS 挖墙算法讲解结束。回看这个过程,像是一只地鼠打洞一般,其中有几个约束,为了能够连通起点到终点,需要使得挖墙点为奇数,且不能造成当前通道与另一通道挖穿
看看该算法下生成的迷宫形态吧(由 EasyX 库绘制):
源码(包含迭代和非迭代版本算法。另:注释 EasyX 的地方是用 EasyX 绘图,如果不会 EasyX 请删除相关代码):
#include <iostream> #include <ctime> #include <stack> #include <vector> #include <algorithm> #include <easyx.h> using namespace std; // 迷宫格子状态 enum CellState:int { PATH = 0, WALL, FLAG }; // 迷宫格二维点结构 struct Point2 { int x, y; Point2(int _x, int _y) :x(_x), y(_y) {} }; // 迷宫大小(要求为奇数) const int mazeSize = 21; // 迷宫生成接口--递归版 void DFS_generator(int _x, int _y, std::vector<std::vector<int>>& maze) { // 定义方向容器 std::vector<std::vector<int>> dir{ {1,0},{-1,0},{0,1},{0,-1} }; // 随机打乱方向 std::random_shuffle(dir.begin(), dir.end()); // 递归生成迷宫 maze[_x][_y] = PATH; for (int i = 0; i < 4; ++i) { if (_x + 2 * dir[i][0] >= 1 && _x + 2 * dir[i][0] <= mazeSize - 2 && _y + 2 * dir[i][1] >= 1 && _y + 2 * dir[i][1] <= mazeSize - 2 && maze[_x + 2 * dir[i][0]][_y + 2 * dir[i][1]] == WALL) { maze[_x + dir[i][0]][_y + dir[i][1]] = PATH; DFS_generator(_x + 2 * dir[i][0], _y + 2 * dir[i][1], maze); } } } // 迷宫生成接口--迭代版 void DFS_iterative_generator(std::vector<std::vector<int>>& maze) { // 定义栈容器 std::stack<Point2> sp; // 定义方向容器 std::vector<std::vector<int>> dir{ {1,0},{-1,0},{0,1},{0,-1} }; // 要求参数为奇数 Point2 temp((rand() % (mazeSize - 2) + 1) | 1, (rand() % (mazeSize - 2) + 1) | 1); sp.push(temp); // 后续迭代生成迷宫,并绘制 while (!sp.empty()) { if (maze[temp.x][temp.y] != PATH) maze[temp.x][temp.y] = PATH; // 随机打乱方向 std::random_shuffle(dir.begin(), dir.end()); int i = 0; for (; i < 4; ++i) { if (temp.x + 2 * dir[i][0] >= 1 && temp.x + 2 * dir[i][0] <= mazeSize - 2 && temp.y + 2 * dir[i][1] >= 1 && temp.y + 2 * dir[i][1] <= mazeSize - 2 && maze[temp.x + 2 * dir[i][0]][temp.y + 2 * dir[i][1]] == WALL) { maze[temp.x + dir[i][0]][temp.y + dir[i][1]] = PATH; temp.x += 2 * dir[i][0]; temp.y += 2 * dir[i][1]; sp.push(temp); break; } } if (i == 4) sp.pop(); if (!sp.empty()) temp = sp.top(); } } // main 函数 int main() { srand((unsigned)time(nullptr)); // 入口出口 Point2 start(0, 1); Point2 end(mazeSize - 1, mazeSize - 2); // 二维迷宫容器 std::vector<std::vector<int>> maze; // 初始化迷宫 for (int i = 0; i < mazeSize; ++i) maze.push_back(std::vector<int>()); for (int i = 0; i < mazeSize; ++i) for (int j = 0; j < mazeSize; ++j) maze[i].push_back(WALL); maze[start.x][start.y] = maze[end.x][end.y] = PATH; // 生成迷宫(迭代和非迭代二选一生成) DFS_generator((rand() % (mazeSize - 2) + 1) | 1, (rand() % (mazeSize - 2) + 1) | 1, maze); // DFS_iterative_generator(maze); // 打印迷宫 for (int j = 0; j < mazeSize; ++j) { for (int i = 0; i < mazeSize; ++i) cout << maze[i][j] << " "; cout << endl; } // EasyX { auto ret = _getwch(); const int width = 15; initgraph(mazeSize * width, mazeSize * width); setlinecolor(DARKGRAY); setfillcolor(LIGHTGRAY); for (int j = 0; j < mazeSize; ++j) for (int i = 0; i < mazeSize; ++i) if (maze[i][j] == WALL) fillrectangle(i * width, j * width, i * width + width - 1, j * width + width - 1); // saveimage(_T("D:\\maze.png")); ret = _getwch(); closegraph(); } return 0; }
2、 十字分割算法生成(是一种十字补墙算法)
a、初始时除了四周全是通路(N是奇数)
b、x,y 均在 1~N-2 中的偶数随机选取一点(即该点坐标均为偶数),然后十字建墙
c、在建好的四面墙(不包含选取点)中随机选择三面,找奇数点开洞,使得四个子空间连通
d、对四个子空间重复操作,直到子空间不可分割为止(淡黄色是开洞位置)(何时不可分割?长度 或 宽度 不大于 1 时)
至此,十字分割补墙算法讲解结束。请注意,在选取建墙点时要求是偶数,挖墙时要求是奇数
看看该算法下生成的迷宫形态吧(由 EasyX 库绘制):
源码(包含迭代和非迭代版本算法。另:注释 EasyX 的地方是用 EasyX 绘图,如果不会 EasyX 请删除相关代码):
#include <iostream> #include <ctime> #include <stack> #include <vector> #include <algorithm> #include <easyx.h> using namespace std; // 迷宫格子状态 enum CellState:int { PATH = 0, WALL, FLAG }; // 迷宫格二维点结构 struct Point2 { int x, y; Point2(int _x, int _y) :x(_x), y(_y) {} }; // 四维点,用于分割矩形区间 struct Point4 { int x1, x2; int y1, y2; Point4(int _x1, int _x2, int _y1, int _y2) :x1(_x1), x2(_x2), y1(_y1), y2(_y2) {} }; // 迷宫大小(要求为奇数) const int mazeSize = 21; // 迷宫生成接口--递归版 void Division_generator(int _l, int _r, int _t, int _b, std::vector<std::vector<int>>& maze) { // 间隔大于 1 时可分割 if (_r - _l > 1 && _b - _t > 1) { int i = 0; // 要求分割点 px,py 为偶数 int px = ((rand() % (_r - _l) + _l + 1) | 1) - 1; int py = ((rand() % (_b - _t) + _t + 1) | 1) - 1; while (px + i <= _r || px - i >= _l || py + i <= _b || py - i >= _t) { if (px + i <= _r) maze[px + i][py] = WALL; if (px - i >= _l) maze[px - i][py] = WALL; if (py + i <= _b) maze[px][py + i] = WALL; if (py - i >= _t) maze[px][py - i] = WALL; ++i; } // 定义方向容器,随机在三面墙上开洞 // 要求开洞位置是奇数 std::vector<int> dir{ 0,1,2,3 }; std::random_shuffle(dir.begin(), dir.end()); for (int i = 0; i < 3; ++i) { if (dir[i] == 0) { int xx = (rand() % (px - _l) + _l) | 1; maze[xx][py] = PATH; } else if (dir[i] == 1) { int xx = (rand() % (_r - px) + px) | 1; maze[xx][py] = PATH; } else if (dir[i] == 2) { int yy = (rand() % (py - _t) + _t) | 1; maze[px][yy] = PATH; } else if (dir[i] == 3) { int yy = (rand() % (_b - py) + py) | 1; maze[px][yy] = PATH; } } // 递归分割 Division_generator(_l, px - 1, _t, py - 1, maze); Division_generator(px + 1, _r, _t, py - 1, maze); Division_generator(_l, px - 1, py + 1, _b, maze); Division_generator(px + 1, _r, py + 1, _b, maze); } } // 迷宫生成接口--迭代版 void Division_iterative_generator(std::vector<std::vector<int>>& maze) { // 定义栈容器 std::stack<Point4> sp; // 定义方向容器 std::vector<int> dir{ 0,1,2,3 }; // 要求参数为奇数 Point4 temp(1, mazeSize - 2, 1, mazeSize - 2); sp.push(temp); // 后续迭代生成迷宫 while (!sp.empty()) { sp.pop(); if (temp.x2 - temp.x1 > 1 && temp.y2 - temp.y1 > 1) { int i = 0; int px = ((rand() % (temp.x2 - temp.x1) + temp.x1 + 1) | 1) - 1; int py = ((rand() % (temp.y2 - temp.y1) + temp.y1 + 1) | 1) - 1; while (px + i <= temp.x2 || px - i >= temp.x1 || py + i <= temp.y2 || py - i >= temp.y1) { if (px + i <= temp.x2) maze[px + i][py] = WALL; if (px - i >= temp.x1) maze[px - i][py] = WALL; if (py + i <= temp.y2) maze[px][py + i] = WALL; if (py - i >= temp.y1) maze[px][py - i] = WALL; ++i; } // 随机在三面墙上开洞,要求开洞位置是奇数 std::random_shuffle(dir.begin(), dir.end()); for (int i = 0; i < 3; ++i) { if (dir[i] == 0) { int xx = (rand() % (px - temp.x1) + temp.x1) | 1; maze[xx][py] = PATH; } else if (dir[i] == 1) { int xx = (rand() % (temp.x2 - px) + px) | 1; maze[xx][py] = PATH; } else if (dir[i] == 2) { int yy = (rand() % (py - temp.y1) + temp.y1) | 1; maze[px][yy] = PATH; } else if (dir[i] == 3) { int yy = (rand() % (temp.y2 - py) + py) | 1; maze[px][yy] = PATH; } } // 将三个方块区间入栈 sp.push(Point4(px + 1, temp.x2, py + 1, temp.y2)); sp.push(Point4(temp.x1, px - 1, py + 1, temp.y2)); sp.push(Point4(px + 1, temp.x2, temp.y1, py - 1)); temp.x2 = px - 1; temp.y2 = py - 1; sp.push(temp); } else if (!sp.empty()) { temp = sp.top(); } } } // main 函数 int main() { srand((unsigned)time(nullptr)); // 入口出口 Point2 start(0, 1); Point2 end(mazeSize - 1, mazeSize - 2); // 二维迷宫容器 std::vector<std::vector<int>> maze; // 初始化迷宫 for (int i = 0; i < mazeSize; ++i) maze.push_back(std::vector<int>()); for (int i = 0; i < mazeSize; ++i) for (int j = 0; j < mazeSize; ++j) (i == 0 || j == 0 || i == mazeSize - 1 || j == mazeSize - 1) ? maze[i].push_back(WALL) : maze[i].push_back(PATH); maze[start.x][start.y] = maze[end.x][end.y] = PATH; // 生成迷宫(迭代和非迭代二选一生成) Division_generator(1, mazeSize - 2, 1, mazeSize - 2, maze); // Division_iterative_generator(maze); // 打印迷宫 for (int j = 0; j < mazeSize; ++j) { for (int i = 0; i < mazeSize; ++i) cout << maze[i][j] << " "; cout << endl; } // EasyX { auto ret = _getwch(); const int width = 15; initgraph(mazeSize * width, mazeSize * width); setlinecolor(DARKGRAY); setfillcolor(LIGHTGRAY); for (int j = 0; j < mazeSize; ++j) for (int i = 0; i < mazeSize; ++i) if (maze[i][j] == WALL) fillrectangle(i * width, j * width, i * width + width - 1, j * width + width - 1); // saveimage(_T("D:\\maze.png")); ret = _getwch(); closegraph(); } return 0; }
3、 随机 Prim 算法生成,一种非递归方法
a、初始时全是墙(N是奇数)
b、构建一墙一通路形式
c、随机选择一个通路,并将周围墙入容器,标记该通路
d、在墙容器中随机选取一堵墙,如果墙两边的通路没有同时被标记,则打通该墙,并将原来未被标记的通路周围的墙加入容器,然后将该通路标记,最后移除该墙
e、重复操作 d,直到墙容器为空,说明该算法完成,最后将被标记的通路清除标记
至此,随机 Prim 挖墙算法讲解结束
看看该算法下生成的迷宫形态吧(由 EasyX 库绘制):
源码(注:注释 EasyX 的地方是用 EasyX 绘图,如果不会 EasyX 请删除相关代码):
#include <iostream> #include <ctime> #include <stack> #include <vector> #include <algorithm> #include <easyx.h> using namespace std; // 迷宫格子状态 enum CellState:int { PATH = 0, WALL, FLAG }; // 迷宫格二维点结构 struct Point2 { int x, y; Point2(int _x, int _y) :x(_x), y(_y) {} }; // 迷宫大小(要求为奇数) const int mazeSize = 21; // 迷宫生成接口 void Prim_generator(std::vector<std::vector<int>>& maze) { // 构建墙隔开通路的迷宫,奇数点为通路 for (int i = 1; i <= mazeSize - 2; i += 2) for (int j = 1; j <= mazeSize - 2; j += 2) maze[i][j] = PATH; // 维护一个墙容器 std::vector<Point2> vp; // 先随机找一个通路 Point2 temp((rand() % (mazeSize - 2) + 1) | 1, (rand() % (mazeSize - 2) + 1) | 1); // 将周围墙入栈 if (temp.x - 1 >= 2) vp.push_back(Point2(temp.x - 1, temp.y)); if (temp.x + 1 <= mazeSize - 3) vp.push_back(Point2(temp.x + 1, temp.y)); if (temp.y - 1 >= 2) vp.push_back(Point2(temp.x, temp.y - 1)); if (temp.y + 1 <= mazeSize - 3) vp.push_back(Point2(temp.x, temp.y + 1)); // 标记该通路 maze[temp.x][temp.y] = FLAG; int pos = 0; // 后续迭代生成迷宫 while (!vp.empty()) { // 在墙容器中随机选取一堵墙 pos = rand() % vp.size(); temp = vp[pos]; // 记录该墙是否打通 bool flag = false; // 后续 if else 判断墙所隔离通路在左右还是上下,并判断是否打通 if (maze[temp.x + 1][temp.y] == WALL) { if (maze[temp.x][temp.y - 1] != maze[temp.x][temp.y + 1]) { maze[temp.x][temp.y] = PATH; // 对新加入的通路进行标记 if (maze[temp.x][temp.y - 1] == FLAG) { maze[temp.x][temp.y + 1] = FLAG; ++temp.y; } else { maze[temp.x][temp.y - 1] = FLAG; --temp.y; } flag = true; } } else { if (maze[temp.x - 1][temp.y] != maze[temp.x + 1][temp.y]) { maze[temp.x][temp.y] = PATH; // 对新加入的通路进行标记 if (maze[temp.x - 1][temp.y] == FLAG) { maze[temp.x + 1][temp.y] = FLAG; ++temp.x; } else { maze[temp.x - 1][temp.y] = FLAG; --temp.x; } flag = true; } } // 如果打通了墙,将进加入的通路周围的墙入容器 if (flag) { if (temp.x - 1 >= 2 && maze[temp.x - 1][temp.y] == WALL) vp.push_back(Point2(temp.x - 1, temp.y)); if (temp.x + 1 <= mazeSize - 3 && maze[temp.x + 1][temp.y] == WALL) vp.push_back(Point2(temp.x + 1, temp.y)); if (temp.y - 1 >= 2 && maze[temp.x][temp.y - 1] == WALL) vp.push_back(Point2(temp.x, temp.y - 1)); if (temp.y + 1 <= mazeSize - 3 && maze[temp.x][temp.y + 1] == WALL) vp.push_back(Point2(temp.x, temp.y + 1)); } // 移除该墙 vp[pos] = *(vp.end() - 1); vp.pop_back(); } // 将被标记的通路还原 for (auto& v1 : maze) for (auto& v2 : v1) if (v2 == FLAG) v2 = PATH; } // main 函数 int main() { srand((unsigned)time(nullptr)); // 入口出口 Point2 start(0, 1); Point2 end(mazeSize - 1, mazeSize - 2); // 二维迷宫容器 std::vector<std::vector<int>> maze; // 初始化迷宫 for (int i = 0; i < mazeSize; ++i) maze.push_back(std::vector<int>()); for (int i = 0; i < mazeSize; ++i) for (int j = 0; j < mazeSize; ++j) maze[i].push_back(WALL); maze[start.x][start.y] = maze[end.x][end.y] = PATH; // 生成迷宫 Prim_generator(maze); // 打印迷宫 for (int j = 0; j < mazeSize; ++j) { for (int i = 0; i < mazeSize; ++i) cout << maze[i][j] << " "; cout << endl; } // EasyX { auto ret = _getwch(); const int width = 15; initgraph(mazeSize * width, mazeSize * width); setlinecolor(DARKGRAY); setfillcolor(LIGHTGRAY); for (int j = 0; j < mazeSize; ++j) for (int i = 0; i < mazeSize; ++i) if (maze[i][j] == WALL) fillrectangle(i * width, j * width, i * width + width - 1, j * width + width - 1); // saveimage(_T("D:\\maze.png")); ret = _getwch(); closegraph(); } return 0; }
////////////////////////////////////////////////////////////////////////////////////////////////////
// 至此,以上三种迷宫生成算法讲解完成。这三种方式生成的迷宫形态有较大差异,需针对不同的游戏进行适当的选择,另外,对于不同的场景应灵活应用。
////////////////////////////////////////////////////////////////////////////////////////////////////
二、两种迷宫寻路算法(后文的迷宫默认使用前文中 随机 Prim 算法 所生成的迷宫)
1、DFS 寻路,采用非递归实现
该寻路方法,应该算是入门级算法了,学习数据结构栈时一般就会接触该算法。
从起点开始,将当前点入栈,向某一方向前进。若周围方向均不能继续前进,则回退,直到找到终点或栈为空。
看看 随机Prin生成 并在该算法下寻路后的迷宫形态吧(由 EasyX 库绘制):
源码(该代码中使用 std::list 实现栈并在寻路后返回 std::list。另:注释 EasyX 的地方是用 EasyX 绘图,如果不会 EasyX 请删除相关代码):
#include <iostream> #include <ctime> #include <list> #include <stack> #include <vector> #include <algorithm> #include <easyx.h> using namespace std; // 迷宫格子状态 enum CellState:int { PATH = 0, WALL, FLAG }; // 迷宫格二维点结构 struct Point2 { int x, y; Point2(int _x, int _y) :x(_x), y(_y) {} bool operator == (const Point2& p2) { return x == p2.x && y == p2.y; } }; // 迷宫大小(要求为奇数) const int mazeSize = 21; // 迷宫生成接口 void Prim_generator(std::vector<std::vector<int>>& maze) { // 构建墙隔开通路的迷宫,奇数点为通路 for (int i = 1; i <= mazeSize - 2; i += 2) for (int j = 1; j <= mazeSize - 2; j += 2) maze[i][j] = PATH; // 维护一个墙容器 std::vector<Point2> vp; // 先随机找一个通路 Point2 temp((rand() % (mazeSize - 2) + 1) | 1, (rand() % (mazeSize - 2) + 1) | 1); // 将周围墙入栈 if (temp.x - 1 >= 2) vp.push_back(Point2(temp.x - 1, temp.y)); if (temp.x + 1 <= mazeSize - 3) vp.push_back(Point2(temp.x + 1, temp.y)); if (temp.y - 1 >= 2) vp.push_back(Point2(temp.x, temp.y - 1)); if (temp.y + 1 <= mazeSize - 3) vp.push_back(Point2(temp.x, temp.y + 1)); // 标记该通路 maze[temp.x][temp.y] = FLAG; int pos = 0; // 后续迭代生成迷宫 while (!vp.empty()) { // 在墙容器中随机选取一堵墙 pos = rand() % vp.size(); temp = vp[pos]; // 记录该墙是否打通 bool flag = false; // 后续 if else 判断墙所隔离通路在左右还是上下,并判断是否打通 if (maze[temp.x + 1][temp.y] == WALL) { if (maze[temp.x][temp.y - 1] != maze[temp.x][temp.y + 1]) { maze[temp.x][temp.y] = PATH; // 对新加入的通路进行标记 if (maze[temp.x][temp.y - 1] == FLAG) { maze[temp.x][temp.y + 1] = FLAG; ++temp.y; } else { maze[temp.x][temp.y - 1] = FLAG; --temp.y; } flag = true; } } else { if (maze[temp.x - 1][temp.y] != maze[temp.x + 1][temp.y]) { maze[temp.x][temp.y] = PATH; // 对新加入的通路进行标记 if (maze[temp.x - 1][temp.y] == FLAG) { maze[temp.x + 1][temp.y] = FLAG; ++temp.x; } else { maze[temp.x - 1][temp.y] = FLAG; --temp.x; } flag = true; } } // 如果打通了墙,将进加入的通路周围的墙入容器 if (flag) { if (temp.x - 1 >= 2 && maze[temp.x - 1][temp.y] == WALL) vp.push_back(Point2(temp.x - 1, temp.y)); if (temp.x + 1 <= mazeSize - 3 && maze[temp.x + 1][temp.y] == WALL) vp.push_back(Point2(temp.x + 1, temp.y)); if (temp.y - 1 >= 2 && maze[temp.x][temp.y - 1] == WALL) vp.push_back(Point2(temp.x, temp.y - 1)); if (temp.y + 1 <= mazeSize - 3 && maze[temp.x][temp.y + 1] == WALL) vp.push_back(Point2(temp.x, temp.y + 1)); } // 移除该墙 vp[pos] = *(vp.end() - 1); vp.pop_back(); } // 将被标记的通路还原 for (auto& v1 : maze) for (auto& v2 : v1) if (v2 == FLAG) v2 = PATH; } // DFS 寻路 std::list<Point2> DFS_find(const Point2& start, const Point2& end, std::vector<std::vector<int>>& maze) { // 定义方向容器(右、下、左、上) std::vector<std::vector<int>> dir{ {1,0},{0,1},{-1,0},{0,-1} }; // 定义栈容器 std::list<Point2> sp; Point2 temp = start; sp.push_back(temp); // 与生成算法相似,迭代 DFS 遍历 while (!sp.empty()) { int i = 0; // 若可向其他方向前进,则继续 for (; i < 4; ++i) { if (temp.x + dir[i][0] >= 0 && temp.x + dir[i][0] <= mazeSize - 1 && temp.y + dir[i][1] >= 0 && temp.y + dir[i][1] <= mazeSize - 1 && maze[temp.x + dir[i][0]][temp.y + dir[i][1]] == PATH) { // 对走过的路进行标记 maze[temp.x][temp.y] = FLAG; temp.x += dir[i][0]; temp.y += dir[i][1]; sp.push_back(temp); if (temp == end) return sp; break; } } // 无路可走时回溯 if (i == 4) { maze[temp.x][temp.y] = FLAG; sp.pop_back(); if (!sp.empty()) temp = sp.back(); } } // 将被标记的通路还原 for (auto& v1 : maze) for (auto& v2 : v1) if (v2 == FLAG) v2 = PATH; return sp; } // main 函数 int main() { srand((unsigned)time(nullptr)); // 入口出口 Point2 start(0, 1); Point2 end(mazeSize - 1, mazeSize - 2); // 二维迷宫容器 std::vector<std::vector<int>> maze; // 初始化迷宫 for (int i = 0; i < mazeSize; ++i) maze.push_back(std::vector<int>()); for (int i = 0; i < mazeSize; ++i) for (int j = 0; j < mazeSize; ++j) maze[i].push_back(WALL); maze[start.x][start.y] = maze[end.x][end.y] = PATH; // 生成迷宫 Prim_generator(maze); // 打印迷宫 for (int j = 0; j < mazeSize; ++j) { for (int i = 0; i < mazeSize; ++i) cout << maze[i][j] << " "; cout << endl; } // 寻路 auto sp = DFS_find(start, end, maze); // 打印路径 cout << endl << "寻路路径:" << endl; int i = 0; for (auto p2 : sp) { if (i++ == 5) { i = 0; cout << "(" << p2.x << ", " << p2.y << ")" << endl; continue; } cout << "(" << p2.x << ", " << p2.y << ")" << "、"; } cout << endl; // EasyX { auto ret = _getwch(); const int width = 15; initgraph(mazeSize * width, mazeSize * width); setlinecolor(DARKGRAY); setfillcolor(LIGHTGRAY); for (int j = 0; j < mazeSize; ++j) for (int i = 0; i < mazeSize; ++i) if (maze[i][j] == WALL) fillrectangle(i * width, j * width, i * width + width - 1, j * width + width - 1); setfillcolor(YELLOW); for (auto p2 : sp) fillrectangle(p2.x * width, p2.y * width, p2.x * width + width - 1, p2.y * width + width - 1); // saveimage(_T("D:\\maze.png")); ret = _getwch(); closegraph(); } return 0; }
2、A* 寻路,一种非递归方法
讲解 A* 寻路算法的文章很多,笔者就不再重复造*了
这里推荐程序员小灰的文章:https://mp.weixin.qq.com/s/FYKR_1yBKR4GJTn0fFIuAA
一些说明:
1、用 F 值评估最短路径,公式 F = G + H
2、G 代表从起点走到当前点的步数,在代码中等于 父节点 的 G 值加 1
3、H 值是当前点到终点距离的评估,可简单认为是无阻碍时到终点所需的步数 |dx| + |dy|
4、openList 和 closeList 应该如何选用容器?
closeList:只需要将节点加入而不需要其他操作,因此可以使用 vector,list 等容器
openList:由于需要从该容器中取出 F 值最小的节点,因此可以考虑使用能够自排序的容器,如 priority_queue,multiset 等
本文使用 list 及 multiset 来实现,且从终点向起点寻路,最终返回一个包含寻路路径的 list 容器
看看 随机Prin生成 并在该算法下寻路后的迷宫形态吧(由 EasyX 库绘制):
源码(注:注释 EasyX 的地方是用 EasyX 绘图,如果不会 EasyX 请删除相关代码):
#include <iostream> #include <ctime> #include <set> #include <list> #include <stack> #include <vector> #include <algorithm> #include <easyx.h> using namespace std; // 迷宫格子状态 enum CellState:int { PATH = 0, WALL, FLAG }; // 迷宫格二维点结构 struct Point2 { int x, y; Point2(int _x, int _y) :x(_x), y(_y) {} bool operator == (const Point2& p2) const { return x == p2.x && y == p2.y; } }; // 迷宫大小(要求为奇数) const int mazeSize = 21; // 迷宫生成接口 void Prim_generator(std::vector<std::vector<int>>& maze) { // 构建墙隔开通路的迷宫,奇数点为通路 for (int i = 1; i <= mazeSize - 2; i += 2) for (int j = 1; j <= mazeSize - 2; j += 2) maze[i][j] = PATH; // 维护一个墙容器 std::vector<Point2> vp; // 先随机找一个通路 Point2 temp((rand() % (mazeSize - 2) + 1) | 1, (rand() % (mazeSize - 2) + 1) | 1); // 将周围墙入栈 if (temp.x - 1 >= 2) vp.push_back(Point2(temp.x - 1, temp.y)); if (temp.x + 1 <= mazeSize - 3) vp.push_back(Point2(temp.x + 1, temp.y)); if (temp.y - 1 >= 2) vp.push_back(Point2(temp.x, temp.y - 1)); if (temp.y + 1 <= mazeSize - 3) vp.push_back(Point2(temp.x, temp.y + 1)); // 标记该通路 maze[temp.x][temp.y] = FLAG; int pos = 0; // 后续迭代生成迷宫 while (!vp.empty()) { // 在墙容器中随机选取一堵墙 pos = rand() % vp.size(); temp = vp[pos]; // 记录该墙是否打通 bool flag = false; // 后续 if else 判断墙所隔离通路在左右还是上下,并判断是否打通 if (maze[temp.x + 1][temp.y] == WALL) { if (maze[temp.x][temp.y - 1] != maze[temp.x][temp.y + 1]) { maze[temp.x][temp.y] = PATH; // 对新加入的通路进行标记 if (maze[temp.x][temp.y - 1] == FLAG) { maze[temp.x][temp.y + 1] = FLAG; ++temp.y; } else { maze[temp.x][temp.y - 1] = FLAG; --temp.y; } flag = true; } } else { if (maze[temp.x - 1][temp.y] != maze[temp.x + 1][temp.y]) { maze[temp.x][temp.y] = PATH; // 对新加入的通路进行标记 if (maze[temp.x - 1][temp.y] == FLAG) { maze[temp.x + 1][temp.y] = FLAG; ++temp.x; } else { maze[temp.x - 1][temp.y] = FLAG; --temp.x; } flag = true; } } // 如果打通了墙,将进加入的通路周围的墙入容器 if (flag) { if (temp.x - 1 >= 2 && maze[temp.x - 1][temp.y] == WALL) vp.push_back(Point2(temp.x - 1, temp.y)); if (temp.x + 1 <= mazeSize - 3 && maze[temp.x + 1][temp.y] == WALL) vp.push_back(Point2(temp.x + 1, temp.y)); if (temp.y - 1 >= 2 && maze[temp.x][temp.y - 1] == WALL) vp.push_back(Point2(temp.x, temp.y - 1)); if (temp.y + 1 <= mazeSize - 3 && maze[temp.x][temp.y + 1] == WALL) vp.push_back(Point2(temp.x, temp.y + 1)); } // 移除该墙 vp[pos] = *(vp.end() - 1); vp.pop_back(); } // 将被标记的通路还原 for (auto& v1 : maze) for (auto& v2 : v1) if (v2 == FLAG) v2 = PATH; } // A*寻路容器 class A_Container { struct Node { Point2 p2; int gVal, hVal, fVal; Node* parent; Node(const Point2& _p2, int _g, int _h, Node* _p) :p2(_p2), gVal(_g), hVal(_h), fVal(_g + _h), parent(_p) {} }; public: A_Container(const Point2& _start) :destPos(_start) {} ~A_Container() { for (auto& no : openList) delete no; for (auto& no : closeList) delete no; } // 将节点加入 openList void pushOpenList(const Point2& _p2) { int gVal = 0; Node* par = nullptr; if (!closeList.empty()) { par = *(--closeList.end()); gVal = par->gVal + 1; } Node* temp = new Node(_p2, gVal, abs(_p2.x - destPos.x) + abs(_p2.y - destPos.y), par); if (_p2.x == destPos.x && _p2.y == destPos.y) p_destNode = temp; openList.insert(temp); temp = nullptr; } // 从 openList 中取出 fVal 值最小的节点加入 closeList auto getMinNode() { auto it = openList.begin(); Point2 ret = (*it)->p2; closeList.push_back(*it); openList.erase(it); return ret; } // 获取寻路终点,用于回溯得到最短路径 Node* getDestNode() { return p_destNode; } // 用于 multiset 比较 的函数对象 struct Compare { bool operator ()(const Node* _n1, const Node* _n2) const { return _n1->fVal < _n2->fVal; } }; private: Point2 destPos; // 目标位置 std::list<Node*> closeList; // closeList 容器 std::multiset<Node*, Compare> openList; // openList 自动排序 Node* p_destNode = nullptr; // 用于返回终点的位置指针 }; // A* 寻路 list<Point2> A_find(const Point2& start, const Point2& end, std::vector<std::vector<int>>& maze) { // 从目标位置开始寻找起点,之后回溯即可得到起点到终点的路径 Point2 temp = end; // 创建高效容器 A_Container cont(start); // 将目标位置加入 openList cont.pushOpenList(temp); // 后续迭代进行,根据 A* 寻路规则,利用高效容器寻找最短路径 while (true) { // 将 openList 中 F 值最小的节点放到 closeList 中 temp = cont.getMinNode(); // 标记节点加入到 openList 中的节点 maze[temp.x][temp.y] = FLAG; // 后续 if 将周围通路加入 openList if (temp.x - 1 >= 0 && maze[temp.x - 1][temp.y] == PATH) { maze[temp.x - 1][temp.y] = FLAG; cont.pushOpenList(Point2(temp.x - 1, temp.y)); if (start == Point2(temp.x - 1, temp.y)) break; } if (temp.y - 1 >= 0 && maze[temp.x][temp.y - 1] == PATH) { maze[temp.x][temp.y - 1] = FLAG; cont.pushOpenList(Point2(temp.x, temp.y - 1)); if (start == Point2(temp.x, temp.y - 1)) break; } if (temp.x + 1 <= mazeSize - 1 && maze[temp.x + 1][temp.y] == PATH) { maze[temp.x + 1][temp.y] = FLAG; cont.pushOpenList(Point2(temp.x + 1, temp.y)); if (start == Point2(temp.x + 1, temp.y)) break; } if (temp.y + 1 <= mazeSize - 1 && maze[temp.x][temp.y + 1] == PATH) { maze[temp.x][temp.y + 1] = FLAG; cont.pushOpenList(Point2(temp.x, temp.y + 1)); if (start == Point2(temp.x, temp.y + 1)) break; } } // 将被标记的通路还原 for (auto& v1 : maze) for (auto& v2 : v1) if (v2 == FLAG) v2 = PATH; // 找到起点后,获取高效容器中的起点,回溯得到最短路径 auto st = cont.getDestNode(); list<Point2> retList; while (st != nullptr) { retList.push_back({ st->p2 }); st = st->parent; } return retList; } // main 函数 int main() { srand((unsigned)time(nullptr)); // 入口出口 Point2 start(0, 1); Point2 end(mazeSize - 1, mazeSize - 2); // 二维迷宫容器 std::vector<std::vector<int>> maze; // 初始化迷宫 for (int i = 0; i < mazeSize; ++i) maze.push_back(std::vector<int>()); for (int i = 0; i < mazeSize; ++i) for (int j = 0; j < mazeSize; ++j) maze[i].push_back(WALL); maze[start.x][start.y] = maze[end.x][end.y] = PATH; // 生成迷宫 Prim_generator(maze); // 打印迷宫 for (int j = 0; j < mazeSize; ++j) { for (int i = 0; i < mazeSize; ++i) cout << maze[i][j] << " "; cout << endl; } // 寻路 auto sp = A_find(end, start, maze); // 打印路径 cout << endl << "寻路路径:" << endl; int i = 0; for (auto p2 : sp) { if (i++ == 5) { i = 0; cout << "(" << p2.x << ", " << p2.y << ")" << endl; continue; } cout << "(" << p2.x << ", " << p2.y << ")" << "、"; } cout << endl; // EasyX { auto ret = _getwch(); const int width = 15; initgraph(mazeSize * width, mazeSize * width); setlinecolor(DARKGRAY); setfillcolor(LIGHTGRAY); for (int j = 0; j < mazeSize; ++j) for (int i = 0; i < mazeSize; ++i) if (maze[i][j] == WALL) fillrectangle(i * width, j * width, i * width + width - 1, j * width + width - 1); setfillcolor(YELLOW); for (auto p2 : sp) fillrectangle(p2.x * width, p2.y * width, p2.x * width + width - 1, p2.y * width + width - 1); // saveimage(_T("D:\\maze.png")); ret = _getwch(); closegraph(); } return 0; }
至此,迷宫生成算法及迷宫寻路算法已讲述完毕。以 EasyX 制作的迷宫算法可视化程序,如有需要请移步:https://codebus.cn/teternity/post/MazeAlgorithm