Javascript combined with Vue to achieve automatic path finding for any maze image

Preface

You can experience the final effect directly: https://maze-vite.vercel.app/

Before pathfinding:

After pathfinding, a red path is automatically generated on the image, and the blue area is the explored area:

Here I deliberately used the phone to shoot at an angle, just to show that the program can fully handle the maze pictures taken by the phone in reality.

I plan to write the entire program using Vue 3 + Vite, but in fact it doesn’t matter whether Vue is used or not. It will not involve complex interfaces, and it is completely possible to use other frameworks or even no framework at all.

Two-dimensional array, one way

I said we should start from scratch, so let's start with a very simple maze.

To us humans, this maze is very simple, with only one obvious path. But it still takes a little effort for a computer to solve such a maze.

A two-dimensional array is a good way to represent this maze:

const m = [
  [1, 1, 0, 0, 0],
  [0, 1, 1, 1, 0],
  [0, 0, 0, 1, 0],
  [0, 0, 0, 1, 1]
]

1 represents a grid that can be walked, and 0 represents a grid that cannot be walked. Each grid can be represented by [x, y]. For example, the starting point is [0, 0] and the end point is [3, 4].

Then there should be a function like this: function function solveMaze (matrix, begin, end) {//...} , matrix is ​​a two-dimensional array describing the maze, begin is the starting point, end is the end point, and the final return value is an ordered set, each element is a grid, representing the correct route trajectory.

The strategy we are going to use here is very simple. Start from the starting point, look around to see which grids are passable (you cannot walk diagonally), then move to this grid, and then repeat the above steps until you reach the end grid. Note that you also need to record the grid from the previous step and exclude it to avoid going back. See the following code for details:

// maze.js

function getPoint(m, x, y) {
  if (x >= 0 && y >= 0 && x < m.length && y < m[x].length) {
    return m[x][y]
  } else {
    return 0
  }
}

function getNextPoint(m, current, lastPoint) {
  let [x, y] = current
  let nextPoint = [
    [x - 1, y], [x + 1, y], [x, y - 1], [x, y + 1]
  ].find(p => {
    let r1 = getPoint(m, p[0], p[1]) > 0
    let r2 = !isSamePoint(p, lastPoint)
    return r1 && r2
  })
  return nextPoint
}

function isSamePoint(p1, p2) {
  return p1[0] === p2[0] && p1[1] === p2[1]
}

function solveMaze (matrix, begin, end) {
  let path = []

  // Current point let current = begin
  path.push(current)

  // The path we walked last time let lastPoint = begin

  // Pick a random point to go while (1) {
    if (isSamePoint(current, end)) {
      break
    }

    let validPoint = getNextPoint(matrix, current, lastPoint)

    path.push(validPoint)
    lastPoint = current
    current = validPoint
  }
  return path
}

const m = [
  [1, 1, 0, 0, 0],
  [0, 1, 1, 1, 0],
  [0, 0, 0, 1, 0],
  [0, 0, 0, 1, 1]
]

console.log(
  solveMaze(m, [0, 0], [3, 4])
)

getNextPoint gets the next traversable grid, solveMaze gets the final traversable path, and the console output is:

These coordinates are the final walking trajectory, and they appear to be correct.

Mapping basic interface

In order to facilitate testing and observation, we need to map our data structure to the web page.

// maze.js
// ...

// Export the solveMaze function and let the Vue component call export {
  solveMaze
}

<template>
  <div>
    <div class="div-matrix">
      <div v-for="(row, x) in matrix" :key="x">
        <div class="cell" 
          :class="{ black: p <= 0, path: isPath(x, y) }"
          v-for="(p, y) in row" :key="y" :style="{ left: `${y * 2.5}em`, top: `${x * 2.5}em` }">
          {{ begin[0] === x && begin[1] === y ? 'B' : '' }}
          {{ end[0] === x && end[1] === y ? 'E' : '' }}
        </div>
      </div>
    </div>
  </div>
</template>

<script>
import { solveMaze } from './maze'

export default {
  data () {
    return {
      begin: [0, 0],
      end: [3, 4],
      matrix: [],
      paths: []
    }
  },
  methods: {
    isPath(x, y) {
      const p = this.paths.find(path => path[0] === x && path[1] === y)
      return p
    }
  },
  created () {
    const m = this.matrix = [
      [1, 1, 0, 0, 0],
      [0, 1, 1, 1, 0],
      [0, 0, 0, 1, 0],
      [0, 0, 0, 1, 1]
    ]
    this.paths = solveMaze(m, this.begin, this.end)
  }
}
</script>

