## Preface

Preview of finished products ：https://codesandbox.io/s/maze-vite-15-i7oik?file=/src/maze.js

Not long ago, I wrote an article about how to solve maze ：https://www.cnblogs.com/judgeou/p/14805429.html

Let’s talk about how to create a maze .

Solving a maze usually starts with the original data （ picture ） Convert to a specific data structure , And then perform some algorithms on it , The results of . And create a maze , It is reasonable to use the appropriate algorithm to generate the data structure first , And then render this data structure ：

**Solving maze**： Input -> data structure -> Algorithm to deal with**Create mazes**： Algorithm to deal with -> data structure -> Output

## The original form

This is a 8×8 The maze of ：

Each room has no access to the other , And what we have to do , It’s just to pick some lattices from the inside , And then smash some of his walls , Connect him to the next room .

Let’s design its data structure ：

```
class Cell {
constructor (x, y, value) {
this.x = x
this.y = y
this.value = value
}
}
class MazeGanerator {
static On = 0b1000
static Left = 0b0100
static Next = 0b0010
static Right = 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 individual bit Represents the opening and closing state of the upper, lower, left and right walls ,0： open ,1： close
}
}
/**
*
* @param {HTMLCanvasElement} canvas
*/
renderCanvas (canvas) {
const { On , Left , Next , Right } = 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
// Start drawing borders
ctx.beginPath()
ctx.lineWidth = cellBorder
if ((value & On ) === On ) {
ctx.moveTo(leftTopX, leftTopY)
ctx.lineTo(leftTopX + cellSize, leftTopY)
}
if ((value & Left ) === Left ) {
ctx.moveTo(leftTopX, leftTopY)
ctx.lineTo(leftTopX, leftTopY + cellSize)
}
if ((value & Next ) === Next ) {
ctx.moveTo(leftTopX, leftTopY + cellSize)
ctx.lineTo(leftTopX + cellSize, leftTopY + cellSize)
}
if ((value & Right ) === Right ) {
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 }
}
}
```

Every grid uses Cell To express ,x、y Is the coordinate , and value The value represents the open and closed state of the four walls of the lattice , By some bit operations ,0b1111 Represents that all walls are closed ,0b0000 It means all the walls are open .C Language programmers usually like to play with bit.

build Function is responsible for initializing the entire maze , The default setting of all grids is that all four walls are closed .

renderCanvas It’s a long function , But the effect is simple , Is to render this maze into a canvas label .

Then combine the code with the previous maze solving code a little bit ：

## Random broken walls

We from (0, 0) set out （ Upper left corner ）, Randomly choose walls that can be broken , Then break the wall to the next grid , Then randomly choose another wall to break , Keep going on , Until there’s no wall to break .

Part of the key code ：

```
class MazeGanerator {
static On = 0b1000
static Left = 0b0100
static Next = 0b0010
static Right = 0b0001
/**
* Broken wall cycle
* @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
}
}
}
/**
* Get walls that can be broken around
* @param {Cell} node
* @returns
*/
getNextDirections (node) {
const { On , Left , Next , Right } = MazeGanerator
let { x, y, value } = node
return [ On , Left , Next , Right ]
.filter(direction => (value & direction) === direction)
.map(direction => {
let nextX
let nextY
let oppositeValue
if (direction === On ) {
oppositeValue = Next
nextX = x
nextY = y - 1
} else if (direction === Left ) {
oppositeValue = Right
nextX = x - 1
nextY = y
} else if (direction === Next ) {
oppositeValue = On
nextX = x
nextY = y + 1
} else if (direction === Right ) {
oppositeValue = Left
nextX = x + 1
nextY = y
}
// Boundary judgment
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)
}
/**
* Random access to broken walls around
* @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
}
}
}
```

Complete code ：https://codesandbox.io/s/maze-vite-10-qoq0h?file=/src/maze.js

The main logic is just breakWall Method , The others are complicated boundary judgment and so on . When you break a wall, you should break two walls , One side is the wall of the current square , One side is the wall of the next square , In the opposite direction .

Here are some of the results of running ：

We can see that the effect is not ideal , The main problem is that the traffic area is too concentrated , So much so that there’s a lot of open space . If we expand the maze , It’s obvious that the walls in many areas are not broken , In a completely closed state .

Randomly send it to any grid to break the wall , It should be able to solve the problem of over concentration of traffic areas , Try modifying the code ：

```
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
// Instead, randomly select the next grid
current = nodes[this.getRandomInt(0, nodes.length - 1)]
} else {
break
}
}
}
```

Running results ：

The traffic area is really scattered , But there are still many inaccessible closed squares . Think carefully , The root cause is that at the end of the iteration , There are still squares that have never been reached , So we need to find a way to make every square arrive at least once , Break at least one wall .

