企业官网建设流程全解析

最近在写一个控制台小游戏，需要一张每次开局都不同的随机地图。我翻了不少方案，最后选择了用C++来做随机迷宫生成，核心算法用了prim算法。折腾了两三个晚上，总算是把生成器跑通了，效果比预想的好很多。这篇文章我会把完整的实现思路、源码、还有调试时踩过的几个坑整理出来，给同样想在自己的项目里接一个随机迷宫功能的朋友做个参考。不管你是要做小游戏关卡、寻路演示，还是单纯想练C++的数据结构，这套代码都能直接拿去用。

1. 为什么选 Prim：先对比几类主流的迷宫生成算法

网上讲迷宫生成的文章很多，主流方案就三种：递归回溯、随机Prim、Kruskal。很多人上来就推荐递归回溯，因为它代码最短。但实际做项目时你会发现，不同算法生成的迷宫“气质”完全不一样，选错算法后面会很别扭。

1.1 三种算法生成的迷宫风格差别很大

先说递归回溯，它的思路是从起点开始往前挖，挖到死路再往回退，换个方向继续挖。这种算法生成迷宫的特点是有一条很长的“主动脉”，主走廊贯穿整个地图，然后从主走廊分出很多短枝。作为游戏地图，玩家很容易顺着主干道一路冲到终点，支路基本不用探索。优点是代码简单，缺点是“太直了”，少了点曲径通幽的意思。

随机Prim算法则完全不一样。它不是一条路挖到底，而是维护一个“候选墙列表”，每次随机挑一堵墙拆。从全局来看，迷宫是从起点向四周“多点同时生长”的，所以生成的结构特别均匀，不会出现特别长的主干道，分支错落有致，更像传统意义上那种绕来绕去的迷宫。

Kruskal算法在思路上是另一个极端，它把所有墙按随机顺序遍历，用并查集判断两端是否连通，不连通就拆墙。生成出来的迷宫非常开阔，通道四通八达，几乎没有任何明显的主干道，比较接近“网状结构”。但它实现起来要维护并查集，代码量明显比前两个大一圈。

1.2 我的选型理由：要随机、要均匀、要容易出效果

我做的是小游戏的地图底子，对迷宫有两个要求：第一是每次生成都要有新鲜感，不能生成几次就发现套路；第二是地图结构要均匀，不能出现一条长廊打通关的情况。随机Prim在这两点上正好处在平衡位置：代码量比Kruskal少很多，生成的纹理又比递归回溯丰富，随机感也更强。

还有一点很关键，Prim算法的核心逻辑非常容易理解。它本质上就是“每次从候选墙里随机抽一堵，能拆就拆”，整个算法只需要维护一个数组和一个列表，不涉及递归，也没有复杂的回溯流程，C++初学者跟着捋一遍也能看懂。当然Prim也不是万能的，后面我在第五节会讲到它的一些局限和调节手段。

1.3 本文代码的目标与运行环境

我给自己定的目标很明确：写一个封装好的C++类，传入宽度和高度就能生成一张迷宫，在控制台里用字符打印出来，生成结果保存成二维数据，方便以后接寻路算法或者游戏渲染。代码用C++11标准，本地我用g++ 9.4实测通过，Windows上用Visual Studio建一个空的控制台工程也能直接编译运行，只要环境支持C++11就没问题。

2. 随机 Prim 生成迷宫的底层原理：把最小生成树问题“反着玩”

要理解随机Prim生成迷宫，先得知道课本上的Prim算法是干什么的。很多人在数据结构课上背过“最小生成树”，但没意识到迷宫生成和它是同一个问题的两个分支。

2.1 经典Prim：一直在扩展最小权边

上课时学的Prim算法是这样的：给定一个带权无向图，先随便选一个顶点作为起点，然后维护一个“已连通”的顶点集合。每次从所有连接“集合内顶点”和“集合外顶点”的边里，挑一条权值最小的边，把边另一端的顶点拉进集合。重复这个过程，直到所有顶点都在集合里，得到的就是一棵最小生成树。

这个过程中有一个非常重要的概念叫“切割边”，就是那些横跨已访问区域和未访问区域的边。Prim每一步都在切割边里挑最优的，所以它始终在“边界”上做文章。

