[Javascript + Vue] random generation of maze pictures

The Last Gentleman 2021-06-23 18:42:40
javascript vue random generation maze


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 8x8 The maze of :

image

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 :

https://codesandbox.io/s/maze-vite-9-1h3qh?file=/src/App.vue

image

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 :

image

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 :

image

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 :

image

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

image

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 :

image

backtracking

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

image

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

image

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

image

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 :

image

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 :

image

And then there's a gap in the line of demarcation :

image

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

image

image

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 :

image

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

image

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 /

版权声明
本文为[The Last Gentleman ]所创,转载请带上原文链接,感谢
https://javamana.com/2021/06/20210623182658868w.html

  1. 【计算机网络 12(1),尚学堂马士兵Java视频教程
  2. 【程序猿历程,史上最全的Java面试题集锦在这里
  3. 【程序猿历程(1),Javaweb视频教程百度云
  4. Notes on MySQL 45 lectures (1-7)
  5. [computer network 12 (1), Shang Xuetang Ma soldier java video tutorial
  6. The most complete collection of Java interview questions in history is here
  7. [process of program ape (1), JavaWeb video tutorial, baidu cloud
  8. Notes on MySQL 45 lectures (1-7)
  9. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  10. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  11. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  12. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  13. 【递归,Java传智播客笔记
  14. [recursion, Java intelligence podcast notes
  15. [adhere to painting for 386 days] the beginning of spring of 24 solar terms
  16. K8S系列第八篇(Service、EndPoints以及高可用kubeadm部署)
  17. K8s Series Part 8 (service, endpoints and high availability kubeadm deployment)
  18. 【重识 HTML (3),350道Java面试真题分享
  19. 【重识 HTML (2),Java并发编程必会的多线程你竟然还不会
  20. 【重识 HTML (1),二本Java小菜鸟4面字节跳动被秒成渣渣
  21. [re recognize HTML (3) and share 350 real Java interview questions
  22. [re recognize HTML (2). Multithreading is a must for Java Concurrent Programming. How dare you not
  23. [re recognize HTML (1), two Java rookies' 4-sided bytes beat and become slag in seconds
  24. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  25. RPC 1: how to develop RPC framework from scratch
  26. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  27. RPC 1: how to develop RPC framework from scratch
  28. 一次性捋清楚吧,对乱糟糟的,Spring事务扩展机制
  29. 一文彻底弄懂如何选择抽象类还是接口,连续四年百度Java岗必问面试题
  30. Redis常用命令
  31. 一双拖鞋引发的血案,狂神说Java系列笔记
  32. 一、mysql基础安装
  33. 一位程序员的独白:尽管我一生坎坷,Java框架面试基础
  34. Clear it all at once. For the messy, spring transaction extension mechanism
  35. A thorough understanding of how to choose abstract classes or interfaces, baidu Java post must ask interview questions for four consecutive years
  36. Redis common commands
  37. A pair of slippers triggered the murder, crazy God said java series notes
  38. 1、 MySQL basic installation
  39. Monologue of a programmer: despite my ups and downs in my life, Java framework is the foundation of interview
  40. 【大厂面试】三面三问Spring循环依赖,请一定要把这篇看完(建议收藏)
  41. 一线互联网企业中,springboot入门项目
  42. 一篇文带你入门SSM框架Spring开发,帮你快速拿Offer
  43. 【面试资料】Java全集、微服务、大数据、数据结构与算法、机器学习知识最全总结,283页pdf
  44. 【leetcode刷题】24.数组中重复的数字——Java版
  45. 【leetcode刷题】23.对称二叉树——Java版
  46. 【leetcode刷题】22.二叉树的中序遍历——Java版
  47. 【leetcode刷题】21.三数之和——Java版
  48. 【leetcode刷题】20.最长回文子串——Java版
  49. 【leetcode刷题】19.回文链表——Java版
  50. 【leetcode刷题】18.反转链表——Java版
  51. 【leetcode刷题】17.相交链表——Java&python版
  52. 【leetcode刷题】16.环形链表——Java版
  53. 【leetcode刷题】15.汉明距离——Java版
  54. 【leetcode刷题】14.找到所有数组中消失的数字——Java版
  55. 【leetcode刷题】13.比特位计数——Java版
  56. oracle控制用户权限命令
  57. 三年Java开发,继阿里,鲁班二期Java架构师
  58. Oracle必须要启动的服务
  59. 万字长文!深入剖析HashMap,Java基础笔试题大全带答案
  60. 一问Kafka就心慌?我却凭着这份,图灵学院vip课程百度云