【Javascript + Vue】实现随机生成迷宫图片

成品预览：https://codesandbox.io/s/maze-vite-15-i7oik?file=http://www.likecs.com/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=http://www.likecs.com/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=http://www.likecs.com/src/maze.js