<style>
.top {
  margin-bottom: 1em;
}
.div-matrix {
  position: relative;
}
.cell {
  border: 1px black solid;
  width: 2em;
  height: 2em;
  position:absolute;
  text-align: center;
}
.cell.path {
  border: 1px red solid;
}
.black {
  background: black;
}
</style>

Final result:

In fact, the corresponding div is generated through the two-dimensional array matrix, and the element value in the array determines the black and white. The paths array stores the resulting paths, and the paths are marked with a red border. This will make it easier to view the test results later.

Breadth-first, blanket search

Take a look at the following maze:

const m = this.matrix = [
  [1, 1, 0, 0, 0],
  [1, 1, 1, 1, 1],
  [0, 1, 0, 1, 0],
  [0, 1, 0, 1, 1]
]

If you apply it to the code above, you will find that the page is stuck. This is because the maze contains forks, causing the algorithm to go in circles. We need some means to remember the path we have taken so that we won't have to walk it again. The method is not difficult. We just need to put the grids that can be walked at the moment into a queue. Then, we need to keep doing the same thing to the grids in the queue until we reach the end grid.

In order to facilitate our algorithm processing, we need to use a new data structure to express it, which is the graph structure.

The graph structure is very similar to a linked list, the biggest difference is that each node can have multiple pointers pointing to different nodes.

At the same time, reduce the dimensionality of the two-dimensional array to one dimension:

const m = [
  1, 1, 0, 0, 0,
  1, 1, 1, 1, 1,
  0, 1, 0, 1, 0,
  0, 1, 0, 1, 1
]

Although this access is not so direct, it only requires one addressing, and copying and transferring is much more convenient than a two-dimensional array.

Then create a Node class to represent the node and a NodeGraph class to represent the entire graph structure.

class Node {
  constructor (x, y, value) {
    this.x = x
    this.y = y
    this.value = value
    this.checked = false
    this.nearNodes = []
  }
}

class NodeGraph {
  constructor (matrix, width, height) {
    this.nodes = []
    this.matrix = matrix
    this.width = width
    this.height = height
  }

  buildNodeGraph () {
    let { width, height } = this
    
    for (let y = 0; y < height; y++) {
      for (let x = 0; x < width; x++) {
        let node = this.getNode(x, y)
  
        let up = this.getNode(x, y - 1)
        let down = this.getNode(x, y + 1)
        let left = this.getNode(x - 1, y)
        let right = this.getNode(x + 1, y)
        node.nearNodes = [ up, down, left, right].filter(node ​​=> node && node.value === 1)
      }
    }
  }

  getNode (x, y) {
    let { nodes, width, matrix } = this
    if (x >= 0 && y >= 0) {
      let node = nodes[y * width + x]
      if (!node) {
        let value = matrix[y * width + x]
        if (value !== undefined) {
          node = new Node(x, y, value)
          nodes[y * width + x] = node
        }
      }
      return node
    } else {
      return null
    }
  }
}

buildNodeGraph converts the matrix array into a graph structure. The nearNodes of each node is equivalent to the grid set that can be explored next. Checked indicates whether the node has been explored.

In order to conveniently view the changes in the status of each step, you need to mark the current grid and the grid in the queue on the screen. I will not post the complete code, you can read it at will in codesandbox:

The blue border is the grid in the queue, and the little man is the current grid. It will stop when it reaches the lower right corner.

What we have done now is just to move the little man to the end point smoothly, but how do we get the path we want? The method is to add an additional attribute parent to Node to record the previous Node. When retrieving nearNodes, assign the current node to the parent of each nearNode:

// ...
for (let node of current.nearNodes) {
  if (node.checked === false) {
	node.parent = current
	queue.push(node)
  }
}
// ...

Then just read the parents from the current node and trace back one by one:

function buildPath (endNode) {
  let path = []
  let node = endNode

  while (node) {
    path.push(node)
    node = node.parent
  }

  return path
}

Effect:

When the little man reaches the end, the red square is the shortest path.

MapEdit

Slightly changing the code will allow us to edit the maze in real time, making testing more convenient.

Operation: Click the square to change the black and white state, hold down alt and click to set a new target point.

Gradually move local variables in solveMaze to the NodeGraph class to make external access more convenient. Note that when the pathfinding is finished, do not end the function, but use a while loop to wait for the new target point to be set:

// ...

    if (equalsNode(current, nodeGraph.endNode)) {
      while (equalsNode(current, nodeGraph.endNode)) {
        await sleep(1000)
      }
      continue
    }
// ...

Optimizing pathfinding algorithms

