Javascript結(jié)合Vue怎樣實(shí)現(xiàn)對(duì)任意迷宮圖片的自動(dòng)尋路功能

小編給大家分享一下Javascript結(jié)合Vue怎樣實(shí)現(xiàn)對(duì)任意迷宮圖片的自動(dòng)尋路功能，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

前言

尋路前：

尋路后，自動(dòng)在圖片上生成紅色路徑，藍(lán)色是探索過的區(qū)域：

這里我故意用手機(jī)斜著角度拍，就是為了展示程序完全可以處理手機(jī)從現(xiàn)實(shí)拍攝的迷宮圖片。

整個(gè)程序我準(zhǔn)備用 Vue 3 + Vite 來寫，但其實(shí)用不用 Vue 都一樣，不會(huì)涉及復(fù)雜的界面，用別的框架甚至不用框架其實(shí)也完全可以。

二維數(shù)組，一本道

說了要從零開始，所以先嘗試從非常簡(jiǎn)單的迷宮入手吧

對(duì)于我們?nèi)祟悂碚f，這個(gè)迷宮十分簡(jiǎn)單，顯而易見的只有一條路。但是計(jì)算機(jī)解決這樣的迷宮還是得稍微花費(fèi)那么一點(diǎn)力氣的。

二維數(shù)組很適合用來表達(dá)這個(gè)迷宮：

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

1 代表可以走的格子，0 代表不能走的格子。每個(gè)格子可以使用 [x, y] 來表示，比如這里起點(diǎn)是 [0, 0]，終點(diǎn)是 [3, 4]。