2.2 迷宫版本：把“最小权”换成“随机权”

迷宫生成要的不是“最小”生成树，而是任意一棵随机生成树。那我们就把Prim算法的“挑权值最小边”这一步改成“随机抽一条切割边”，效果立刻就不一样了：每次生成的树都是随机的，但依然满足生成树的性质。

把空地看成图，每个通道格是一个顶点，相邻通道格之间的墙是一条边，那么迷宫问题就完全等价于“从这张图里选出一组边，构成一棵生成树”。生成树保证了两点：

• 所有顶点连通，迷宫没有不可达的区域；
• 没有环，迷宫任意两格之间只有一条路径，不会出现绕圈子的情况。

随机Prim每一次拆墙，都是在切割边集合里随机抽取，然后把一个新顶点并入当前连通区域。由于拆掉的墙永远只连接一个“已访问”顶点和一个“未访问”顶点，所以永远不会把两个已经连通的区域再连起来，环也就不会产生。

2.3 坐标设计：为什么宽高必须是奇数

第一次实现的时候，我踩过一个特别基础的坑：迷宫尺寸设成了偶数，结果整个坐标体系全乱了。原因是代码里把迷宫建模成了一张二维网格，每个墙占一个格子，每个通道也占一个格子，通道和墙交替排列。

假设通道格坐标是 (x, y)，那么它和右边通道格之间的墙坐标就是 (x+1, y)。要让“通道-墙-通道”这种结构以固定的节奏排下去，迷宫总宽度必须是奇数，通道格永远落在 (奇数, 奇数) 坐标上，墙则落在至少有一个坐标是偶数的位置上。举例来说，一个 7 宽 5 高的迷宫，通道格只可能在 (1,1)、(3,1)、(5,1)、(1,3)、(3,3)、(5,3) 这些坐标上，其余全是墙。起点就选 (1,1)，左上角靠内部的位置。

这个设计带来的好处特别直接：一段数组就能装下整个迷宫，坐标 (x, y) 对应的数组下标就是y * width + x，拆墙就是把墙坐标位置从“墙”改成“通道”，判断两个格子是否连通只需要看坐标是不是相邻的奇奇格。

2.4 候选墙列表：核心不变量

随机Prim生成迷宫的整个逻辑，可以概括成一句话：维护一个候选墙列表，不断从里面随机抽墙拆。

候选墙列表里存的是哪些墙？是“当前已访问区域”和“未访问区域”之间的墙。一开始只有起点 (1,1) 是已访问的，所以候选墙就是起点上下左右四堵墙。每次从列表里抽一堵墙出来，判断它两侧的格子：如果恰好一侧已访问、一侧未访问，就拆掉它，把未访问那一侧标记为已访问，再把新格子四周的墙加入候选列表。如果两侧都已访问，或者都没访问，说明这堵墙已经没有“连接新区域”的价值了，直接丢弃。

这里有一个细节值得反复品味：候选墙列表其实就是图论里的“切割边”集合。只要始终只从切割边集合里选墙拆，生成结果就天然是一棵生成树。很多写迷宫的人喜欢在拆墙时随意打通墙，结果迷宫出现环路，就是因为没有守住这条不变量。

3. C++ 实现：从数据结构到可编译的完整代码

原理讲清楚了，代码就好写了。下面这部分我直接给出可以编译运行的完整C++实现，再拆开解释每一步为什么这么写。

3.1 数据结构：一维 vector 和候选墙列表

我用两个核心数据结构：

• std::vector<bool> grid;，保存整个迷宫的格子状态，true表示墙，false表示通道。用一维数组是因为初始化、遍历、序列化都方便，坐标换算就一行代码。
• std::vector<std::pair<int,int>> walls;，候选墙坐标列表。之所以用std::pair而不是自定义结构体，是因为这里只需要坐标，不需要额外属性，STL容器直接搞定。

需要提醒一下，std::vector<bool>在C++里是一个特化版本，它不是真正存bool的数组，而是做了位压缩。好处是省内存，坏处是它没法像普通数组一样提供bool*指针，但在迷宫这个场景里完全不碍事。