Imagine this scenario:

The starting point and the end point are in a straight line with no obstacles in between, but this little man is running everywhere and it takes a while to reach the end point. This won’t work and it must be optimized.

Add an attribute endDistance to the Node class to record the distance from each node to the end point. The getDistance function can directly calculate the distance based on the coordinates. This distance does not take into account possible obstacles in the middle, but it is also very useful for route evaluation:

class Node {
  constructor (x, y, value) {
    this.x = x
    this.y = y
    this.value = value
    this.endDistance = 0 // Distance to the end point, ignoring obstacles in the middle this.checked = false
    this.parent = null
    this.nearNodes = []
  }
}

function getDistance(nodeA, nodeB) {
  const x = Math.abs(nodeB.x - nodeA.x)
  const y = Math.abs(nodeB.y - nodeA.y)
  return (x + y)
}

Each time, the Node with the smallest endDistance is taken out from the queue through the popBestNextNode method:

class NodeGraph {
// ...

  popBestNextNode () {
    let { queue } = this
    let bestNode = queue[0]
    let bestNodeIndex = 0
    let { length } = queue

    for (let i = 0; i < length; i++) {
      let node = queue[i]
      if (node.endDistance < bestNode.endDistance) {
        bestNode = node
        bestNodeIndex = i
      }
    }

    queue.splice(bestNodeIndex, 1)
    return bestNode
  }
// ...
}

Since there is endDistance, there must also be beginDistance to record the number of steps taken from the starting point. This value is not calculated directly from the coordinates, but accumulated as it moves forward, so that beginDistance is not an estimate, but an actual value:

// ...
for (let node of current.nearNodes) {
  if (node.checked === false && node.value) {
	node.parent = current
	node.checked = true
	node.endDistance = getDistance(node, nodeGraph.endNode)
	node.beginDistance = current.beginDistance + 1
	node.cost = node.endDistance + node.beginDistance
	nodeGraph.queue.push(node)
  }
}
// ...

Considering that new factors may be added in the future, a cost attribute is directly added to express the cost. Currently, cost is endDistance + beginDistance. The smaller the cost, the higher the priority.

In a situation like this, the little man initially tried to approach from above, but as he continued to move forward, the number of steps he had to take increased, and he decided it would be better to go down, so he gave up the route above.

Now, the villain's actions become more reliable:

Pathfinding an image

Take this random picture I drew as a parameter:

The goal is to get from point B to point E. We only need to read the pixels of this image, convert them into an array based on black and white colors, and put them into the solveMaze function.

To do this, you need an input tag with type="file" to select the image, generate a URL through URL.createObjectURL(File), and then use new Image() to create an img tag, which does not need to be added to the body, and give the url to img.src. Copy it into Canvas via CanvasRenderingContext2D.drawImage(), and then call CanvasRenderingContext2D.getImageData() to get the pixel array.

At this time, we can no longer use div for rendering, because this picture has tens of thousands of pixels, and if there is a div for each pixel, the browser will not be able to handle it, and the pictures will be even larger in the future.

So here we use Canvas for rendering, and arrange three Canvas, one to display the original image of the maze, one to display the explored nodes, and one to display the current shortest path, that is, the nodes in the path array, and then stack these three Canvas together. Finally, we just need to update the last two Canvas in the callback.

Download the picture above to your computer, click the Choose File button to select the picture, and then you can see the effect. You can also choose other pictures, but my starting and ending point coordinates are hard-coded, and the code has not been optimized, so it may be difficult to handle pictures that are too large.

Note: If you encounter cross-domain problems, you will have to upload the images yourself.

Customize your starting point and change your route at any time

The click coordinates can be known by using offsetX and offsetY in the click event, and the coordinates of the start and end points can be saved. Once there is a change, the previous path-finding function is stopped and the current path-finding function is re-executed. Therefore, a judgment needs to be made in the loop to decide whether to exit the function. This is suitable for doing in the callback.

Then provide an input box to freely adjust the number of cycles before updating the screen, so that the speed of path finding can be adjusted.

Processing color images

Preview: https://codesandbox.io/s/maze-vite-8-h845p?file=/src/App.vue (Note that if a cross-domain error occurs, upload the image yourself)

I won’t put iframes anymore. I feel like there are too many of them, making this page quite stuck.

Previously, it was assumed that white pixels were walkable areas. Now, try to use nearby pixels with similar colors as walkable areas, which will have a better effect.

Directly pass the rgba color data into solveMaze, and then calculate the color difference between the adjacent nodes and the current node in the loop. If the difference is too large, it will not be put into the queue.