那么應(yīng)該有這么一個(gè)函數(shù)： function solveMaze (matrix, begin, end) {//...}，matrix是描述迷宮的二維數(shù)組，begin 是起點(diǎn)，end 是終點(diǎn)，最終返回值是一個(gè)有序集合，每一個(gè)元素是一個(gè)格子，代表正確的路線軌跡。

這里我們準(zhǔn)備采用的策略十分簡(jiǎn)單，從起點(diǎn)開始，看看周圍上下左右（不能斜著走）哪些是可以走的格子，然后移動(dòng)到這個(gè)格子，接著循環(huán)上面的步驟，直到遇到 end 格子，注意還需要記錄上一步的格子，把它排除，以免走回頭路。具體看以下代碼：

// 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 = []

  // 當(dāng)前點(diǎn)
  let current = begin
  path.push(current)

  // 上次走過的路
  let lastPoint = begin

  // 隨便挑一個(gè)可以走的點(diǎn)
  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 獲取可以下一步通行的格子，solveMaze 獲取最終可行走的路徑，控制臺(tái)輸出：

這些坐標(biāo)就是最終的行走軌跡，目測(cè)是正確的。

映射基礎(chǔ)界面

為了方便測(cè)試觀察，得把我們的數(shù)據(jù)結(jié)構(gòu)映射到網(wǎng)頁上面。

// maze.js
// ...

// 導(dǎo)出 solveMaze 函數(shù)，讓vue組件調(diào)用
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" :>
          {{ 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>

最終效果：

其實(shí)就是通過二維數(shù)組 matrix 生成對(duì)應(yīng) div，數(shù)組里面元素值決定黑白。paths 數(shù)組存儲(chǔ)結(jié)果路徑，把路徑用紅色邊框標(biāo)記出來。這樣就方便以后測(cè)試結(jié)果的查看了。

廣度優(yōu)先，地毯式搜索

看看下面這個(gè)迷宮：

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

如果把他應(yīng)用到上面的代碼，會(huì)發(fā)現(xiàn)頁面卡死了，這是因?yàn)檫@個(gè)迷宮含有岔路，導(dǎo)致算法一直在繞圈。我們需要一些手段，把走過的路記住，以后就不再走了，方法不難，只要把當(dāng)前可以走的格子，放進(jìn)一個(gè)隊(duì)列中，然后要做的，就是不斷對(duì)這個(gè)隊(duì)列里的格子，作出同樣處理，直到遇到終點(diǎn)格子。

為了方便我們用算法進(jìn)行處理，需要使用新的數(shù)據(jù)結(jié)構(gòu)來表達(dá)，它就是 圖(Graph) 結(jié)構(gòu)。

圖結(jié)構(gòu)和鏈表很像，最大不同是每個(gè)節(jié)點(diǎn)可以有多個(gè)指針指向不同的節(jié)點(diǎn)。

同時(shí)把二維數(shù)組給他降維打擊，變成一維：

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

雖然這樣訪問起來不那么直接，但是只需要一次尋址，復(fù)制傳輸也比二維數(shù)組方便得多。

然后創(chuàng)建一個(gè) Node 類代表節(jié)點(diǎn)，NodeGraph 類代表整個(gè)圖結(jié)構(gòu)。

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 把 matrix 數(shù)組轉(zhuǎn)換為圖結(jié)構(gòu)，每個(gè)節(jié)點(diǎn)的 nearNodes 就相當(dāng)于是下一步可以走的格子集合，checked 表示這個(gè)節(jié)點(diǎn)是否已經(jīng)探索過。

為了方便查看每一步狀態(tài)的變化，需要把當(dāng)前所在格子和隊(duì)列中的格子，在畫面上標(biāo)記出來，完整代碼我就不貼了，codesandbox 可以隨意看：

藍(lán)色邊框就是隊(duì)列中的格子，小人就是當(dāng)前所在的格子，當(dāng)它走到右下角時(shí)就會(huì)停下來。

目前做的，只是順利讓小人移動(dòng)到終點(diǎn)而已，但是怎么得出我們要的路徑呢？方法就是在 Node 多加一個(gè)屬性 parent，記錄上一個(gè) Node。當(dāng)取出 nearNodes 時(shí)，把當(dāng)前節(jié)點(diǎn)賦值到每一個(gè) nearNode 的 parent 即可：

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

然后就是從當(dāng)前節(jié)點(diǎn)，讀取 parent 一個(gè)一個(gè)回溯即可：

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

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

  return path
}

效果：

當(dāng)小人到達(dá)終點(diǎn)時(shí)，紅色方格就是最短路徑了。

地圖編輯

稍微改動(dòng)下代碼，讓我們可以實(shí)時(shí)編輯迷宮，測(cè)試更加方便。

操作：點(diǎn)擊方格可以改變黑白狀態(tài)，按住alt點(diǎn)擊可以設(shè)置新的目標(biāo)點(diǎn)。

逐漸把 solveMaze 里面的局部變量移到 NodeGraph 類里面，這樣外部訪問更加便利。注意當(dāng)尋路結(jié)束的時(shí)候，不要結(jié)束函數(shù)，而是使用 while 循環(huán)一直等待新的目標(biāo)點(diǎn)被設(shè)置：

// ...

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

優(yōu)化尋路算法

想象一下這種情形：

起點(diǎn)和終點(diǎn)一條直線，中間毫無阻擋，但是這個(gè)小人竟然到處跑，好一會(huì)才到終點(diǎn)，這樣下去不行的，必須要優(yōu)化。

在 Node 類加一個(gè)屬性 endDistance 記錄每個(gè)節(jié)點(diǎn)到終點(diǎn)的距離，getDistance 函數(shù)根據(jù)坐標(biāo)可以直接計(jì)算出距離，這個(gè)距離是沒有考慮到中間可能出現(xiàn)的障礙的，但對(duì)路線的評(píng)估也十分有用：

class Node {
  constructor (x, y, value) {
    this.x = x
    this.y = y
    this.value = value
    this.endDistance = 0 // 與終點(diǎn)的距離，忽略中間的障礙
    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)
}

每次通過 popBestNextNode 方法從隊(duì)列取出 endDistance 最小的 Node：

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

既然有 endDistance，那也要有 beginDistance，用來記錄從起點(diǎn)走過來的步數(shù)。這個(gè)數(shù)值不直接從坐標(biāo)計(jì)算，而是隨著前進(jìn)累加，這樣 beginDistance 就不是估算值了，而是實(shí)際值：

// ...
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)
  }
}
// ...

考慮到以后可能會(huì)有新的因素加入，所以直接添加一個(gè) cost 屬性，用來表達(dá) 成本。目前 cost 就是 endDistance + beginDistance，cost 越小，優(yōu)先級(jí)越高。

