最近在写一个控制台小游戏需要一张每次开局都不同的随机地图。我翻了不少方案最后选择了用C来做随机迷宫生成核心算法用了prim算法。折腾了两三个晚上总算是把生成器跑通了效果比预想的好很多。这篇文章我会把完整的实现思路、源码、还有调试时踩过的几个坑整理出来给同样想在自己的项目里接一个随机迷宫功能的朋友做个参考。不管你是要做小游戏关卡、寻路演示还是单纯想练C的数据结构这套代码都能直接拿去用。1. 为什么选 Prim先对比几类主流的迷宫生成算法网上讲迷宫生成的文章很多主流方案就三种递归回溯、随机Prim、Kruskal。很多人上来就推荐递归回溯因为它代码最短。但实际做项目时你会发现不同算法生成的迷宫“气质”完全不一样选错算法后面会很别扭。1.1 三种算法生成的迷宫风格差别很大先说递归回溯它的思路是从起点开始往前挖挖到死路再往回退换个方向继续挖。这种算法生成迷宫的特点是有一条很长的“主动脉”主走廊贯穿整个地图然后从主走廊分出很多短枝。作为游戏地图玩家很容易顺着主干道一路冲到终点支路基本不用探索。优点是代码简单缺点是“太直了”少了点曲径通幽的意思。随机Prim算法则完全不一样。它不是一条路挖到底而是维护一个“候选墙列表”每次随机挑一堵墙拆。从全局来看迷宫是从起点向四周“多点同时生长”的所以生成的结构特别均匀不会出现特别长的主干道分支错落有致更像传统意义上那种绕来绕去的迷宫。Kruskal算法在思路上是另一个极端它把所有墙按随机顺序遍历用并查集判断两端是否连通不连通就拆墙。生成出来的迷宫非常开阔通道四通八达几乎没有任何明显的主干道比较接近“网状结构”。但它实现起来要维护并查集代码量明显比前两个大一圈。算法核心思路生成纹理死胡同比例实现复杂度递归回溯深挖到死路再回溯长走廊短枝杈高低随机Prim随机拆墙多向生长分支均匀环少中中Kruskal并查集合并边缘均匀网状低中高1.2 我的选型理由要随机、要均匀、要容易出效果我做的是小游戏的地图底子对迷宫有两个要求第一是每次生成都要有新鲜感不能生成几次就发现套路第二是地图结构要均匀不能出现一条长廊打通关的情况。随机Prim在这两点上正好处在平衡位置代码量比Kruskal少很多生成的纹理又比递归回溯丰富随机感也更强。还有一点很关键Prim算法的核心逻辑非常容易理解。它本质上就是“每次从候选墙里随机抽一堵能拆就拆”整个算法只需要维护一个数组和一个列表不涉及递归也没有复杂的回溯流程C初学者跟着捋一遍也能看懂。当然Prim也不是万能的后面我在第五节会讲到它的一些局限和调节手段。1.3 本文代码的目标与运行环境我给自己定的目标很明确写一个封装好的C类传入宽度和高度就能生成一张迷宫在控制台里用字符打印出来生成结果保存成二维数据方便以后接寻路算法或者游戏渲染。代码用C11标准本地我用g 9.4实测通过Windows上用Visual Studio建一个空的控制台工程也能直接编译运行只要环境支持C11就没问题。2. 随机 Prim 生成迷宫的底层原理把最小生成树问题“反着玩”要理解随机Prim生成迷宫先得知道课本上的Prim算法是干什么的。很多人在数据结构课上背过“最小生成树”但没意识到迷宫生成和它是同一个问题的两个分支。2.1 经典Prim一直在扩展最小权边上课时学的Prim算法是这样的给定一个带权无向图先随便选一个顶点作为起点然后维护一个“已连通”的顶点集合。每次从所有连接“集合内顶点”和“集合外顶点”的边里挑一条权值最小的边把边另一端的顶点拉进集合。重复这个过程直到所有顶点都在集合里得到的就是一棵最小生成树。这个过程中有一个非常重要的概念叫“切割边”就是那些横跨已访问区域和未访问区域的边。Prim每一步都在切割边里挑最优的所以它始终在“边界”上做文章。2.2 迷宫版本把“最小权”换成“随机权”迷宫生成要的不是“最小”生成树而是任意一棵随机生成树。那我们就把Prim算法的“挑权值最小边”这一步改成“随机抽一条切割边”效果立刻就不一样了每次生成的树都是随机的但依然满足生成树的性质。把空地看成图每个通道格是一个顶点相邻通道格之间的墙是一条边那么迷宫问题就完全等价于“从这张图里选出一组边构成一棵生成树”。生成树保证了两点所有顶点连通迷宫没有不可达的区域没有环迷宫任意两格之间只有一条路径不会出现绕圈子的情况。随机Prim每一次拆墙都是在切割边集合里随机抽取然后把一个新顶点并入当前连通区域。由于拆掉的墙永远只连接一个“已访问”顶点和一个“未访问”顶点所以永远不会把两个已经连通的区域再连起来环也就不会产生。2.3 坐标设计为什么宽高必须是奇数第一次实现的时候我踩过一个特别基础的坑迷宫尺寸设成了偶数结果整个坐标体系全乱了。原因是代码里把迷宫建模成了一张二维网格每个墙占一个格子每个通道也占一个格子通道和墙交替排列。假设通道格坐标是 (x, y)那么它和右边通道格之间的墙坐标就是 (x1, 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::vectorbool grid;保存整个迷宫的格子状态true表示墙false表示通道。用一维数组是因为初始化、遍历、序列化都方便坐标换算就一行代码。std::vectorstd::pairint,int walls;候选墙坐标列表。之所以用std::pair而不是自定义结构体是因为这里只需要坐标不需要额外属性STL容器直接搞定。需要提醒一下std::vectorbool在C里是一个特化版本它不是真正存bool的数组而是做了位压缩。好处是省内存坏处是它没法像普通数组一样提供bool*指针但在迷宫这个场景里完全不碍事。3.2 核心循环随机抽墙、判断两端、打通、扩展整个生成算法的主循环可以分成四个步骤随机从walls里抽一堵墙。抽法很讲究我先随机一个下标然后把该位置的元素和最后一个元素互换再pop_back()。这一步是O(1)的如果用erase删中间元素会有大量元素搬移迷宫一大就慢。根据墙坐标判断它是横向墙还是纵向墙从而算出它两侧相邻的通道格坐标。判断方法很简单墙坐标 (wx, wy)如果wy是偶数说明这是一堵横在上下两个通道格之间的水平墙两侧格子是 (wx, wy-1) 和 (wx, wy1)如果wx是偶数则它是竖墙两侧格子是 (wx-1, wy) 和 (wx1, wy)。检查两侧格子是否合法是否恰好有一个已访问。这里要特别小心数组越界和坐标奇偶性两侧格子必须是合法的奇奇坐标。清空该墙状态把未访问侧格子设为已访问再把新格子四周的墙加入候选列表继续循环。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_castunsigned int( std::chrono::steady_clock::now().time_since_epoch().count()); std::mt19937 rng(seed); std::vectorstd::pairint, 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_distributionint dist(0, static_castint(walls.size()) - 1); int idx dist(rng); std::pairint, 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::vectorbool grid; void addWallIfValid(int x, int y, std::vectorstd::pairint, 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 -stdc11 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版本时发现这类问题绝大多数都出在“坐标系混乱”和“访问状态判断错误”上。下次你要是生成的迷宫有孤立区域先检查这两个地方多半能直接找到病根。
C++实现随机迷宫生成：Prim算法原理与完整代码解析
最近在写一个控制台小游戏需要一张每次开局都不同的随机地图。我翻了不少方案最后选择了用C来做随机迷宫生成核心算法用了prim算法。折腾了两三个晚上总算是把生成器跑通了效果比预想的好很多。这篇文章我会把完整的实现思路、源码、还有调试时踩过的几个坑整理出来给同样想在自己的项目里接一个随机迷宫功能的朋友做个参考。不管你是要做小游戏关卡、寻路演示还是单纯想练C的数据结构这套代码都能直接拿去用。1. 为什么选 Prim先对比几类主流的迷宫生成算法网上讲迷宫生成的文章很多主流方案就三种递归回溯、随机Prim、Kruskal。很多人上来就推荐递归回溯因为它代码最短。但实际做项目时你会发现不同算法生成的迷宫“气质”完全不一样选错算法后面会很别扭。1.1 三种算法生成的迷宫风格差别很大先说递归回溯它的思路是从起点开始往前挖挖到死路再往回退换个方向继续挖。这种算法生成迷宫的特点是有一条很长的“主动脉”主走廊贯穿整个地图然后从主走廊分出很多短枝。作为游戏地图玩家很容易顺着主干道一路冲到终点支路基本不用探索。优点是代码简单缺点是“太直了”少了点曲径通幽的意思。随机Prim算法则完全不一样。它不是一条路挖到底而是维护一个“候选墙列表”每次随机挑一堵墙拆。从全局来看迷宫是从起点向四周“多点同时生长”的所以生成的结构特别均匀不会出现特别长的主干道分支错落有致更像传统意义上那种绕来绕去的迷宫。Kruskal算法在思路上是另一个极端它把所有墙按随机顺序遍历用并查集判断两端是否连通不连通就拆墙。生成出来的迷宫非常开阔通道四通八达几乎没有任何明显的主干道比较接近“网状结构”。但它实现起来要维护并查集代码量明显比前两个大一圈。算法核心思路生成纹理死胡同比例实现复杂度递归回溯深挖到死路再回溯长走廊短枝杈高低随机Prim随机拆墙多向生长分支均匀环少中中Kruskal并查集合并边缘均匀网状低中高1.2 我的选型理由要随机、要均匀、要容易出效果我做的是小游戏的地图底子对迷宫有两个要求第一是每次生成都要有新鲜感不能生成几次就发现套路第二是地图结构要均匀不能出现一条长廊打通关的情况。随机Prim在这两点上正好处在平衡位置代码量比Kruskal少很多生成的纹理又比递归回溯丰富随机感也更强。还有一点很关键Prim算法的核心逻辑非常容易理解。它本质上就是“每次从候选墙里随机抽一堵能拆就拆”整个算法只需要维护一个数组和一个列表不涉及递归也没有复杂的回溯流程C初学者跟着捋一遍也能看懂。当然Prim也不是万能的后面我在第五节会讲到它的一些局限和调节手段。1.3 本文代码的目标与运行环境我给自己定的目标很明确写一个封装好的C类传入宽度和高度就能生成一张迷宫在控制台里用字符打印出来生成结果保存成二维数据方便以后接寻路算法或者游戏渲染。代码用C11标准本地我用g 9.4实测通过Windows上用Visual Studio建一个空的控制台工程也能直接编译运行只要环境支持C11就没问题。2. 随机 Prim 生成迷宫的底层原理把最小生成树问题“反着玩”要理解随机Prim生成迷宫先得知道课本上的Prim算法是干什么的。很多人在数据结构课上背过“最小生成树”但没意识到迷宫生成和它是同一个问题的两个分支。2.1 经典Prim一直在扩展最小权边上课时学的Prim算法是这样的给定一个带权无向图先随便选一个顶点作为起点然后维护一个“已连通”的顶点集合。每次从所有连接“集合内顶点”和“集合外顶点”的边里挑一条权值最小的边把边另一端的顶点拉进集合。重复这个过程直到所有顶点都在集合里得到的就是一棵最小生成树。这个过程中有一个非常重要的概念叫“切割边”就是那些横跨已访问区域和未访问区域的边。Prim每一步都在切割边里挑最优的所以它始终在“边界”上做文章。2.2 迷宫版本把“最小权”换成“随机权”迷宫生成要的不是“最小”生成树而是任意一棵随机生成树。那我们就把Prim算法的“挑权值最小边”这一步改成“随机抽一条切割边”效果立刻就不一样了每次生成的树都是随机的但依然满足生成树的性质。把空地看成图每个通道格是一个顶点相邻通道格之间的墙是一条边那么迷宫问题就完全等价于“从这张图里选出一组边构成一棵生成树”。生成树保证了两点所有顶点连通迷宫没有不可达的区域没有环迷宫任意两格之间只有一条路径不会出现绕圈子的情况。随机Prim每一次拆墙都是在切割边集合里随机抽取然后把一个新顶点并入当前连通区域。由于拆掉的墙永远只连接一个“已访问”顶点和一个“未访问”顶点所以永远不会把两个已经连通的区域再连起来环也就不会产生。2.3 坐标设计为什么宽高必须是奇数第一次实现的时候我踩过一个特别基础的坑迷宫尺寸设成了偶数结果整个坐标体系全乱了。原因是代码里把迷宫建模成了一张二维网格每个墙占一个格子每个通道也占一个格子通道和墙交替排列。假设通道格坐标是 (x, y)那么它和右边通道格之间的墙坐标就是 (x1, 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::vectorbool grid;保存整个迷宫的格子状态true表示墙false表示通道。用一维数组是因为初始化、遍历、序列化都方便坐标换算就一行代码。std::vectorstd::pairint,int walls;候选墙坐标列表。之所以用std::pair而不是自定义结构体是因为这里只需要坐标不需要额外属性STL容器直接搞定。需要提醒一下std::vectorbool在C里是一个特化版本它不是真正存bool的数组而是做了位压缩。好处是省内存坏处是它没法像普通数组一样提供bool*指针但在迷宫这个场景里完全不碍事。3.2 核心循环随机抽墙、判断两端、打通、扩展整个生成算法的主循环可以分成四个步骤随机从walls里抽一堵墙。抽法很讲究我先随机一个下标然后把该位置的元素和最后一个元素互换再pop_back()。这一步是O(1)的如果用erase删中间元素会有大量元素搬移迷宫一大就慢。根据墙坐标判断它是横向墙还是纵向墙从而算出它两侧相邻的通道格坐标。判断方法很简单墙坐标 (wx, wy)如果wy是偶数说明这是一堵横在上下两个通道格之间的水平墙两侧格子是 (wx, wy-1) 和 (wx, wy1)如果wx是偶数则它是竖墙两侧格子是 (wx-1, wy) 和 (wx1, wy)。检查两侧格子是否合法是否恰好有一个已访问。这里要特别小心数组越界和坐标奇偶性两侧格子必须是合法的奇奇坐标。清空该墙状态把未访问侧格子设为已访问再把新格子四周的墙加入候选列表继续循环。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_castunsigned int( std::chrono::steady_clock::now().time_since_epoch().count()); std::mt19937 rng(seed); std::vectorstd::pairint, 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_distributionint dist(0, static_castint(walls.size()) - 1); int idx dist(rng); std::pairint, 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::vectorbool grid; void addWallIfValid(int x, int y, std::vectorstd::pairint, 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 -stdc11 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版本时发现这类问题绝大多数都出在“坐标系混乱”和“访问状态判断错误”上。下次你要是生成的迷宫有孤立区域先检查这两个地方多半能直接找到病根。