To separate the channels of an RGBA integer, we can write:

/**
 * Get the RGB value of Node * @param {Node} node 
 * @returns 
 */
function getNodeRGB (node) {
  let { value } = node
  let r = value & 0xFF
  let g = value >> 8 & 0xFF
  let b = value >> 16 & 0xFF
  return [ r, g, b ]
}

The simplest way to find the similarity of RGB colors is to regard the two colors as two points with three-dimensional coordinates and then find their Euclidean distance, but this does not conform to the perception model of the human eye. The detailed method is already available on wiki: https://zh.wikipedia.org/wiki/ColorDifference

The calculations in this area are a bit complicated, and I have written them in color.js.

result:

Pay attention to the colorDiffThreshold in the code. I currently use 2.25. If it is too high, it will cause the wall to pass through. If it is too low, it will easily fail to find the way.

Performance Optimization

After clicking the screen twice, you need to wait a while before the path finding starts. This should consume a lot of CPU. Open the performance analyzer in DevTools to analyze where the most performance is consumed:

Obviously, the solveMaze function takes up most of the time. Expand the Call Tree below:

buildNodeGraph and getNode are the key points of optimization. Open the code and you can directly see the CPU time consumed by each sentence:

if (!node) {...} in line 57 is a simple judgment, but it takes a lot of time. Try changing it to node === undefined , and value no longer needs to be judged. Accessing and reading the nodes array also takes a lot of time. Try initializing it with new Array(length) at the beginning, which should be better. The optimized code:

Looks slightly better.

Performance monitoring during pathfinding:

I found that buildPath is quite time-consuming, which is reasonable. After all, it is called every time through the loop and traverses the entire chain completely. The solution is also simple. Just call it when the final result is output. Based on previous experience, while (node) is changed to while (node ​​!== null).

Now he has no presence at all.

Next is the for...of statement. It is recommended to change it to the traditional array subscript self-decrement, which is the fastest. Of course, for...of is more readable in daily use.

Then popBestNextNode:

Here, the entire array is traversed each time to find the node with the smallest cost, and there is also an array element removal operation at the end. It is really hard for me to tell whether JavaScript arrays are stored in continuous memory or scattered, but in any case, a binary heap can be used instead to get better performance. I won’t implement it myself, but just use the existing one: https://www.npmjs.com/package/heap-js. Note that a custom comparator is passed into new Heap(), and then the implementation of popBestNextNode is changed to return this.queue.pop().

Finally, remove the two for loops in buildNodeGraph, no longer pre-initialize all Nodes, and add a new method to NodeGraph:

  getNearNodes (node) {
    let { x, y } = node
    let up = this.getNode(x, y - 1)
    let down = this.getNode(x, y + 1)
    let left = this.getNode(x - 1, y)
    let right = this.getNode(x + 1, y)
    return [ up, down, left, right ].filter(node ​​=> node !== null)
  }

In the subsequent path-finding loop, getNearNodes is called to obtain adjacent nodes, which greatly reduces the initial lag.

Finally, two strategies are provided:

• Strict: When the color difference between adjacent pixels is less than a certain value, they are added to the queue. For images with little color change in the walking area, the result is almost the shortest path.
• Fuzzy: Adjacent pixels are added to the queue regardless of the color difference, and their difference value is multiplied by certain coefficients as the cost of the node. Fits any picture and always finds a way in the end. . .

let nearNodes = nodeGraph.getNearNodes(current)
for (let i = nearNodes.length - 1; i >= 0; i--) {
  let node = nearNodes[i]
  if (node.checked === false) {
	node.checked = true

	let colordiff = getNodeColorDiff(node, current)
	const colorDiffThreshold = 2 // Allowable color difference, range 0~100

	node.parent = current
	node.endDistance = getDistance(node, nodeGraph.endNode)
	node.beginDistance = current.beginDistance + 1

	if (mode === "1") { // Strict node.cost = node.endDistance + node.beginDistance

	  if (colordiff < colorDiffThreshold) {
		nodeGraph.queue.push(node)
	  }
	} else if (mode === "2") { // Blur node.cost = node.endDistance + node.beginDistance + (colordiff * width * height)
	  nodeGraph.queue.push(node)
	}
  }
}

Source code: https://gitee.com/judgeou/maze-vite

This is the end of this article about combining Javascript with Vue to achieve automatic pathfinding for any maze image. For more relevant content about Javascript combined with Vue maze automatic pathfinding, please search for previous articles on 123WORDPRESS.COM or continue to browse the following related articles. I hope everyone will support 123WORDPRESS.COM in the future!