Prepare one nodesShuffle Array , The elements and nodes It’s the same , But use Shuffle algorithm To get out of order , And then in breakWall Iterate through the shuffled array ：

```
/**
* Broken wall cycle
* @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
}
}
}
```

Complete code ：https://codesandbox.io/s/maze-vite-11-jfcum?file=/src/App.vue

Running effect ：

It looks like a model , But watch carefully , There are large isolated areas , such as ：

A、B Areas are inaccessible to each other , Is there any way to make any two squares in the maze , There is only one access road ？ The answer is yes . The point is that , You can’t choose from all the squares in each iteration , But we have to choose from the squares that have been broken through the wall , In this way, isolated areas can be completely eliminated .

```
/**
* Broken wall cycle
* @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)
}
}
}
/**
* Get walls that can be broken around
* @param {Cell} node
* @returns
*/
getNextDirections (node) {
const { On , Left , Next , Right } = MazeGanerator
let { x, y, value } = node
return [ On , Left , Next , Right ]
.filter(direction => (value & direction) === direction)
.map(direction => {
let nextX
let nextY
let oppositeValue
if (direction === On ) {
oppositeValue = Next
nextX = x
nextY = y - 1
} else if (direction === Left ) {
oppositeValue = Right
nextX = x - 1
nextY = y
} else if (direction === Next ) {
oppositeValue = On
nextX = x
nextY = y + 1
} else if (direction === Right ) {
oppositeValue = Left
nextX = x + 1
nextY = y
}
// Boundary judgment
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)
}
```

Use the squares that have been broken through the wall checked Attribute tag , And put it in an array nodesChecked, Take a random box from this array each time .getNextDirections Add a filter , That is, if the square opposite a wall has ever been broken through the wall , You can’t choose this wall . If a square has no walls to break , Take him from nodesChecked Delete in , Reduce the number of iterations .

Complete code ：https://codesandbox.io/s/maze-vite-12-28isc?file=/src/maze.js:9899-10297

Running effect ：

## backtracking

Now all the regions are connected , There are no more isolated areas , But there are some very ugly dead ends , such as ：

These dead ends are too shallow , How to make maze have good strategic depth ？ The answer is to combine our first plan , Don’t use random transmission yet , It’s moving along the road , Until there is no wall to break , Again from nodesChecked One out of the stack node, Take him as a new starting point and move on , until nodesChecked If it is empty, you can ：

```
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()
}
}
}
```

Very good results , This method can be called backtracking , It does look like .

The disadvantages of this approach are also obvious , As the size of the maze increases , The number of iterations and array space required will also increase .

Last , Add some necessary definable parameters , The final product ：https://codesandbox.io/s/maze-vite-13-j9uqv?file=/src/maze.js:10050-10503

## The wall builder

From a realistic point of view , No one builds a maze with all the walls first , And then chisel them through . So is there an algorithm to generate mazes by adding walls ？ The answer is yes .

In limine , The whole maze looks like this ：

nothing in the world , So the next step is to add walls to it ？ yes , Neither , We need to think differently , Not adding walls , It’s about splitting the maze in two ：

And then there’s a gap in the line of demarcation ：

And then do the same thing in the rest of the area

Constantly segmenting regions , Until the size of the area reaches 1 until .

```
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 It's two separate regions
if ( width > height) { // Vertical cutting
let splitLength = Math.floor(width / 2) // In half
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 { // Crosscut
let splitLength = Math.floor(height / 2) // In half
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 ]
}
```

Complete code ：https://codesandbox.io/s/maze-vite-14-eggfr?file=/src/maze.js:12878-13569

canvas I won’t post the rendering code here , The key here is to Cell Change it to Area, Used to represent a rectangular range of any size , Then store the gap in another array gaps in , When rendering, render first Area, To render gaps Just go .

result ：

I don’t think the effect is very good , Try not to split every time , It’s a random selection of cut points , Just change splitLength The assignment statement of ：

```
splitArea (area) {
let { x, y, width, height } = area
let xA, xB, yA, yB, widthA, widthB, heightA, heightB // A、B It's two separate regions
if ( width > height) { // Vertical cutting
let splitLength = this.getRandomInt(1, width - 1) // Cut at random
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 { // Crosscut
let splitLength = this.getRandomInt(1, height - 1) // Cut at random
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 ]
}
```

effect ：https://codesandbox.io/s/maze-vite-15-i7oik?file=/src/maze.js

A little bit better , At least it doesn’t seem to be that kind of neat “ field ” The shape of the characters has changed , But anyway , It can’t be compared with the effect of backtracking , I haven’t come up with a better way yet , If you have interesting ideas , Be sure to share in the comments .

The final source code ：https://gitee.com/judgeou/maze-vite/tree/ Maze generation /