3.2 核心循环：随机抽墙、判断两端、打通、扩展

整个生成算法的主循环可以分成四个步骤：

1. 随机从walls里抽一堵墙。抽法很讲究：我先随机一个下标，然后把该位置的元素和最后一个元素互换，再pop_back()。这一步是O(1)的，如果用erase删中间元素，会有大量元素搬移，迷宫一大就慢。
2. 根据墙坐标判断它是横向墙还是纵向墙，从而算出它两侧相邻的通道格坐标。判断方法很简单：墙坐标 (wx, wy)，如果wy是偶数，说明这是一堵横在上下两个通道格之间的水平墙，两侧格子是 (wx, wy-1) 和 (wx, wy+1)；如果wx是偶数，则它是竖墙，两侧格子是 (wx-1, wy) 和 (wx+1, wy)。
3. 检查两侧格子是否合法，是否恰好有一个已访问。这里要特别小心数组越界和坐标奇偶性，两侧格子必须是合法的奇奇坐标。
4. 清空该墙状态，把未访问侧格子设为已访问，再把新格子四周的墙加入候选列表，继续循环。

3.3 完整源码

下面是我整理好的完整代码，去掉注释分隔线大概一百行，直接复制就能跑：

#include <iostream> #include <vector> #include <utility> #include <random> #include <chrono> class MazeGenerator { public: MazeGenerator(int w, int h) { // 保证迷宫宽高为奇数，偶数时自动加 1 width = (w % 2 == 0) ? w + 1 : w; height = (h % 2 == 0) ? h + 1 : h; grid.assign(width * height, true); } void generate() { // 重新初始化 std::fill(grid.begin(), grid.end(), true); // 随机数引擎，用当前时间做种子 unsigned int seed = static_cast<unsigned int>( std::chrono::steady_clock::now().time_since_epoch().count()); std::mt19937 rng(seed); std::vector<std::pair<int, int>> walls; // 起点选在 (1,1)，这个位置在奇奇坐标上，必定是通道格 int startX = 1, startY = 1; grid[startY * width + startX] = false; // 把起点四周的墙加入候选列表 addWallIfValid(startX, startY - 1, walls); addWallIfValid(startX, startY + 1, walls); addWallIfValid(startX - 1, startY, walls); addWallIfValid(startX + 1, startY, walls); while (!walls.empty()) { // 随机抽一堵墙，O(1) 删除 std::uniform_int_distribution<int> dist(0, static_cast<int>(walls.size()) - 1); int idx = dist(rng); std::pair<int, int> wall = walls[idx]; walls[idx] = walls.back(); walls.pop_back(); int wx = wall.first; int wy = wall.second; // 计算墙两侧的通道格坐标 int ax, ay, bx, by; if (wy % 2 == 0) { // 水平墙，上下各一个通道格 ax = wx; ay = wy - 1; bx = wx; by = wy + 1; } else { // 竖向墙，左右各一个通道格 ax = wx - 1; ay = wy; bx = wx + 1; by = wy; } // 越界或坐标不是奇奇格，直接丢弃 if (ax < 0 || ay < 0 || bx < 0 || by < 0 || ax >= width || ay >= height || bx >= width || by >= height) { continue; } if (ax % 2 == 0 || ay % 2 == 0 || bx % 2 == 0 || by % 2 == 0) { continue; } bool aVisited = !grid[ay * width + ax]; bool bVisited = !grid[by * width + bx]; // 两侧访问状态相同，要么都已访问，要么都没访问，不能拆 if (aVisited == bVisited) { continue; } // 打通墙 grid[wy * width + wx] = false; // 把新访问的通道格标记为已访问，并把它四周的墙加入候选 int newX, newY; if (!aVisited) { newX = bx; newY = by; grid[newY * width + newX] = false; } else { newX = ax; newY = ay; grid[newY * width + newX] = false; } addWallIfValid(newX, newY - 1, walls); addWallIfValid(newX, newY + 1, walls); addWallIfValid(newX - 1, newY, walls); addWallIfValid(newX + 1, newY, walls); } // 手动开入口和出口：入口在顶部边界，出口在底部边界 grid[0 * width + 1] = false; grid[(height - 1) * width + (width - 2)] = false; } void print() const { for (int y = 0; y < height; ++y) { for (int x = 0; x < width; ++x) { std::cout << (grid[y * width + x] ? '#' : ' '); } std::cout << '\n'; } } bool isWall(int x, int y) const { return grid[y * width + x]; } private: int width, height; std::vector<bool> grid; void addWallIfValid(int x, int y, std::vector<std::pair<int, int>>& walls) const { if (x < 0 || y < 0 || x >= width || y >= height) return; if (grid[y * width + x]) { walls.emplace_back(x, y); } } }; int main() { MazeGenerator maze(41, 21); maze.generate(); maze.print(); return 0; }

