六种迷宫与地牢生成实验
一张随机地图，可以是一条不断拐弯的走廊，也可以是一组房间，或者一片没有直角的洞穴。我想把这些差别做成可以动手比较的实验：先生成，再看路线，最后调整规则。
实验室可以切换六种方式。在同一实现版本中，保留算法、尺寸、种子和参数，可以重新生成同一结果。你也可以显示起终点之间的路径，观察直线距离很近的两个位置，实际要绕多远。
先选一张地图
| 生成方式 | 观察重点 | 直接体验 |
|---|---|---|
| 深度优先回溯（DFS） | 连续深入的一条路径，走不动再回退 | 生成主路扭曲型 |
| 随机 Prim | 从已开通区域的边缘向外扩张 | 生成自然分岔型 |
| 房间与迷宫（Rooms and Mazes） | 开阔房间与狭窄走廊交替出现 | 生成块状分割型 |
| 随机 Kruskal | 多个独立片段逐渐合并 | 生成 Kruskal 迷宫 |
| 递归分割 | 大区域被一堵堵墙切成小区域 | 生成递归分割迷宫 |
| 细胞自动机洞穴 | 随机噪声逐渐变成连片的岩壁与空地 | 生成洞穴地图 |
前三项对应兔四《三套简单的迷宫地图生成方案》中使用的三种名称；后三项是本实验补充的对照方法。原文的“块状分割型”指房间与迷宫组合，和这里的“递归分割”是两种做法。本文核对的是 GameRes 上署名兔四的公开版本。
文章内的小图使用精简布局：点击“参数”展开设置，点击“换一张”更换种子；统计指标在完整实验室中查看。手机上建议先用“小 · 31 × 23 格”，大地图缩到窄屏后，通道与标记会更难辨认。
完整页面里的“生成新地图”会换种子，“用当前种子生成”会保留种子重算。切换算法、拖动参数后会即时生成；输入尺寸或种子后确认输入，也会更新地图。宽度支持 21–101、高度支持 21–81，均使用奇数，包含最外侧封闭的墙。输入偶数时会调整为相邻的较小奇数，最终条件以页面显示为准。
连通性与唯一通路
把可走的位置想成点，把相邻位置之间的通道想成线。所有点互相可达，就是连通；如果同时没有环，那么任意两点之间都只有一条不重复经过节点的路径，这种结构叫树。所谓“完美迷宫”，指的就是这种性质，并不代表它一定最好玩。
本实验中的 DFS、Prim、Kruskal 和完整递归分割生成树形迷宫。房间和洞穴则允许宽阔空间，也就允许多种走法。比较它们时，需要分别看“有没有走不到的地方”和“有没有绕路的选择”。
页面里的路线和连通统计都按上下左右四邻接计算，斜着接触的格子不能直接互通。A、B 是地图内部的两个标记，并非在外墙上开的门：程序从一个通行格做一次广度优先搜索，取最远格作为 A，再从 A 搜索得到 B 与最短路线。对于含环的房间、洞穴，这种两次搜索不保证找到全图最远的一对；显示的路线仍然是所选 A、B 之间的最短路线。
| 页面指标 | 本实验的统计口径 |
|---|---|
| 连通区域 | 最终通行格的连通分量数；成功生成后为 1，不是房间的数量 |
| 可通行占比 | 通行格数除以宽 × 高，分母包含外墙；显示到一位小数 |
| 死路数量 | 恰好只有一个相邻通行格的位置数，不是所有支路的条数 |
| A → B 最短路线 | 每次跨到一个相邻通行格计 1 步；不是转弯次数，也不是经过的格子总数 |
房间模式还显示实际房间数及最终留下的连接点数；洞穴模式则显示整理时回填的空地格数。洞穴的这个数不包含平滑过程中所有“空地变墙”的次数。彩色房间和橙色连接点只是观察标记，不会改变通行规则。
状态栏的生成耗时包含生成、连通分析与寻路，不包含绘图和 PNG 编码。它适合观察当前设备上的响应，不宜拿不同浏览器的一次读数直接排算法快慢。
DFS：沿着一条路深入
从一个格子出发，在尚未进入的相邻格子中随机选一个，打通并继续前进。没有新邻居时，就沿记录的来路退回，直到遇到还能延伸的位置。这是深度优先搜索的回溯过程；每次只接入一个新格子，所以不会把已有路径绕成环。Jamis Buck 的回溯法说明
可以把它想成一位带着线团的探路者：先尽量走远，再回头处理漏掉的岔口。通常能看到较长的连续走廊，但具体哪条成为起终点之间的主路，还取决于终点选在哪里。
试试看：生成 DFS 地图。先隐藏路径，猜一猜两个标记之间需要经过多少次转弯，再显示答案。
随机 Prim：随机扩展边缘
本页维护的是一组尚未开通、但邻接已开通区域的前沿格子。每次随机挑一个前沿格，再从它已经开通的邻居中随机选一个接通，随后更新前沿，直到覆盖全部格子。这是随机化的 Prim 变体；随机抽前沿格与随机抽候选墙的抽样方式不同，也都不等于按队列先入先出展开的 BFS。Jamis Buck 的 Prim 说明
相比沿着最新位置深入，多个边缘位置轮流生长，更容易出现分散的短分支。岔口多意味着需要判断的地方多，但不能单凭岔口数断言一定更难：提示、视野和奖励的位置同样会影响探索体验。
试试看：用相同种子生成 Prim，再切回 DFS。相同种子便于保存实验条件；不同算法消耗随机数的方式不同，因此不会共享相同的道路骨架。
房间与迷宫：预留房间
Bob Nystrom 的方法先放置互不重叠的房间，再让迷宫填满剩余空间。随后寻找隔着一格墙的不同区域，打通必要连接，并可添加额外连接；最后回填走廊的死胡同。房间的位置、尺寸与迷宫网格对齐，方便衔接。Rooms and Mazes 原文
这里有两个容易混淆的细节。连接阶段是在“区域组成的图”上避免遗漏，不能据此说整张地牢只有一条路：房间内部已经有多种走法。回填死胡同也不会凭空产生环；增加连接才会提供新的绕路。
实验室把这个过程的几项取舍做成了控件：
- 房间放置尝试（20–180 次）：增加放置机会，实际能放下多少仍受空间和重叠检查约束；小图很快就会放不下更多房间。
- 额外连接概率（0–25%）：调整连接阶段的额外开口机会，观察有没有新增的迂回路线；这个比例不等于最终地图的环占比。
- 走廊曲折程度（0–100%）：数值较低时，在还能直行的情况下更偏好沿原方向走；100% 表示重新随机选方向，也可能再次选中直行，并非每步必转弯。
- 修剪走廊死路：用相同种子开关对比，观察哪些非房间格被回填；房间本身会保留。
试试看：生成一张地牢。把一间房想成营地、一间想成战斗区域，看看路线是否给了玩家准备与绕行的机会。
Kruskal：合并区域
最初每个格子都是独立区域。将相邻格子之间的候选边打乱，逐条检查：两侧属于不同区域，就连接并合并；已经属于同一区域，就跳过，避免闭环。程序通常用并查集快速判断两个格子是否已经相通。Jamis Buck 的 Kruskal 说明
它和 Prim 最值得比较的是生长位置：Prim 围绕已有区域推进，Kruskal 可以在地图各处建立片段。两者都能得到树形迷宫，地图纹理却可能不同。
试试看：生成 Kruskal 地图，观察短死路和长通道的分布，再换几个种子检查这个印象是否稳定。
递归分割：逐层加墙
先有一片可走的区域，加一堵水平或竖直的墙，并留下一个门洞，再对墙两侧重复。每次分区保留唯一通道；细分到单行或单列时停止，便能得到树形迷宫。Jamis Buck 的递归分割说明
它很适合观察“大结构先决定，小结构后补充”的过程。长墙会形成明显边界，门洞则成为跨区必经之处。这里的门洞只是通路，没有额外的钥匙或开门机制。
试试看：生成递归分割地图，寻找把地图分成两大片的墙，再沿墙找到唯一通口。
细胞自动机：生成洞穴
先随机分布岩壁和空地，再反复查看每格周围的墙：周围越拥挤，越倾向于变成墙；周围越空旷，越倾向于成为地面。邻域规则可以让碎片聚合，却不能单独保证不同空地相通，所以需要后续识别和处理独立区域。Sebastian Lague 的洞穴生成实现
洞穴适合比较空间轮廓，不要求每条路都只有一个格子宽。本页的平滑规则是：周围八格中，岩壁至少 5 格则变墙，至多 3 格则变空地，恰好 4 格保持原状；每轮都从上一轮完整结果同步计算。这里观察的是八邻域，后续行走和连通检查仍使用四邻接。
本实验在平滑后保留最大的连通空地，把孤立碎片回填为岩壁，再选择起终点；因此看到的结果包含生成后的整理步骤。初始岩石比例可调 38–56%，平滑可调 2–7 轮，初始比例不等于最终岩壁占比。若最大空地不足 9 格，会改为中央的一小块空地，并在完整页面提示。可以查看一个小图极端样本：不同种子也可能经这种整理得到同样的地图，不能把它当作平滑规则本身保证了连通。
试试看：生成洞穴。固定种子，先只改变初始墙比例，再只改变平滑次数，分别观察岩壁占地和狭窄通道的变化。
可复查的对照实验
用“修剪走廊死路”做一次单变量实验，无需操作指令：
- 打开保留死路的地图。确认种子为
rooms-first、尺寸 61 × 41、放置尝试 90、额外连接 8%、曲折程度 55%。 - 观察几个走不通的走廊，然后只勾选“修剪走廊死路”；也可以直接打开修剪后的同条件地图。
- 对照房间是否保留、死路是否消失，并分别保存两张图的分享链接。
2026 年 9 月 8 日的当前实现得到以下结果，供核对操作条件；这是一组样本，不代表所有种子的统计结论。
| 条件 | 房间数 | 可通行占比 | 死路数 | A → B 路线 |
|---|---|---|---|---|
| 保留死路 | 19 | 58.9% | 27 | 168 步 |
| 修剪死路 | 19 | 52.6% | 0 | 155 步 |
参数改变后，A、B 会重新选定。 这组样本的端点也变了，不能据 168 → 155 步声称“同一起终点之间出现了捷径”。两条路线都仍是各自端点的最短路线；观察回填效果时，房间保留情况、通行面积和死路数更直接。
分享链接与导出图片
“分享”会保存当前算法、尺寸、种子、该算法的参数，以及路线、房间区分、格线的显示选择。从文章内嵌图分享时，链接会自动打开完整工作台。若浏览器不允许自动复制，弹窗仍会选中链接，可手动复制。复现链接并没有固定程序版本；需要长期留档时，建议把链接与 PNG 一起保存。
“导出 PNG”得到的是静态图片，包含当前观察图层、A/B 标记、算法名、种子、尺寸、路线步数和相关生成参数。地图部分按每格 16 像素绘制，因此不会因为手机屏幕较窄就只导出一张缩小截图。若未自动下载，点击地图下方的“保存 PNG”；导出期间换了地图时，提示会明确为“保存刚才的 PNG”。PNG 用于查看和交流，当前页面没有 JSON、SVG、可编辑关卡文件的导出或图片导入功能。
生成与图片编码都在浏览器本地完成。完整网页文件可离线使用；仅保存一个本地 file:// 地址，其他电脑并不会因此取得网页文件。在线分享链接仍需能访问本站，或由对方拥有同一份完整网页及脚本。
从随机结果到设计
我会先选定一种要观察的体验，例如“能否绕开一场战斗”，然后固定种子，每次只改一个参数。发现有趣的结果就保留链接；需要存档时，也可以从实验室导出地图。
树形迷宫适合研究回溯和路径判断；房间与走廊适合安排空间节奏；洞穴适合研究不规则地形。地图的形状只是开始。下一步可以在同一张地图上尝试放置目标、资源和障碍，看看这些规则是否真的让探索产生了选择。
关于参考资料
这篇文章和互动页面采用自己的文字与实现，没有搬运参考文章的配图、动画或整段代码。主要灵感来自 Bob Nystrom 的 Rooms and Mazes，以及兔四的知乎原链接。整理时知乎页面返回访问限制，未取得该页面正文；三种方案的名称与内容依据 GameRes 上同名、同署名的公开文章核对。Kruskal、递归分割和细胞自动机是额外加入的对照实验，各自资料已列在对应段落。