像這樣的情況，小人一開始企圖從上方靠近，但是隨著不斷前進(jìn)，經(jīng)過的步數(shù)越來越多，倒不如走下面了，于是就放棄的上面的路線。

現(xiàn)在，小人的行動(dòng)變成更加靠譜了：

對(duì)圖片進(jìn)行尋路

拿這張我隨便畫的圖來作為參數(shù)：

目標(biāo)是從 B 點(diǎn)到達(dá) E 點(diǎn)，我們只需要讀取這張圖片的像素，根據(jù)黑白顏色，轉(zhuǎn)換成為一個(gè)數(shù)組，放到 solveMaze 函數(shù)即可。

為此，需要有一個(gè) input 標(biāo)簽，type="file"，用來選擇圖片，通過 URL.createObjectURL(File) 生成一個(gè) URL，然后使用 new Image() 創(chuàng)建一個(gè) img 標(biāo)簽，它不需要添加進(jìn) body，把 url 給到 img.src。通過 CanvasRenderingContext2D.drawImage() 復(fù)制進(jìn) Canvas，再調(diào)用 CanvasRenderingContext2D.getImageData() 即可獲取像素?cái)?shù)組。

這時(shí)不能再用 div 去渲染了，因?yàn)檫@張圖幾萬個(gè)像素，每個(gè)像素一個(gè) div 的話，瀏覽器也吃不消，再加上將來圖片將會(huì)更大。

所以這里改用 Canvas 進(jìn)行渲染，安排三個(gè) Canvas，一個(gè)顯示迷宮的原圖，一個(gè)顯示探索過的節(jié)點(diǎn)，一個(gè)顯示當(dāng)前最短路徑，也就是 path 數(shù)組里面的節(jié)點(diǎn)，然后把這三個(gè) Canvas 疊在一起即可，最后就是在回調(diào)里面去更新后面兩個(gè) Canvas 即可。

把我上面的圖片下載到自己電腦，點(diǎn)擊選擇文件按鈕選擇圖片，然后就能看到效果了，選別的圖片也可以，只是我的起點(diǎn)和終點(diǎn)坐標(biāo)是寫死的，而且代碼沒有優(yōu)化過，太大的圖片恐怕難以處理。

注意：如果遇到跨域問題那就要自己上傳圖片了。

自定義起始點(diǎn)，以及隨時(shí)變更路線

利用點(diǎn)擊事件中的 offsetX、offsetY 即可知道點(diǎn)擊坐標(biāo)，把起點(diǎn)和終點(diǎn)的坐標(biāo)保存起來，一旦有變化，則停止之前的尋路函數(shù)，重新執(zhí)行當(dāng)前的尋路函數(shù)，因此需要在循環(huán)中作一個(gè)判斷來決定是否退出函數(shù)，這件事情適合在回調(diào)里面做。

然后提供一個(gè)輸入框，自由調(diào)整經(jīng)歷多少個(gè)循環(huán)才更新一次畫面，這樣能調(diào)整尋路的速度。

處理彩色圖片

預(yù)覽：https://codesandbox.io/s/maze-vite-8-h845p?file=/src/App.vue (注意如果出現(xiàn)跨域錯(cuò)誤，就自己上傳圖片吧)

不放iframe了，感覺放太多了，讓這個(gè)頁面已經(jīng)相當(dāng)卡。

前面都是默認(rèn)白色像素是可以行走的區(qū)域，現(xiàn)在嘗試把顏色相似的附近像素作為行走區(qū)域，這樣效果會(huì)更加好。

直接把 rgba 顏色數(shù)據(jù)傳入 solveMaze，然后在循環(huán)中計(jì)算出相鄰節(jié)點(diǎn)與當(dāng)前節(jié)點(diǎn)的顏色差距，差距過大則不放入隊(duì)列。

把一個(gè) rgba 整數(shù)的各個(gè)通道拆分開來可以這么寫：

