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

前言

成品预览：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

稍微有所改观，至少看起来不会是那种规规整整的“田”字型了，但无论如何，都没法和回溯法的效果相提并论，我暂时还没能想到更加好的方法，如果大家有有趣的想法，请务必在评论中分享。

最终的源代码：https://gitee.com/judgeou/maze-vite/tree/迷宫生成/