3.4 编译与运行效果

把代码存成random_maze.cpp，在终端里执行：

g++ -std=c++11 random_maze.cpp -o random_maze ./random_maze

输出就是一张用#表示墙、空格表示通道的字符迷宫。因为入口和出口被我单独打通了，所以迷宫顶部有一个缺口、底部有一个缺口。每次运行结果都不一样，如果你把尺寸改成 7 宽 5 高，控制台里还会刷出一个迷你迷宫，很适合拿来调试。

4. 调试中踩过的坑和三个容易被忽略的细节

这一段是我实际写代码时踩过的真实坑，每一个都让我debug了好一段时间，列出来给大家避避雷。

4.1 随机数种子：为什么生成的迷宫总是一模一样

第一次跑通时，我连续执行了三次程序，发现三次输出一模一样。原因很经典：rand()函数如果不设置种子，默认种子是固定值1，生成序列完全一致。很多人会立刻想到用srand(time(nullptr))设种子，但这也会带来一个隐蔽问题：程序在一秒内连续生成多个迷宫时，time返回的秒数是一样的，导致这几个迷宫也完全一致。

我的解决办法是彻底弃用rand()，改用<random>库里的std::mt19937，种子取std::chrono::steady_clock的纳秒计数。这样每次生成迷宫时种子几乎不可能重复，即使在同一毫秒内多次生成也能保证序列不同。另外std::mt19937的随机质量比rand()好太多，生成的迷宫分布更均匀，不会出现大片区域结构相似的情况。

4.2 偶数尺寸和越界：迷宫边缘冒出莫名其妙的洞

我最初设迷宫为 30 宽 20 高，结果打印出来一看，边缘有几个“半截通道”，还有个别墙位置错乱，整个迷宫像是被什么东西啃过。排查了半天，发现根因就是宽高设成了偶数。偶数尺寸下，通道格坐标无法稳定落在“奇奇”位置上，主循环里根据墙坐标计算两侧通道格时，经常算出 (偶数, 奇数) 这类不该出现的坐标，然后错误地打通了墙。

这个问题的教训是：在数据结构设计上就把约束写死，比在算法里到处做检查要可靠得多。所以我最终在构造函数里做了保护：传入偶数尺寸就自动加一变成奇数。这样外部无论如何传参，迷宫内部总能保持自洽的奇偶结构。

另一个边界相关的坑是：拆墙时没有检查墙的邻居是否越界。比如 (1,0) 这堵墙在迷宫最上沿，它的一侧是 (1,1) 起点，另一侧是 (1,-1)，直接越界了。如果不检查就把 (1,-1) 当成格子来读，轻则写出错误迷宫，重则越界访问内存导致程序崩溃。处理方式是主循环里老老实实做越界判断，非法墙直接丢弃。边界上的洞一定不是算法长出来的，而是手动打通入口/出口时单独开的。

4.3 候选墙列表重复入队的影响

按我上面代码的写法，同一个墙坐标是有可能被重复添加进候选列表的。比如墙 (2,1) 一开始作为起点右墙被加入，后来 (3,1) 被访问后，又会把 (2,1) 作为它的左墙再加入一次。如果这个墙一直没有被抽中，列表里就存在两个一模一样的坐标。

重复会不会破坏生成树的正确性？不会。因为当重复的墙被抽出来时，它要么已经被打通了，两侧都已访问，会被“访问状态相同”分支过滤掉；要么还没打通，但此时它仍然是一堵连接已访问和未访问区域的墙，拆掉它仍然是合法的。所以正确性完全不受影响。

