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

2021年6月24日 31点热度 0条评论 来源: 最后的绅士

前言

成品预览: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/迷宫生成/

    原文作者:最后的绅士
    原文地址: https://www.cnblogs.com/judgeou/p/14893560.html
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。