迷宫生成算法：固定大小迷宫与无限迷宫

本文迁移自之前的文章集。包含固定大小迷宫的随机化 Prim 算法与无限迷宫的递归分割算法。对应在线项目见于迷宫生成算法演示。

以下讨论在平面上每个方格放置墙或空地，四相邻的迷宫。此外我们希望生成的迷宫至少是连通的，即任意两个空地，可以从一个出发到另一个。

对于固定大小迷宫，考虑一种随机化 Prim 算法，思路如下：

地图 = 全部为墙
标记 = 全部为空
起点 = 随机选一格
列表 = [起点]
while (列表 非空) {
	一格 = 从列表中 随机挑
    从列表中 删除 该格
	if (该格 被标记) continue;
    标记 该格
    if (该格 周围墙数 ≤ 1) { 将周围4面墙加入列表 }
	终点 = 该格
}

这种算法甚至允许主动选择起点和通过设置初始状态实现大块“空房间”的效果。

关于更自由地使用此算法，可参考三套简单的迷宫地图生成方案。

我们进一步希望我们生成的迷宫岔路尽可能多，定义为不存在 2×2 的墙块。

而为了实现无限，我们需要做的是将迷宫分割成若干个区域（如 64×64 大小的区域），然后将它们衔接。

在每个区域，可使用递归分割算法：

void func (args...) {
	建造横墙
	建造竖墙
	在墙上挖三个洞
	for (区域 : 四个区域) {
		func (args...);
	}
}