/**
 * 獲取 Node 的 RGB 值
 * @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 ]
}

求 rgb 顏色的相似度，最樸素的方法是把兩個(gè)顏色看成是兩個(gè)三維坐標(biāo)的點(diǎn)，然后求其歐幾里得距離，但這不符合人眼的感知模型。詳細(xì)方法wiki已經(jīng)有了：https://zh.wikipedia.org/wiki/顏色差異

關(guān)于這方面的運(yùn)算有點(diǎn)復(fù)雜，我都寫到了 color.js 里面了。

結(jié)果：

注意代碼里的 colorDiffThreshold，目前我用的 2.25，如果太高，會(huì)導(dǎo)致穿墻，太低則容易找不到路失敗。

性能優(yōu)化

當(dāng)點(diǎn)擊兩次畫面后，需要稍微等一會(huì)才會(huì)開始尋路，這里應(yīng)該耗費(fèi)了不少CPU。打開 DevTools 的性能分析器分析下到底是哪里消耗最多性能：

很明顯 solveMaze 函數(shù)占據(jù)了大多數(shù)時(shí)間，展開下面的 Call Tree：

buildNodeGraph 和 getNode 是優(yōu)化重點(diǎn)，打開代碼，可以直接看到每句話耗費(fèi)的CPU時(shí)間：

57 行的 if (!node) {...} 明明是簡(jiǎn)單的判斷，卻耗費(fèi)了不少時(shí)間，試試看改成 node === undefined，并且 value 也不再需要判斷了。對(duì) nodes 數(shù)組的訪問與讀取也耗費(fèi)不少時(shí)間，嘗試一開始用 new Array(length) 初始化，應(yīng)該會(huì)好一些。優(yōu)化之后的代碼：

看起來稍微好一些。

在尋路途中進(jìn)行性能監(jiān)測(cè)：

發(fā)現(xiàn) buildPath 相當(dāng)?shù)暮馁M(fèi)時(shí)間，這也是理所應(yīng)當(dāng)?shù)?，畢竟每次循環(huán)都調(diào)用，并且完整遍歷整個(gè)鏈條。處理辦法也簡(jiǎn)單，只在最后出結(jié)果時(shí)調(diào)用他即可，根據(jù)前面的經(jīng)驗(yàn)，while (node) 改為 while (node !== null)。

現(xiàn)在他完全沒有存在感了。

然后是 for...of 語句，建議改為傳統(tǒng)的數(shù)組下標(biāo)自減，這是最快的，當(dāng)然日常使用 for...of 可讀性更強(qiáng)。

然后是 popBestNextNode：

這里每次都完整遍歷整個(gè)數(shù)組找出cost最小的節(jié)點(diǎn)，最后還有一個(gè)數(shù)組元素移除的操作。我真的很難判斷 JavaScript 的數(shù)組到底是存儲(chǔ)在連續(xù)內(nèi)存里面還是分散的，但是不管怎么樣，這里完全可以使用二叉堆替代來獲取更好的性能。具體就不自己實(shí)現(xiàn)了，直接用現(xiàn)成的：https://www.npmjs.com/package/heap-js。注意 new Heap() 的時(shí)候傳入自定義的比較器，然后把 popBestNextNode 的實(shí)現(xiàn)改為 return this.queue.pop() 即可。

最后，把 buildNodeGraph 的那兩層for循環(huán)全部移除，不再預(yù)先初始化所有的 Node，給 NodeGraph 添加一個(gè)新方法：

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

在后面的尋路循環(huán)中再去調(diào)用 getNearNodes 來獲取相鄰的節(jié)點(diǎn)，這樣就大幅縮減了一開始的卡頓了。

最后，提供兩種策略：

• 嚴(yán)格：當(dāng)相鄰像素顏色差距小于某個(gè)值，才加入隊(duì)列。適合行走區(qū)域的顏色變化不大的圖片，得出的結(jié)果幾乎就是最短的路徑。

• 模糊：相鄰像素?zé)o論顏色的差距，都加入隊(duì)列，其差距值乘以某些系數(shù)，作為節(jié)點(diǎn)的 cost。適合任何圖片，最終總是能找到一條路。。。

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 // 容許通過的顏色差異，范圍 0~100

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

	if (mode === "1") { // 嚴(yán)格
	  node.cost = node.endDistance + node.beginDistance

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

以上是“Javascript結(jié)合Vue怎樣實(shí)現(xiàn)對(duì)任意迷宮圖片的自動(dòng)尋路功能”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對(duì)大家有所幫助，如果還想學(xué)習(xí)更多知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道！