前言
成品预览：https://codesandbox.io/s/maze-vite-15-i7oik?file=/src/maze.js
不久前写了一篇文章介绍了如何解迷宫：https://www.cnblogs.com/judgeou/p/14805429.html
这回来说说怎么生成迷宫。
解迷宫通常是先把原始数据（图片）转换为特定数据结构，然后对其执行一些算法，得出结果。而生成迷宫，理所应当的是先使用合适的算法生成数据结构，再把这个数据结构渲染出来：
- 解迷宫：输入 -> 数据结构 -> 算法处理
- 生成迷宫：算法处理 -> 数据结构 -> 输出
原初形态
这是一个 8x8 的迷宫：
每一个房间都无法到达其他房间，而我们要做的，就是从里面挑选一些格子，然后打掉他的某些墙壁，让他与隔壁房间联通。
下面来设计它的数据结构：
class Cell {
constructor (x, y, value) {
this.x = x
this.y = y
this.value = value
}
}
class MazeGanerator {
static 上 = 0b1000
static 左 = 0b0100
static 下 = 0b0010
static 右 = 0b0001
/**
*
* @param {Number} width
* @param {Number} height
*/
constructor (width, height) {
this.width = width
this.height = height
this.cellSize = 50
this.cellBorder = 2
this.nodes = new Array(width * height)
}
build () {
let { nodes } = this
let { length } = nodes
for (let i = 0; i < length; i++) {
let { x, y } = this.indexToPos(i)
let node = nodes[i] = new Cell(x, y, 0b1111) // 4个bit代表上下左右墙壁的开闭状态，0：开，1：闭
}
}
/**
*
* @param {HTMLCanvasElement} canvas
*/
renderCanvas (canvas) {
const { 上, 左, 下, 右 } = MazeGanerator
let { nodes, width, height, cellSize, cellBorder } = this
let { length } = nodes
canvas.width = width * cellSize
canvas.height = height * cellSize
let ctx = canvas.getContext('2d')
ctx.fillStyle = "#FFFFFF"
ctx.fillRect(0, 0, canvas.width, canvas.height)
for (let i = 0; i < length; i++) {
let node = nodes[i]
let { x, y, value } = node
let leftTopX = x * cellSize
let leftTopY = y * cellSize
// 开始画边框
ctx.beginPath()
ctx.lineWidth = cellBorder
if ((value & 上) === 上) {
ctx.moveTo(leftTopX, leftTopY)
ctx.lineTo(leftTopX + cellSize, leftTopY)
}
if ((value & 左) === 左) {
ctx.moveTo(leftTopX, leftTopY)
ctx.lineTo(leftTopX, leftTopY + cellSize)
}
if ((value & 下) === 下) {
ctx.moveTo(leftTopX, leftTopY + cellSize)
ctx.lineTo(leftTopX + cellSize, leftTopY + cellSize)
}
if ((value & 右) === 右) {
ctx.moveTo(leftTopX + cellSize, leftTopY)
ctx.lineTo(leftTopX + cellSize, leftTopY + cellSize)
}
ctx.closePath()
ctx.strokeStyle = '#000000'
ctx.stroke()
}
}
indexToPos (i) {
let x = i % this.width
let y = Math.floor(i / this.width)
return { x, y }
}
}
每一个格子用 Cell 来表示，x、y 是坐标，而 value 值代表了格子四面墙的开闭状态，通过一些位运算来实现，0b1111 代表全部墙均为闭合，0b0000 代表全部墙都打开。C语言程序员通常会特别喜欢玩弄bit。
build 函数负责初始化整个迷宫，把所有格子默认设置为四面墙全部闭合。
renderCanvas 函数很长，但是作用很简单，就是把这个迷宫渲染到一个 canvas 标签。
然后把代码和之前的解迷宫的代码稍微结合一下：
https://codesandbox.io/s/maze-vite-9-1h3qh?file=/src/App.vue
随机破墙
我们从 (0, 0) 出发（即左上角），随机选择可以破的墙，然后破墙到达下一个格子，之后再次随机选一堵墙来破，一直持续下去，直到遇上无墙可破的情况。
部分关键的代码：
class MazeGanerator {
static 上 = 0b1000
static 左 = 0b0100
static 下 = 0b0010
static 右 = 0b0001
/**
* 破墙循环
* @param {Function} cb
*/
async breakWall (cb = async () => {}) {
let { nodes } = this
let current = nodes[0]
for (;;) {
let breakDirection = this.getRandomNext(current)
await cb(current)
if (breakDirection !== null) {
current.value ^= breakDirection.value
breakDirection.nextNode.value ^= breakDirection.oppositeValue
current = breakDirection.nextNode
} else {
break
}
}
}
/**
* 获取周围可以破的墙
* @param {Cell} node
* @returns
*/
getNextDirections (node) {
const { 上, 左, 下, 右 } = MazeGanerator
let { x, y, value } = node
return [ 上, 左, 下, 右 ]
.filter(direction => (value & direction) === direction)
.map(direction => {
let nextX
let nextY
let oppositeValue
if (direction === 上) {
oppositeValue = 下
nextX = x
nextY = y - 1
} else if (direction === 左) {
oppositeValue = 右
nextX = x - 1
nextY = y
} else if (direction === 下) {
oppositeValue = 上
nextX = x
nextY = y + 1
} else if (direction === 右) {
oppositeValue = 左
nextX = x + 1
nextY = y
}
// 边界判断
if (nextX >= 0 && nextY >= 0 && nextX < this.width && nextY < this.height) {
return { x: nextX, y: nextY, value: direction, oppositeValue }
} else {
return null
}
})
.filter(item => item !== null)
}
/**
* 随机获取周围可以破的墙
* @param {Cell} node
* @returns
*/
getRandomNext (node) {
let nextDirections = this.getNextDirections(node)
if (nextDirections.length > 0) {
let nextDirection = nextDirections[this.getRandomInt(0, nextDirections.length - 1)]
let nextNode = this.nodes[this.posToIndex(nextDirection.x, nextDirection.y)]
return {
nextNode,
value: nextDirection.value,
oppositeValue: nextDirection.oppositeValue
}
} else {
return null
}
}
}
完整代码：https://codesandbox.io/s/maze-vite-10-qoq0h?file=/src/maze.js
主要逻辑其实只是 breakWall 方法，其他的都是一些繁琐的边界判断之类的。破墙的时候注意要破两面墙，一面是当前方块的墙，一面是下一个方块的墙，方向刚好相反。
下面是运行起来的一些结果：
可以看到效果不太理想，主要的问题是通行区域过于集中，以至于经常出现大块空地。如果把迷宫规模扩大，明显发现很多区域的墙都没有破，处于完全封闭状态。
随机传送到任意方格进行破墙，应该可以解决通行区域过于集中的问题，尝试修改代码：
async breakWall (cb = async () => {}) {
let { nodes } = this
let current = nodes[0]
for (;;) {
let breakDirection = this.getRandomNext(current)
await cb(current)
if (breakDirection !== null) {
current.value ^= breakDirection.value
breakDirection.nextNode.value ^= breakDirection.oppositeValue
// 改为随机选取下一个方格
current = nodes[this.getRandomInt(0, nodes.length - 1)]
} else {
break
}
}
}
运行结果：
通行区域确实分散了开来，但仍然存在很多无法到达的封闭方格。仔细想想，根本原因是因为整个迭代过程结束后，依然存在从未到达过的方格，所以需要想办法让每一个方格都至少到达一次，至少打破一面墙。
准备一个 nodesShuffle 数组，里面的元素和 nodes 是一样的，但是使用 洗牌算法 去打乱顺序，然后在 breakWall 里面迭代这个洗牌后的数组即可：
/**
* 破墙循环
* @param {Function} cb
*/
async breakWall (cb = async () => {}) {
let { nodesShuffle } = this
let { length } = nodesShuffle
for (let i = 0; i < length; i++) {
let current = nodesShuffle[i]
let breakDirection = this.getRandomNext(current)
await cb(current)
if (breakDirection !== null) {
current.value ^= breakDirection.value
breakDirection.nextNode.value ^= breakDirection.oppositeValue
}
}
}
完整代码：https://codesandbox.io/s/maze-vite-11-jfcum?file=/src/App.vue
运行效果：
看起来算是有模有样了，但是仔细观察，存在互相隔绝的大区域，比如：
A、B 区域互相无法到达，有没有办法可以使得迷宫中任意两个方格，都有且只有一条通达道路呢？答案是肯定的。关键点在于，每回迭代不能从所有的方格里面随意选，而是必须要从已被破过墙的方格里面选择，这样就能够彻底杜绝孤立区域。
/**
* 破墙循环
* @param {Function} cb
*/
async breakWall (cb = async () => {}) {
let { nodes, nodesChecked } = this
nodesChecked.push(nodes[0])
nodes[0].checked = true
for (; nodesChecked.length > 0;) {
let randomIndex = this.getRandomInt(0, nodesChecked.length - 1)
let current = nodesChecked[randomIndex]
let breakDirection = this.getRandomNext(current)
await cb(current)
if (breakDirection !== null) {
current.value ^= breakDirection.value
let { nextNode } = breakDirection
nextNode.value ^= breakDirection.oppositeValue
nextNode.checked = true
nodesChecked.push(nextNode)
} else {
nodesChecked.splice(randomIndex, 1)
}
}
}
/**
* 获取周围可以破的墙
* @param {Cell} node
* @returns
*/
getNextDirections (node) {
const { 上, 左, 下, 右 } = MazeGanerator
let { x, y, value } = node
return [ 上, 左, 下, 右 ]
.filter(direction => (value & direction) === direction)
.map(direction => {
let nextX
let nextY
let oppositeValue
if (direction === 上) {
oppositeValue = 下
nextX = x
nextY = y - 1
} else if (direction === 左) {
oppositeValue = 右
nextX = x - 1
nextY = y
} else if (direction === 下) {
oppositeValue = 上
nextX = x
nextY = y + 1
} else if (direction === 右) {
oppositeValue = 左
nextX = x + 1
nextY = y
}
// 边界判断
if (nextX >= 0 && nextY >= 0 && nextX < this.width && nextY < this.height) {
let nextNode = this.nodes[this.posToIndex(nextX, nextY)]
return { x: nextX, y: nextY, value: direction, oppositeValue, nextNode }
} else {
return null
}
})
.filter(item => item !== null && item.nextNode.checked === false)
}
把被破过墙的方格使用 checked 属性标记起来，并且放入数组 nodesChecked，每次就从这个数组随机取下一个方格。getNextDirections 添加一个过滤条件，就是如果某面墙对着的方格曾经被破过墙，就不能选这面墙了。如果一个方格已经无墙可破，则把他从 nodesChecked 中删除，减少迭代次数。
完整代码：https://codesandbox.io/s/maze-vite-12-28isc?file=/src/maze.js:9899-10297
运行效果：
回溯法
现在所有区域都联通了，不再有孤立区域，但是却存在一些非常难看的死胡同，比如：
这些死胡同实在太浅了，如何让迷宫拥有良好的战略纵深呢？答案就是结合我们的第一个方案，先不要使用随机传送法，而是沿路往前推进，直至遇到无墙可破的情况，再从 nodesChecked 出栈一个 node，把他当作新的起点继续前进，直到 nodesChecked 为空即可：
async breakWall (cb = async () => {}) {
let { nodes, nodesChecked } = this
nodesChecked.push(nodes[0])
nodes[0].checked = true
let current = nodes[0]
for (; nodesChecked.length > 0;) {
let breakDirection = this.getRandomNext(current)
await cb(current)
if (breakDirection !== null) {
current.value ^= breakDirection.value
let { nextNode } = breakDirection
nextNode.value ^= breakDirection.oppositeValue
nextNode.checked = true
nodesChecked.push(nextNode)
current = nextNode
} else {
current = nodesChecked.pop()
}
}
}
效果很不错，这种方法可以称为回溯法，看起来也确实像。
这种方法的缺点也是显而易见，随着迷宫规模的增大，需要的迭代次数和数组空间也会增大。
最后，加入一些必要的可定义参数，最终成品：https://codesandbox.io/s/maze-vite-13-j9uqv?file=/src/maze.js:10050-10503
墙壁建造者
从现实的角度考虑，没有人在建造迷宫时先把所有的墙造好，然后再把他们凿穿。所以是否有一种算法是通过添加墙壁来实现生成迷宫的呢？答案是有的。
一开始，整个迷宫看起来是这样的：
什么也没有，所以接下来要往里面添加墙壁？是，也不是，我们要换一种思路，不是添加墙壁，而是将整个迷宫一分为二：
接着在分界线上砸出一个缺口：
然后在剩下的区域里面再做同样的事情
不断对区域进行切分，直到区域大小达到 1 为止。
class Area {
constructor (x, y, width, height) {
this.x = x
this.y = y
this.width = width
this.height = height
}
}
async createWall (cb = async () => {}) {
let { width, height } = this
let areas = this.areas = [ new Area(0, 0, width, height) ]
for (;;) {
let index = areas.findIndex(area => area.width > 1 || area.height > 1)
if (index >= 0) {
let area = areas[index]
let [ areaA, areaB ] = this.splitArea(area)
areas.splice(index, 1)
areas.push(areaA)
areas.push(areaB)
await cb()
} else {
break
}
}
}
splitArea (area) {
let { x, y, width, height } = area
let xA, xB, yA, yB, widthA, widthB, heightA, heightB // A、B 是两个分裂后的区域
if ( width > height) { // 竖切
let splitLength = Math.floor(width / 2) // 对半分
xA = x
yA = y
widthA = splitLength
heightA = height
xB = x + splitLength
yB = y
widthB = width - splitLength
heightB = height
let yRandom = this.getRandomInt(y, y + height - 1)
let gap = { x: xB, y: yRandom, direction: 'horizontal' }
this.gaps.push(gap)
} else { // 横切
let splitLength = Math.floor(height / 2) // 对半分
xA = x
yA = y
widthA = width
heightA = splitLength
xB = x
yB = y + splitLength
widthB = width
heightB = height - splitLength
let xRandom = this.getRandomInt(x, x + width - 1)
let gap = { x: xRandom, y: yB, direction: 'vertical' }
this.gaps.push(gap)
}
let areaA = new Area(xA, yA, widthA, heightA)
let areaB = new Area(xB, yB, widthB, heightB)
return [ areaA, areaB ]
}
完整代码：https://codesandbox.io/s/maze-vite-14-eggfr?file=/src/maze.js:12878-13569
canvas 的渲染代码这里我就不贴了，这里关键就是把 Cell 改为了 Area，用来表示一个任意大小的矩形范围，然后把缺口存储到另外一个数组 gaps 中，渲染的时候先渲染 Area，再渲染 gaps 就行。
结果：
感觉效果不太行，尝试不要每次都对半分，而是随机选择切割点，只需要改动 splitLength 的赋值语句即可：
splitArea (area) {
let { x, y, width, height } = area
let xA, xB, yA, yB, widthA, widthB, heightA, heightB // A、B 是两个分裂后的区域
if ( width > height) { // 竖切
let splitLength = this.getRandomInt(1, width - 1) // 随机切割
xA = x
yA = y
widthA = splitLength
heightA = height
xB = x + splitLength
yB = y
widthB = width - splitLength
heightB = height
let yRandom = this.getRandomInt(y, y + height - 1)
let gap = { x: xB, y: yRandom, direction: 'horizontal' }
this.gaps.push(gap)
} else { // 横切
let splitLength = this.getRandomInt(1, height - 1) // 随机切割
xA = x
yA = y
widthA = width
heightA = splitLength
xB = x
yB = y + splitLength
widthB = width
heightB = height - splitLength
let xRandom = this.getRandomInt(x, x + width - 1)
let gap = { x: xRandom, y: yB, direction: 'vertical' }
this.gaps.push(gap)
}
let areaA = new Area(xA, yA, widthA, heightA)
let areaB = new Area(xB, yB, widthB, heightB)
return [ areaA, areaB ]
}
效果：https://codesandbox.io/s/maze-vite-15-i7oik?file=/src/maze.js
稍微有所改观，至少看起来不会是那种规规整整的“田”字型了，但无论如何，都没法和回溯法的效果相提并论，我暂时还没能想到更加好的方法，如果大家有有趣的想法，请务必在评论中分享。