| 四种迷宫生成算法的实现和可视化 | 您所在的位置：网站首页 › 迷宫图简单画法教程 › 四种迷宫生成算法的实现和可视化 |
四种迷宫生成算法的实现和可视化
|
（上图是使用随机化Prim算法生成一个200x200的迷宫的过程） Github项目地址：maze 前言本文中的迷宫指的是最常见的那种迷宫：迷宫整体轮廓是二维矩形，迷宫里的格子是正方形的，格子上下左右各相邻另外一个格子（边和角除外），迷宫内部没有环路，也没有无法到达的格子，起点在一个角（本文中为左上角），终点在另一个角（本文中为右下角），从起点到终点有且仅有一条路径：
每个格子都可以抽象成图上的一个点，而相邻且连通的格子间的路径可以抽象成图像的一个边，不难发现这实际上是一棵树。
常见的迷宫生成算法有4种：深度优先算法、随机化Kruskal算法、随机化Prim算法和递归分割算法。对这4种算法再分类可以分为2类：前3种归为一类，最后1种自成一类。为什么我在这里将前3种归为一类呢？因为前3种算法有着相似的流程： 将所有相邻格子连接起来，形成一个无向图G={V,E}。构造G的一个子图G'={V',E'}，G'要求是一颗树，且V'=V前3种算法的不同之处在于第2步构造G'时所使用的方法不同。 数据结构前面我们已经看到了，迷宫可以抽象为一颗树，在此我们使用邻接表来存储树，邻接表类AdjacencyList定义如下（省略了实现和非关键代码）： class AdjacencyList { public: AdjacencyList(int row = 0, int column = 0); void connect(int i, int j); void disconnect(int i, int j); int row() const { return m_row; } int column() const { return m_column; } std::vector &neighbor(int i); std::vector &surround(int i); private: int m_row; int m_column; std::vector m_index2neighbor; std::vector m_index2surround; };迷宫中的格子抽象成的点按照从左向右，从上向下进行编号，row()和column()用来获得迷宫的大小，connect()用来连接两个相邻的点，disconnect()用来断开两个连接的点，neighbor()用来获取与某个点相连接的点，surround()用来获取与某个点相邻（不一定连接在一起）的点。 深度优先算法算法过程图示：
使用深度优先算法构造得到的G'实际上就是G的深度优先搜索树，与普通的深度优先算法不同的是，选择下一个要染灰的点时需要加入一些随机性，否则迷宫每次都会生成得一摸一样。算法代码为： AdjacencyList DeepFirstSearch::generate() { enum Color { White, Gray, Black }; AdjacencyList result(m_row, m_column); vector color(static_cast(m_row * m_column), White); vector current; current.reserve(static_cast(m_row * m_column)); color[0] = Gray; current.push_back(0); while (current.size()) { int last = current.back(); random_shuffle(result.surround(last).begin(), result.surround(last).end()); auto iter = result.surround(last).cbegin(); for (; iter != result.surround(last).cend(); iter++) { if (color[static_cast(*iter)] == White) { color[static_cast(*iter)] = Gray; result.connect(last, *iter); current.push_back(*iter); break; } } // all adjacent points are found if (iter == result.surround(last).cend()) { current.pop_back(); color[static_cast(last)] = Black; } } return result; } 随机化Kruskal算法算法过程图示：
Kruskal原本是构造最小生成树的算法，但迷宫中的边都没有权重（或者说权重都是0），因此在把新边加入树中时随机选择一个就可以。在选择边时需要引入随机性，否则每次都会得到相同的结果。算法代码为： AdjacencyList Kruskal::generate() { AdjacencyList result(m_row, m_column); UnionFind uf(m_row * m_column); vector edges; for (int i = 0; i // avoid duplicate edge if (i > iter) { edges.push_back(pair(i, iter)); } } } random_shuffle(edges.begin(), edges.end()); for (auto iter : edges) { if(!uf.connected(iter.first, iter.second)) { uf.connect(iter.first, iter.second); result.connect(iter.first, iter.second); } } return result; } 随机化Prim算法算法过程图示：
Prim同样是构造最小生成树的算法，注意事项和Kruskal相同。算法代码为： AdjacencyList Prim::generate() { AdjacencyList result(m_row, m_column); vector linked(static_cast(m_row * m_column), false); linked[0] = true; set paths; paths.insert(pair(0, 1)); paths.insert(pair(0, m_column)); static default_random_engine e(static_cast(time(nullptr))); while (!paths.empty()) { // random select a path in paths int pos = static_cast(e() % paths.size()); auto iter = paths.begin(); advance(iter, pos); // connect the two node of path result.connect(iter->first, iter->second); // get the node not in linked int current = 0; if (!linked[static_cast(iter->first)]) { current = iter->first; } else { current = iter->second; } // add the node to linked linked[static_cast(current)] = true; // add all not accessed path to paths, and delete all invalid path from paths for (auto i : result.surround(current)) { pair currentPath = makeOrderedPair(i, current); if (!linked[static_cast(i)]) { paths.insert(currentPath); } else { paths.erase(paths.find(currentPath)); } } } return result; } 递归分割算法算法过程图示：
如果说前面3种算法是通过“拆墙”来构造迷宫，那么递归分割算法就是通过“建墙”来构造迷宫了。在当前要处理的矩形中随机选择一个点，然后以这个点为中心向上下左右4个方向各建一堵墙，其中3堵墙都要留门，不然就会出现无法到达的区域。对被这4堵墙划分成的4个矩形递归执行这个过程，就能得到一个迷宫。算法代码为： AdjacencyList RecursiveDivision::generate() { AdjacencyList result(m_row, m_column); result.connectAllSurround(); divide(result, 0, 0, m_column - 1, m_row - 1); return result; } void RecursiveDivision::divide(AdjacencyList &list, int left, int top, int right, int bottom) { // the x range of input is [left, right] // the y range of input is [top, bottom] if ((right - left int p = y * m_column + i; int q = (y + 1) * m_column + i; toDisconnect.emplace_back(p, q); } for (int i = top; i 0}; // get the gap position gapPos[0] = static_cast(e() % static_cast(y - top + 1)) + top; gapPos[1] = static_cast(e() % static_cast(bottom - y)) + y + 1; gapPos[2] = static_cast(e() % static_cast(x - left + 1)) + left; gapPos[3] = static_cast(e() % static_cast(right - x)) + x + 1; for (int i = 0; i int p = 0; int q = 0; if (i p = y * m_column + gapPos[i]; q = (y + 1) * m_column + gapPos[i]; } pair pair(p, q); toDisconnect.erase(find(toDisconnect.begin(), toDisconnect.end(), pair)); } } for (auto &pair : toDisconnect) { list.disconnect(pair.first, pair.second); } divide(list, left, top, x, y); divide(list, x + 1, top, right, y); divide(list, left, y + 1, x, bottom); divide(list, x + 1, y + 1, right, bottom); } 参考链接Maze generation algorithm：https://en.wikipedia.org/wiki/Maze_generation_algorithm |
【本文地址】