但公平性会受一点影响：重复出现的墙被抽中的概率更高，相当于某些墙拥有了“加权”，这会让随机分布不是完全均匀的。实际效果上，影响小到肉眼看不出来。我做这个项目时选择接受重复，因为检查去重需要额外维护一套哈希集合或标记数组，代码复杂度和运行开销都上去了，收益却微乎其微。如果你想做严格的统计实验，再考虑去重优化。

4.4 快速验证生成结果是否正确

代码写完后别急着接项目，先花一分钟验证迷宫质量。我常用的验证方法是写一个BFS遍历函数：从入口 (0,1) 出发，计算能到达的通道格数量，再统计整个迷宫里的奇奇通道格总数。两个数相等，说明迷宫内部完全连通，没有孤岛区域；如果不相等，那八成是主循环里“访问状态判断”写错了。

另外一个我很关心的指标是死胡同数量。死胡同指的是三面都是墙、只有一个方向可以走的通道格。Prim算法生成的迷宫死胡同数量在我的测试里大概占全部通道格的15%到20%。这个数据我不建议当成标准答案去背，因为不同尺寸、不同随机种子差异不小，但它可以作为你检查算法是否正确的一个参考维度：如果死胡同占比异常低，比如接近0，那很可能生成出来的不是迷宫而是一堆并排通道。

5. 让迷宫活起来：动画、寻路扩展与系列规划

迷宫生成只是第一步，要把这坨字符数据真正用进项目里，后面还可以做不少有意思的扩展。

5.1 控制台动画：看着迷宫一点点长出来

调试的时候，我一直想在每次拆墙后看看迷宫长成什么样。最简单的办法是每次循环都清屏重绘。Windows平台可以用system("cls")，跨平台一点的做法是用ANSI转义序列\033[H把光标移回左上角，再重新打印整个网格。

不过system("cls")每次调用都挺慢，一帧一刷会明显卡顿。我的做法是每拆 10 到 20 堵墙才刷新一次，并且用Sleep(5)控制速度。这样你能清楚看到迷宫从起点向四周生长的过程，那种“一个点长出一棵树”的感觉非常直观，用来给别人讲Prim算法原理特别好使。

5.2 玩法扩展：寻路、障碍与难度参数

迷宫生成完，顺手就可以接寻路算法。因为内部数据已经是一张标准的二维网格了，BFS寻路和A*寻路都能直接跑。把路径上的格子标记成别的字符，迷宫就变成了“寻找出口”的关卡。

如果你对难度有要求，可以调节Prim的随机策略。举个例子：抽墙时不使用完全均匀分布，而是偏向抽取靠近当前已访问区域中心的墙，生成结果就会更偏向于枝杈密集的洞穴；反过来偏向抽取边缘的墙，就会得到更开阔的通道。这种“可控随机”是Prim算法比较好调节的优势，递归回溯想做到类似效果就麻烦很多。

还有一点要提醒，迷宫通道通常只支持四方向移动。如果你的游戏角色支持斜向移动，一定要额外判断对角线两侧的墙是否同时存在，否则角色会从墙角直接穿过去。这个问题在游戏开发里特别常见，属于那种不测根本发现不了、测出来又觉得自己蠢的bug。

5.3 系列计划：下一篇想对比递归回溯和 Kruskal

这个标题是“(1)prim算法”，我打算把迷宫生成做成一个系列。下一篇大概率会做递归回溯算法和Kruskal算法的完整实现，用同一个MazeGenerator接口，方便替换核心算法来对比纹理效果。之后可能还会写BFS和A*寻路，最后把迷宫生成和寻路做成一个完整的控制台小游戏。

最后分享一个我常用的调试小技巧：写一个统计函数，遍历整个迷宫，把空格区域用洪泛填充算法标上不同编号，一眼就能看出迷宫是不是有多块不连通的区域。这个方法对于排查递归回溯和Kruskal的bug同样适用。我在做Prim版本时发现，这类问题绝大多数都出在“坐标系混乱”和“访问状态判断错误”上。下次你要是生成的迷宫有孤立区域，先检查这两个地方，多半能直接找到病根。