• 周日. 11月 27th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

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

[db:作者]

1月 6, 2022

前言

成品预览:https://codesandbox.io/s/maze-vite-15-i7oik?file=/src/maze.js

不久前写了一篇文章介绍了如何解迷宫:https://www.cnblogs.com/judgeou/p/14805429.html

这回来说说怎么生成迷宫。

解迷宫通常是先把原始数据(图片)转换为特定数据结构,然后对其执行一些算法,得出结果。而生成迷宫,理所应当的是先使用合适的算法生成数据结构,再把这个数据结构渲染出来:

  • 解迷宫:输入 -> 数据结构 -> 算法处理
  • 生成迷宫:算法处理 -> 数据结构 -> 输出

原初形态

这是一个 8×8 的迷宫:

image

每一个房间都无法到达其他房间,而我们要做的,就是从里面挑选一些格子,然后打掉他的某些墙壁,让他与隔壁房间联通。

下面来设计它的数据结构:

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 标签。

然后把代码和之前的解迷宫的代码稍微结合一下:

image

随机破墙

我们从 (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 方法,其他的都是一些繁琐的边界判断之类的。破墙的时候注意要破两面墙,一面是当前方块的墙,一面是下一个方块的墙,方向刚好相反。

下面是运行起来的一些结果:

image

可以看到效果不太理想,主要的问题是通行区域过于集中,以至于经常出现大块空地。如果把迷宫规模扩大,明显发现很多区域的墙都没有破,处于完全封闭状态。

随机传送到任意方格进行破墙,应该可以解决通行区域过于集中的问题,尝试修改代码:

 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
}
}
}

运行结果:

image

通行区域确实分散了开来,但仍然存在很多无法到达的封闭方格。仔细想想,根本原因是因为整个迭代过程结束后,依然存在从未到达过的方格,所以需要想办法让每一个方格都至少到达一次,至少打破一面墙。

准备一个 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

运行效果:

image

看起来算是有模有样了,但是仔细观察,存在互相隔绝的大区域,比如:

image

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

运行效果:

image

回溯法

现在所有区域都联通了,不再有孤立区域,但是却存在一些非常难看的死胡同,比如:

image

这些死胡同实在太浅了,如何让迷宫拥有良好的战略纵深呢?答案就是结合我们的第一个方案,先不要使用随机传送法,而是沿路往前推进,直至遇到无墙可破的情况,再从 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()
}
}
}

image

效果很不错,这种方法可以称为回溯法,看起来也确实像。

这种方法的缺点也是显而易见,随着迷宫规模的增大,需要的迭代次数和数组空间也会增大。

最后,加入一些必要的可定义参数,最终成品:https://codesandbox.io/s/maze-vite-13-j9uqv?file=/src/maze.js:10050-10503

image

墙壁建造者

从现实的角度考虑,没有人在建造迷宫时先把所有的墙造好,然后再把他们凿穿。所以是否有一种算法是通过添加墙壁来实现生成迷宫的呢?答案是有的。

一开始,整个迷宫看起来是这样的:

image

什么也没有,所以接下来要往里面添加墙壁?是,也不是,我们要换一种思路,不是添加墙壁,而是将整个迷宫一分为二:

image

接着在分界线上砸出一个缺口:

image

然后在剩下的区域里面再做同样的事情

image

image

不断对区域进行切分,直到区域大小达到 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 就行。

结果:

image

感觉效果不太行,尝试不要每次都对半分,而是随机选择切割点,只需要改动 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

image

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

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

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注